The complexity of the word problems for commutative semigroups and polynomial ideals.(English)Zbl 0506.03007
MSC:
| 03D15 | Complexity of computation (including implicit computational complexity) |
| 20M14 | Commutative semigroups |
| 68Q25 | Analysis of algorithms and problem complexity |
| 08A50 | Word problems (aspects of algebraic structures) |
| 03D40 | Word problems, etc. in computability and recursion theory |
| 20F10 | Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) |
Cite
Full Text:DOI
References:
| [1] | Aho, A. V.; Hopcroft, J. E.; Ullman, J. D., The Design and Analysis of Computer Algorithms (1974), Addison-Wesley: Addison-Wesley Reading, Massachusetts ·Zbl 0207.01701 |
| [2] | Biryukov, A. P., Some algorithmic problems for finitely defined commutative semigroups, Siberian Math. J., 8, 384-391 (1967) ·Zbl 0223.20064 |
| [3] | Blum, M., A machine-independent theory of the complexity of recursive functions, J. Assoc. Comput. Mach., 14, 322-336 (1967) ·Zbl 0155.01503 |
| [4] | Blum, M., On effective procedures for speeding up algorithms, J. Assoc. Comput. Mach., 18, 290-305 (1971) ·Zbl 0221.02016 |
| [5] | Cardoza, E. W., Computational Complexity of the Word Problem for Commutative Semigroups (October 1975), M.I.T., Project MAC, TM 67 |
| [6] | Cardoza, E.; Lipton, R.; Meyer, A. R., Exponential space complete problems for Petri nets and commutative semigroups: Preliminary report, (Proceedings, 8th Ann. ACM STOC (1976)), 50-54 ·Zbl 0374.20067 |
| [7] | Cook, S. A., The complexity of theorem proving procedures, (Proceedings, 3rd Ann. ACM STOC (1971)), 151-158 ·Zbl 0363.68125 |
| [8] | Emiličev, V. A., On algorithmic decidability of certain mass problems in the theory of commutative semigroups, Sibirsk. Mat. Ž, 4, 788-798 (1963), [In Russian.] ·Zbl 0147.00703 |
| [9] | Ferrante, J.; Rackoff, C., The Computational Complexity of Logical Theories, (Lecture Notes in Mathematics No. 718 (1979), Springer-Verlag: Springer-Verlag Berlin/Heidelberg/New York) ·Zbl 0404.03028 |
| [10] | Fischer, P. C.; Meyer, A. R.; Rosenberg, A. L., Counter machines and counter languages, Math. Systems Theory, 2, 3, 265-283 (1968) ·Zbl 0165.32002 |
| [11] | Ginsburg, S.; Spanier, E. H., Semigroups, Presburger formulas, and languages, Pacific J. Math., 16, 2, 285-296 (1965) ·Zbl 0143.01602 |
| [12] | Hack, M., Petri Nets and Commutative Semigroups (July 1974), M.I.T., Project MAC, CSGN 18 |
| [13] | Hack, M., Decidability Questions for Petri Nets (June 1976), M.I.T., Laboratory for Computer Science, TR 161 |
| [14] | Hentzelt, K., Zur Theories der Polynomideale und Resultanten, Math. Ann., 88, 53-79 (1922) ·JFM 48.0094.03 |
| [15] | Hermann, G., Die Frage der endlich vielen Schritte in der Theorie der Polynomideale, Math. Ann., 95, 736-788 (1926) ·JFM 52.0127.01 |
| [16] | Hilbert, D., Über die Theorie der algebrischen Formen, Math. Ann., 36, 473-534 (1890) ·JFM 22.0133.01 |
| [17] | Holt, A. W., (Final Report of the Information Systems Theory Project (1968), Rome Air Development Center (N.Y.): Rome Air Development Center (N.Y.) Griffiss Air Force Base), RADC-TR-68-305 |
| [18] | Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, Massachusetts ·Zbl 0196.01701 |
| [19] | Hartmanis, J.; Stearns, R. E., On the computational complexity of algorithms, Trans. Amer. Math. Soc., 117, 285-306 (1965) ·Zbl 0131.15404 |
| [20] | Karp, R. M., Reducibility among Combinatorial Problems, (Complexity of Computer Computations (1972), Plenum: Plenum New York), 85-104 ·Zbl 0366.68041 |
| [21] | Keller, R. M., Vector Replacement Systems: A Formalism for Modelling Asynchronous Systems (December 1972), Princeton University, CSL, TR 117 |
| [22] | König, J., Einleitung in die allgemeine Theorie der algebraischen Grössen (1903), Teubner: Teubner Leipzig ·JFM 34.0093.02 |
| [23] | Laing, R., Realization and Complexity of Commutative Events (1967), University of Michigan, TR 03105-48-T |
| [24] | Lipton, R., The Reachability Problem is Exponential-Space-Hard, Yale University, Department of Computer Science, Report No. 62 (January 1976) |
| [25] | Malcev, A. I., On homomorphisms of finite groups, Ivanov. Gos. Ped. Inst. Učen. Zap., 18, 49-60 (1958), [In Russian.] |
| [26] | Mayr, E. W.; Meyer, A. R., The Complexity of the finite containment problem for Petri Nets, J. Assoc. Comput. Mach., 28, 2 (1981) ·Zbl 0462.68020 |
| [27] | Markov, A., The impossibility of certain algorithms in the theory of associative systems, Dokl. Akad. Nauk SSSR, 5, 587-590 (1947) |
| [28] | Mayr, E. W., An algorithm for the general Petri net reachability problem, (Proceedings, 13th Ann. ACM STOC (1981)), 238-246 |
| [29] | Meyer, A. R., The inherent computational complexity of theories of ordered sets, (Proceedings of the International Congress of Mathematicians, 1974, Vol. 2 (1975)), 477-482 ·Zbl 0361.02061 |
| [30] | Minsky, M., Recursive unsolvability of Post’s problem of tag and other topics in the theory of Turing machines, Ann. Math., 74, 437-455 (1961) ·Zbl 0105.00802 |
| [31] | Meyer, A. R.; Stockmeyer, L., The equivalence problem for regular expressions with squaring requires exponential space, (Proceedings, 13th Ann. IEEE Symp. on SWAT (1973)), 125-129 |
| [32] | Machtey, M.; Young, P. R., An Introduction to the General Theory of Algorithms (1978), North-Holland: North-Holland New York ·Zbl 0376.68027 |
| [33] | Petri, C. A., Kommunikation mit Automaten, (Schriften des IMM No. 2 (1962), Institut für Instrumentelle Mathematik (Bonn)) |
| [34] | Post, E., Recursive unsolvability of a problem of Thue, J. Symbolic Logic, 12, 1-11 (1947) ·Zbl 1263.03030 |
| [35] | Rackoff, C., The covering and boundedness problems for vector additions systems, Theoret. Comput. Sci., 6, 223-231 (1978) ·Zbl 0368.68054 |
| [36] | Richman, F., Constructive aspects of Noetherian rings, (Proc. Amer. Math. Soc., 44 (1974)), 436-441 ·Zbl 0265.13011 |
| [37] | Savitch, W., Relationships between nondeterministic and deterministic tape complexities, J. Comput. System Sci., 4, 177-192 (1970) ·Zbl 0188.33502 |
| [38] | Seidenberg, A., Constructions in algebra, Trans. Amer. Math. Soc., 197, 273-313 (1974) ·Zbl 0356.13007 |
| [39] | Simmons, H., The word and torsion problems for commutative Thue systems, (Adian, S. I.; Boone, W. W.; Higman, G., Word Problems II (1980), North-Holland: North-Holland New York), 395-400 ·Zbl 0432.03023 |
| [40] | Stockmeyer, L.; Meyer, A. R., Word problems requiring exponential space, (Proceedings, 5th Ann. ACM STOC (1973)), 1-9 ·Zbl 0359.68050 |
| [41] | Stockmeyer, L., The Complexity of Decision Problems in Automata Theory and Logic (1974), M.I.T., Project MAC, TR 133 |
| [42] | Taiclin, M. A., Algorithmic problems for commutative semigroups, Soviet Math. Dokl., 9, 201-204 (1968) ·Zbl 0174.02201 |
| [43] | Taiclin, M. A., On the isomorphism problem for commutative semigroups, Math. USSR Sb., 22, 104-128 (1974) ·Zbl 0302.20050 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
