Efficient solution of the word problem in slim varieties (Q1315326)

The aim of the paper is to formulate general conditions on a variety that ensure halting of what the author calls the ``confluence-completion process'' (probably better known as the Knuth-Bendix procedure) and thus imply unifom solvability of the word problem for the variety. The starting point of the author's considerations is the fact that the procedure halts for the variety of all commutative semigroups. Therefore his general conditions imitate some quite specific properties of the latter variety. Let \(W\) be the absolutely free algebra of some type and let \(F\) be the free algebra of a variety of this type. For \(w\in W\), its equivalence class in \(F\) is denoted by \(\{w\}\) and the word obtained from \(w\) by replacing an occurrence of a subword \(u\) by \(v\) is denoted by \(w[ u/v]\). A representation of \(F\) is any injection \(\rho\) of \(F\) into a well- ordered set such that if \(\rho (\{r\})> \rho(\{ s\})\) and \(u\) is any word containing a subword \(r'\) with \(\{r'\}= \{r\}\), then \(\rho( \{u\})> \rho( \{u [r'/s]\})\). Let \(\{v \}\subseteq \{w\}\) denote that some \(v'\in \{v\}\) is a subword of some \(w'\in \{w\}\). It can be easily proved that if \(F\) has a representation, then \(\subseteq\) is a partial order on \(F\). A variety is said to be slim if each of its finitely generated free algebras has solvable word problem, is representable and well quasi- ordered under \(\subseteq\). The critical pair of two relations \((p_ 1, q_ 1)\) and \((p_ 2, q_ 2)\) with \(\rho (\{ p_ i \})> \rho (\{q_ i\})\) is \((\{w_ 1 [p_ 1/ q_ 1]\}\), \(\{w_ 2 [p_ 2/ q_ 2]\})\), where the pair \((w_ 1, w_ 2)\) of words is such that \(\{w_ 1\}= \{w_ 2\}\), \(p_ i\) is a subword of \(w_ i\), and there is no similar pair \((u_ 1, u_ 2)\) with \(u_ i\) a subword of \(w_ i\), \(i=1,2\). A variety in which the set of critical pairs of any finite set of relations can be effectively computed is called critically computable. The main results of the paper (Theorems 2 and 3) say that if \(V\) is a slim critically computable variety given by a set of balanced identities, then the Knuth-Bendix procedure applied to any finite \(V\)-presentation halts and thus the word problem is uniformly solvable for \(V\). As an application, it is shown (Theorem 4) that the semigroup variety defined by an identity of the form \(x_ 1 x_ 2\ldots x_ k yz= x_ 1 x_ 2\ldots x_ k zy\) has uniformly solvable word problem. Reviewer's remark: 1. The author attributes the result about halting of the Knuth-Bendix procedure for commutative semigroups to \textit{A. M. Ballantyne} and \textit{D. S. Lankford} [Comput. Math. Appl. 7, 159-165 (1981; Zbl 0449.20059)] but it should be mentioned that the same fact was independently discovered by \textit{R. H. Gilman} [J. Algebra 57, 544-554 (1979; Zbl 0403.20022)] and \textit{G. E. Peterson} and \textit{M. E. Stickel} [J. Assoc. Comput. Math. 28, 233-264 (1981; Zbl 0479.68092)]. 2. The main results of the paper have recently been generalized by \textit{M. Sapir} [Church-Rosser varieties of semigroups and associative algebras (preprint)].