On the invariance of small overlap hypotheses (Q810153)

For any semigroup presentation (X;R), words \(w_ 1\) and \(w_ 2\) are R- words if \((w_ 1,w_ 2)\) is in R. A non-empty subword (factor) p of an R-word w is called a piece if there is an R-word \(w'\) and (possibly empty) words on X, u, v, \(u'\), \(v'\) such that \(w=upv\), \(w'=u'pv'\) and either \(u\neq u'\) or \(v\neq v'\). For any positive integer n, (X;R) satisfies C(n) if no R-word can be written as a product of fewer than n pieces. Interest in these so-called small overlap hypotheses stems from a result of J. Remmers that any finite semigroup presentation satisfying C(3) has a solvable word problem [see the forthcoming book of the reviewer, `Techniques of Semigroup Theory' (Oxford University Press, 1992)]. The author shows that given a semigroup S defined by a C(n)-presentation, there is another presentation for S which fails to satisfy C(2). However, any presentation may be effectively reduced to an equivalent presentation which is free of trivial relators (relations of the form \(w=w)\) and avoidable letters (letters a, every occurrence of which in R has the form \((a=w)\), where w is a word on X-\(\{\) \(a\}\)). The main positive result concerns two presentations \((X_ 1;R_ 1)\) and \((X_ 2;R_ 2)\) for a semigroup Q which are C(2), free of trivial relators and of avoidable letters. Then for all \(n\geq 1\), \((X_ 1;R_ 1)\) satisfies C(n) if and only if \((X_ 2;R_ 2)\) does also.