Zebra factorizations in free semigroups.

DOI10.1007/S00233-003-0030-ZMaRDI QIDQ1882653zbMATH OpenOpenAlexWikidataFDO

Authors Andrzej Ehrenfeucht, Tero Harju, Grzegorz Rozenberg

Publication date 1 October 2004

Published in Semigroup Forum (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00233-003-0030-z

zbMATH Keywords

free semigroupsseparative semigroupszebra factorizations

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Algebraic theory of languages and automata (68Q70)

Review text

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.

Recommendations

• Automatic subsemigroups of free products.
• Product-free sets in the free semigroup
• Factorizable semigroups
• scientific article; zbMATH DE number 3933342
• Two combinatorial properties of partitions of the free semigroup into finitely many parts

This page was built for publication: Zebra factorizations in free semigroups.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1882653)