The word problem for relatively free semigroups. (Q2491184): Difference between revisions

It is almost self-evident that the equational theory of a variety \(V\) of algebras is decidable if and only if the word problem is solvable in the relatively free algebra of countably infinite rank in \(V\), and thus if and only if it is solvable in each relatively free algebra of finite rank in \(V\). Now for any variety \(V\) of semigroups the word problem for the relatively free semigroup of rank 1 is clearly solvable. Thus for varieties of semigroups with undecidable equational theory, there arises the question of what upper bounds are possible for the ranks of the relatively free semigroups in \(V\) that do have decidable word problem. In the paper under review, the author constructs a series of finitely based semigroup varieties \(X_p\), \(p>1\), with the property that the word problem is decidable in the relatively free semigroup of rank \(m\) in \(X_p\) if and only if \(m<p\). -- The proof is based on Minsky machines.