Mikołaj Bojańczyk

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.

## Leave a Reply