Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report)

ABSTRACT

The uniform word problem for commutative semigroups (UWCS) is the problem of determining from any given finite set of defining relations and any pair of words, whether the words describe the same element in the commutative semigroup defined by the relations. The effective decidability of this classical algebraic problem was first explicitly noted by Malcev [1958] and Emilichev [1958], though in retrospect this result can be seen to be contained in the earlier work of König [1903] and Hermann [1926] on polynomial ideals.

REFERENCES

• 1: Adleman, L., and K. Manders, "Computational Complexity of Decision Procedures for Polynomials," 16th IEEE Annual Symp. on Foundations of Computer Science, 1975, pp. 169-177.
• 2: Biryukov, A.P., "Some Algorithmic Problems for Finitely Defined Commutative Semigroups," Siberian Mathematics Journal, Vol. 8, 1967, pp. 384-391.
• 3: Cardoza, E.W., "Computational Complexity of the Word Problem for Commutative Semigroups," Project MAC Technical Memorandum 67, M.I.T., 1975.
• 4: Emelichev, V.A., "Commutative Semigroups with One Defining Relation," Shuya Gosudarstvennyi Pedagogicheskii Institut Uchenye Zapiski, Vol. 6, 1958, pp. 227-242.
• 5: Fischer, P.C., Meyer, A.R., and A.L. Rosenberg, "Counter Machines and Counter Languages," Mathematical Systems Theory, Vol. 2, No. 3, 1968, pp. 265-283.
• 6: Ginsburg, S., and E.H. Spanier, "Semigroups, Presburger Formulas, and Languages," Pacific Journal of Mathematics, Vol. 16, No. 2, 1965, pp. 285-296.
• 7: Hack, M., "The Equality Problem for Vector Addition Systems is Undecidable," Computation Structures Group Memo 121, Project MAC, M.I.T., 1975, pp.1-32.
• 8: Hermann, G., "Die Frage der endlich vielen Schritte in der Theorie der Polynomideale," Math. Ann., Vol. 95, 1926, pp. 736-788.
• 9: Karp, R., and R. Miller, "Parallel Program Schemata," JCSS, Vol. 3, 1969, pp. 147-195.
• 10: Konig, J., Einleitung in die Allgemeine Theorie der Algebraischen Groszen, B.G. Teubner, Leipzig, 1903.
• 11: Lipton, R., "The Reachability Problem Requires Exponential Space," Technical Report, Department of Computer Science, Yale University, 1975; Theoretical Computer Science, 1976, to appear.
• 12: Malcev, A.I., "On Homomorphisms of Finite Groups," Ivano Gosudarstvenni Pedagogicheski Institut Uchenye Zapiski, Vol. 18, 1958, pp. 49-60.
• 13: Markov, A., "The Impossibility of Certain Algorithms in the Theory of Associative Systems," Dokl. Akad. Nauk SSSR, Vol. 5, 1947, pp. 587-590.
• 14: Post, E., "Recursive Unsolvability of a Problem of Thue," J. Symbolic Logic, Vol. 12, 1947, pp. 1-11.
• 15: Savitch, W., "Relations between Nondeterministic and Deterministic Tape Complexities," JCSS, Vol. 14, 1970, pp. 177-192.
• 16: Seidenberg, A., "Constructions in Algebra," Trans. American Mathematical Society, Vol. 197, 1974,
• 17: Stockmeyer, L., The Complexity of Decision Problems in Automata Theory and Logic, Project MAC Technical Report 133, M.I.T., 1974.
• 18: L. J. Stockmeyer , A. R. Meyer, Word problems requiring exponential time(Preliminary Report), Proceedings of the fifth annual ACM symposium on Theory of computing, p.1-9, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804029]
• 19: Taiclin, M.A., "Algorithmic Problems for Commutative Semigroups," Soviet Mathematics Doklady, Vol. 9, 1968, pp. 201-204.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.0 General

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
          Subjects: Reducibility and completeness
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

General Terms:
Theory