Modularity in the Semilattice of ω-Words

A partial ordering of ω-words can be introduced with regard to whether an ω-word can be transformed into another by a Mealy machine. It is known that the poset of ω-words that is introduced by this ordering is a join-semilattice. The width of this join-semilattice has the power of continuum while the depth is at least . We have created a technique for proving that power-characteristic ω-words are incomparable. We use this technique to show that this join-semilattice is not modular. 1. Introduction Infinite words ( -words) provide a fertile ground of research and many classes of -words are known. While closure properties of some classes of -words have been studied extensively (see, e.g., [1–3]), we are interested in the general algebraic structure of -words. Mealy machines are a simple model of a word transforming automaton with the beneficial property of always transforming an -word into an -word. A partial ordering is defined on -words by the existence of a Mealy machine transforming one word into another (we write if such a machine exists). When both and are true, we say that ？？and？？ ？？are machine equivalent. A class of -words is called machine invariant if contains all possible transformations of its elements. Buls [4] has shown that machine invariant classes of -words form a completely distributive lattice. Belovs [5] showed that the poset of machine equivalent classes of -words is a join-semilattice and that the width of this join-semilattice has the power of continuum while the depth is at least . We show in this paper that this join-semilattice is not modular. 2. Preliminaries Let be a finite, nonempty set and the free monoid generated by . Call an alphabet, its elements letters, and the elements of ？？ finite words. The identity element of is called the empty word and is denoted by . Let be a word over a finite and non-empty alphabet . We denote the length of by . Similarly, the cardinality of is denoted by . The concatenation of the words is denoted by or simply . Define and for all ？？ . We say that (resp., ) is a prefix (resp., suffix) of . Denote by and the respective sets of prefixes and suffixes of . Let denote the set of integers : Call a total map an (indexed) -word of the alphabet . For any define and write The set of all -words over is denoted by . We say that is a prefix of , if there exists an integer such that . An -word is called ultimately periodic if there exist integers and such that for all . In this case is called preperiod and a period of . An ultimately periodic -word with a preperiod of zero is called periodic. We say a