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


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


[1] Knuth, D.E.; Bendix, P.B., Simple word problems in universal algebras, (), 263-297 · Zbl 0188.04902
[2] Huet, G., Confluent reductions; abstract properties and applications to term rewriting systems, (), 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, () · Zbl 0449.20059
[4] Lankford, D.S.; Ballantyne, A.M., Decision procedures for simple equational theories with permutative axioms: complete sets of permutative reductions, () · 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, () · 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 Princeton, New Jersey
[7] Evans, T., On multiplicative systems defined by generators and relations.—I. normal form theorems, (), 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, ()
[11] Degano, P.; Sirovich, F., On deciding equivalence for a class of primitive recursive functions, () · Zbl 0449.68054
[12] Bücken, H., Reduction systems and small cancellation theory, (), 53-59, Austin, Texas
[13] Hack, M., Decision problems for Petri nets and vector addition systems, ()
[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 New York
[19] Simmons, H., The word and torsion problems for commutative thru systems, (), 395-400
[20] Redei, L., The theory of finitely generated commutative semigroups, (1965), 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, (), 50-54 · Zbl 0374.20067
[24] Cardoza, E.W., Ms. thesis, computational complexity of the word problem for commutative semigroups, ()
[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, (), 87-100
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.