lescanne@poincare.crin.fr (Pierre Lescanne) (11/09/90)
At the beginning of summer I asked about the decidability of the word
problem in semi-groups and known results. I received many answers and
I thank those who gave me information.
I would like first to state precisely what I was interested in, by
reformulating the question as follows: "Does there exist a decision
procedure that takes a set A of pairs of vectors over the natural
numbers (the relations or axioms) and a pair of vectors (w1,w2) (the
identity or theorem to be proved) and says whether w is a consequence
of A?" A can also be seen as a set of pairs of ground terms on * and
V as an alphabet of constants, where * is supposed associative and
commutative. For instance "Is <aaab = aaabbbb> a consequence of <abbb
= aab> and <abb = aabbb>" is an instance of the problem that should be
decided by the procedure.
The most often quoted paper is
Ernest Mayr and Albert Meyer, "The Complexity of the Word Problems for
Commutative Semigroups and Polynomial Ideals"in "Advances in
Mathematics" 46, pp. 305-329 (1982).
It contains a full bibliography. In addition Yuri Gurevich said
The problem is decidable, see Michael Taitslin's paper in Algebra and
Logica, 1966, number 4 (in Russian), where a much more general problem is
proved decidable. At that time people did not care about complexity.
Pedersen mentions Emelichev, 1958 (obscure Russian journal), Mal'cev,
1958 (translated in American Math Soc translations 2, 1956).
Additional references are quoted on p.17 of Jantzen's EATCS monograph
on confluent string rewriting. For confluence methods there is of
course Ballantyne and Lankford's work (Computing and Math with Applic
7, (1981), 159-165), and R. Gilman J. Algebra 57 (1971), 544-554.
Also he (Pedersen) gave a generalization of Ballantyne and Lankford's
approach in his dissertation (unpublished).
(Note: Ballantyne and Lankford solve a different problem than the one I
addressed, since they accept the introduction of new non-nullary
operators and of non-ground axioms. For instance they can provide by
completion a decision procedure for abelian groups that are
commutative semi-groups plus a unary operator "minus" and a constant 0,
plus a few non-ground axioms.)
Clote points out a new paper "Complexity of unification in free groups
and free semigroups" of A. Koscielski and L. Pacholski (Rapport de
recherche, Universite de Caen, and to appear in next FOCS) where the
authors give exponential time upper and lower bounds for the problem
of satisfaction of a word equation in a finite alphabet.
McNaughton mentioned "Cancellativity in finitely presented semigroups"
by P. Narendran and C. O'Dunlaing, J. SYMBOLIC COMPUTATION, vol. 7
(1989), pp. 457-472.
One should also mention:
Dung T.Huynh, Complexity of the word problem for commutative
semigroups of fixed dimension, Acta Informatica, (1985), vol. 22,
pp.421-423.
----- Pierre Lescanne -----
--
Pierre LESCANNE
Centre de Recherche en Informatique de Nancy (CNRS)
INRIA-Lorraine
<telephone>: (work) 83 59 30 07 (country code is 33)
(home) 83 22 76 92
<fax>: 83 27 83 19
<e-mail>: lescanne@loria.crin.fr
<post>: BP 239, F54506 VANDOEUVRE Cedex FRANCE