Mikołaj Bojańczyk

## 7. Algebra for infinite words

Recall that a monoid consists of a universe together with a product operation which maps each one letter word to , and which is associative in the sense that the following diagram commutes where flattens a word of words into a word in the obvious way, while applies the product operation to every word in a word of words.

To define monoids for infinite words, we use the same definition, only is replaced by . This requires a new flattening operation which we illustrate on three examples: Note how in the second example above, the first infinite word causes the rest of the input to be ignored. This ignoring is a little bit of a hack, which could be avoided by either using two sorts (finite and infinite word), or by considering a richer notion of words which is closed under substitution, e.g. words where the positions form a countable well-ordering.

Summing up, -monoids are defined below.

Definition.  An -monoid consists of a unierse together with a product operation which is the identity on one letter words and which is associative in the sense that the following diagram commutes It is not difficult to see that , with flattening as the monoid operation, is an -monoid. Here is an example of an -monoid with a finite universe.

Example. This -monoid is going to recognize the -words over alphabet which contain infinitely many ‘s. The  universe is The product operation is defined as follows. To define with , we do the following. First, remove all letters from . If the result is empty, return .  If there is a letter of the form or , then return the or , whichever comes first in . Otherwise, if the result is an infinite word, then return if there are infinitely many ‘s and otherwise. Otherwise, return if there is at least one and otherwise. Homomorphism. Define a homomorphism of -monoids and to be a function between their universes which respects the structure of -morphisms in the sense that the following diagram commutes Compositional functions. As with normal monoids, instead of defining an associative product operation on a universe , it is sometimes easier to give a compositional function from an existing -monoid to , and get the -monoid structure on automatically from that. We describe this now. Suppose that is an -monoid and is a set. A function is called compositional if every words satisfy Lemma. If is compositional, then there is a multiplication operation on which turns it into an -monoid, and which turns into a homomorphism of -monoids.

Proof. Compositionality can be rephrased as saying that there is some function which makes the following diagram commute The above diagram then shows that is a homomorphism, assuming that yields a structure of an -monoid on , i.e. it is associative. Associativity is not difficult to show. 