Square-free words on partially commutative free monoids (Q1076163)

For an alphabet \(A\) let \(\theta \subseteq A\times A\) be a relation and \(\sim\) the congruence generated by the pairs \((ab,ba)\) such that \((a,b)\) is in \(\theta\). Define \(M(A,\theta)=A^*/\sim\) as the partially commutative free monoid relative to \(\theta\). The authors show that we can decide whether \(M(A,\theta)\) contains infinitely many square-free elements (those having no factorizations of the form \(m=rs^2t\) for \(s\neq 1)\).