Exponential space complete problems for Petri nets and commutative semigroups (Preliminary Report)
作者： E. Cardoza , R. Lipton , A. R. Meyer
关键词: Commutative property 、 Discrete mathematics 、 Mathematics 、 Semigroup 、 Word problem (mathematics) 、 Decidability 、 Special classes of semigroups 、 Finite set 、 Preliminary report 、 Petri net
摘要: The uniform word problem for commutative semigroups (UWCS) is the of determining from any given finite set defining relations and pair words, whether words describe same element in semigroup defined by relations. effective decidability this classical algebraic was first explicitly noted Malcev [1958] Emilichev [1958], though retrospect result can be seen to contained earlier work Konig [1903] Hermann [1926] on polynomial ideals.
acm.org
sci-hub.se 参考文章(13)
Grete Hermann, Die Frage der endlich vielen Schritte in der Theorie der Polynomideale. (Unter Benutzung nachgelassener Sätze von K. Hentzelt) Mathematische Annalen. ,vol. 95, pp. 736- 788 ,(1926) , 10.1007/BF01206635
Gyula Kőnig, Einleitung in die allgemeine Theorie der algebraischen Gröszen B.G. Teubner. ,(1903)
Seymour Ginsburg, Edwin Spanier, Semigroups, Presburger formulas, and languages. Pacific Journal of Mathematics. ,vol. 16, pp. 285- 296 ,(1966) , 10.2140/PJM.1966.16.285
Michel Hack, The equality problem for vector addition systems is undecidable Theoretical Computer Science. ,vol. 2, pp. 77- 95 ,(1976) , 10.1016/0304-3975(76)90008-6
Walter J. Savitch, Relationships between nondeterministic and deterministic tape complexities Journal of Computer and System Sciences. ,vol. 4, pp. 177- 192 ,(1970) , 10.1016/S0022-0000(70)80006-X
Leonard Adleman, Kenneth Manders, Computational complexity of decision procedures for polynomials foundations of computer science. pp. 169- 177 ,(1975) , 10.1109/SFCS.1975.9
A. Seidenberg, Constructions in algebra Transactions of the American Mathematical Society. ,vol. 197, pp. 273- 313 ,(1974) , 10.1090/S0002-9947-1974-0349648-2
L. J. Stockmeyer, A. R. Meyer, Word problems requiring exponential time(Preliminary Report) Proceedings of the fifth annual ACM symposium on Theory of computing - STOC '73. pp. 1- 9 ,(1973) , 10.1145/800125.804029
Emil L. Post, Recursive Unsolvability of a Problem of Thue Journal of Symbolic Logic. ,vol. 12, pp. 1- 11 ,(1947) , 10.2307/2267170
A. P. Biryukov, Some algorithmic problems for finitely defined commutative semigroups Siberian Mathematical Journal. ,vol. 8, pp. 384- 391 ,(1967) , 10.1007/BF02196421