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