Zebra factorizations in free semigroups. (Q1882653): Difference between revisions

For any subsemigroup \(S\) of the free semigroup \(A^+\) on an alphabet \(A\), \(\Omega(S)\) comprises those words of \(S\) for which each prefix and suffix also belongs to \(S\). When nonempty, \(\Omega(S)\) is a free semigroup. In the special case where \(S\) is ``separative'' -- its complement \(S^c\) in \(A^+\) is also a (nonempty) semigroup -- it is proven that every word in \(A^+\) has a unique minimum-length factorization as a product of elements of \(\Omega(S)\) or \(\Omega(S^c)\): its shortest ``zebra factorization''. (Clearly, since every letter of the alphabet belongs to either \(S\) or \(S^c\) and thus to either \(\Omega(S)\) or \(\Omega(S^c)\), some factorization of this type always exists when \(S\) is separative.) It is shown that whenever the alphabet has at least two elements, there are uncountably many separative subsemigroups.