zbMATH — the first resource for mathematics

Distributivity in the semilattice of \(\omega\)-words. (English) Zbl 1217.68167
Chajda, I. (ed.) et al., Proceedings of the 79th workshop on general algebra “79. Arbeitstagung Allgemeine Algebra”, 25th conference of young algebraists, Palacký University Olomouc, Olomouc, Czech Republic, February 12–14, 2010. Klagenfurt: Verlag Johannes Heyn (ISBN 978-3-7084-0407-3/pbk). Contributions to General Algebra 19, 13-21 (2010).
Summary: A partial ordering of \(\omega\)-words can be introduced with regard to whether an \(\omega\)-word can be transformed into another by a Mealy machine. It is known that the poset of \(\omega\)-words that is introduced by this ordering is a join-semilattice of continuum width and at least denumerable depth. We show that this join-semilattice is not distributive.
For the entire collection see [Zbl 1201.08001].

68R15 Combinatorics on words
06A12 Semilattices
68Q45 Formal languages and automata