×

New decision algorithms for finitely presented commutative semigroups. (English) Zbl 0449.20059


MSC:

20M05 Free semigroups, generators and relations, word problems
68T99 Artificial intelligence
20M35 Semigroups in automata theory, linguistics, etc.
20M14 Commutative semigroups
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Knuth, D. E.; Bendix, P. B., Simple word problems in universal algebras, (Leech, J., Proc. Computational Problems in Abstract Algebras (1970), Pergamon Press: Pergamon Press Oxford), 263-297 · Zbl 0188.04902
[2] Huet, G., Confluent reductions; abstract properties and applications to term rewriting systems, (Proc. 18th Symp. Foundations of Comput. Sci.. Proc. 18th Symp. Foundations of Comput. Sci., Providence. Proc. 18th Symp. Foundations of Comput. Sci.. Proc. 18th Symp. Foundations of Comput. Sci., Providence, Rapport de Recherche No. 283 (1977)). (Proc. 18th Symp. Foundations of Comput. Sci.. Proc. 18th Symp. Foundations of Comput. Sci., Providence. Proc. 18th Symp. Foundations of Comput. Sci.. Proc. 18th Symp. Foundations of Comput. Sci., Providence, Rapport de Recherche No. 283 (1977)), IRIA Laboria, Rocquencourt, B.P. No. 105, 78105 Le Chesnay (1977)
[3] Lankford, D. S.; Ballantyne, A. M., Decision procedures for simple equational theories with commutative axioms: complete sets of commutative reductions, (Rept. ATP-35 (1977), University of Texas: University of Texas Austin, Texas) · Zbl 0449.20059
[4] Lankford, D. S.; Ballantyne, A. M., Decision procedures for simple equational theories with permutative axioms: complete sets of permutative reductions, (Rept. ATP-37 (1977), University of Texas: University of Texas Austin, Texas) · Zbl 0449.20059
[5] Lankford, D. S.; Ballantyne, A. M., Decision procedures for simple equational theories with commutative-associative axioms: complete sets of commutative-associative reductions, (Rept. ATP-39 (1977), University of Texas: University of Texas Austin, Texas) · Zbl 0449.20059
[6] Stickel, M.; Peterson, G., Complete sets of reductions for equational theories with complete unification algorithms (1977), RCA David Sarnoff Research Center: RCA David Sarnoff Research Center Princeton, New Jersey
[7] Evans, T., On multiplicative systems defined by generators and relations.—I. Normal form theorems, (Proc. Camb. Phil. Soc., 47 (1951)), 637-649 · Zbl 0043.02001
[8] Newman, M. H.A., On theories with a combinatorial definition of equivalence, Ann. Math., 43, 223-243 (1942) · Zbl 0060.12501
[9] Evans, T., A decision problem for transformations of trees, Can. J. Math., 15, 584-590 (1963) · Zbl 0116.14905
[10] Treash, C., Inverse property loops and related Steiner triple systemsau]C. Treash, (Ph.D. Thesis (1969), Emory University)
[11] Degano, P.; Sirovich, F., On deciding equivalence for a class of primitive recursive functions, (Consiglio Nazionale delle Ricerche (1979), Instituto di Elaborazione delle Informazione: Instituto di Elaborazione delle Informazione Pisa) · Zbl 0449.68054
[12] Bücken, H., Reduction systems and small cancellation theory, (Proc. 4th Workshop Automated Deduction (1-3 Feb. 1979)), 53-59, Austin, Texas
[13] Hack, M., Decision problems for Petri nets and vector addition systems, (Computational Structures Group Memo, 95 (1974), Project MAC, M.I.T: Project MAC, M.I.T Cambridge, Mass)
[14] Biryukov, A. P., Some algorithmic problems for finitely defined commutative semigroups, Siberian Math. J., 8, 384-391 (1967) · Zbl 0223.20064
[15] Emelichev, V. A., Commutative semigroups with one defining relation, Shuya Gosudarstvennyi Pedagogicheskii Institut Uchenye Zapiski, 6, 227-242 (1958)
[16] Hermann, G., Die frage der endlich vielen schritte in der theorie der polynomideale, Math. Ann., 95, 736-788 (1926) · JFM 52.0127.01
[17] Malcev, A. I., On homomorphisms of finite groups, Ivano Gosudarstvennyi Pedagogicheskii Institut Uchenye Zapiski, 18, 49-60 (1958)
[18] Rabin, M., Logic, In Automata, and Computability Conf. (1965), Oriskany: Oriskany New York
[19] Simmons, H., The word and torsion problems for commutative thru systems, (Boone, W.; Higman, G., Word Problems II (1980), North-Holland: North-Holland Amsterdam), 395-400 · Zbl 0432.03023
[20] Redei, L., The Theory of Finitely Generated Commutative Semigroups (1965), Pergamon Press: Pergamon Press Oxford · Zbl 0133.27904
[21] Seidenberg, A., Constructions in algebra, Trans. Am. Math. Soc., 197, 272-313 (1974) · Zbl 0356.13007
[22] König, J., Einleitung in die Allgemeine Theorie der Algebraischen Groszen (1903), Teubner, Leipzig · JFM 34.0093.02
[23] Cardoza, E.; Lipton, R.; Meyer, A. R., Exponential space complete problems for Petri nets and commutative semigroups, (Proc. 8th Annual ACM Symposium on Theory of Computing (1976)), 50-54 · Zbl 0374.20067
[24] Cardoza, E. W., Ms. Thesis, Computational complexity of the word problem for commutative semigroups, (MAC Technical Memo. 67 (1975), MIT: MIT Cambridge Mass)
[25] Evans, T., The isomorphism problem for some classes of multiplicative systems, Trans. Am. Math. Soc., 109, 303-312 (1963) · Zbl 0141.01303
[26] Evans, T., Some solvable word problems, (Boone, W.; Higman, G., Word Problems II (1980), North-Holland: North-Holland Amsterdam), 87-100 · Zbl 0432.08004
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.