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