%0 Journal Article
%T Equivalence of Right Infinite Words
%A Liga Kulesa
%J Journal of Discrete Mathematics
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/219291
%X Closure properties of some classes of right infinite words have been studied extensively; we are interested in the general algebraic structure of right infinite words. We investigate preorder of morphism invariant classes and show that it is not a semilattice. 1. Introduction Right infinite words are ubiquitous in mathematics and theoretical computer science, therefore closure properties of some classes of right infinite words have been studied extensively. We consider simple function called morphism, which transforms right infinite word into a right infinite word. There are several kinds of properties that are typically studied about a class of words (a language), being finite or infinite. These include categorization, the study of the relationships between different languages; representation, different ways of describing the words belonging to a language; closure properties, the invariance of the language when certain transformations are applied; for example, Cobham [1] proved that the class of automatic sequences is closed under uniform transductions, that is, under the transducers where every transition outputs a string of the same length. In 1994, Dekking presented proof that finite state transduction of morphic sequence is still morphic, even if the transducer is nonuniform [2]. In [3] Belovs introduced partial ordering on right infinite words: if and only if there exists a Mealy machine that transforms to . He proved that this ordering is an upper semilattice, but it is not a lower semilattice. Similarly we can introduce partial ordering or right infinite words by transducers. We consider a poset of morphism invariant classes, which is simpler structure, therefore from an algebraic point of view it is surprising that it is neither an upper semilattice, nor a lower semilattice. Recently, Muchnik et al. [4] proved that transducer can be expressed as a composition of morphism and Mealy machine. Thus the ordering introduced by transducers is not an upper semilattice, nor a lower semilattice. In this sense the ordering defined by Mealy machine crucially differs. 2. Preliminaries Let be a finite nonempty set, and let be a free monoid generated by . The identity element of is called the empty word and is denoted by . A function is called morphism if and . The morphism is uniquely defined by its values on the elements. The morphism is called nonerasing if for all . It is called uniform if for all . It is called literal if for all . The morphism can also be applied to an infinite word as follows: It is possible to define morphism with more than one
%U http://www.hindawi.com/journals/jdm/2013/219291/