7. Algebra for infinite words

Mikołaj Bojańczyk

zajęcia / courses

Recall that a monoid consists of a universe $M$ together with a product operation

$\pi : M^* \to M$

which maps each one letter word $m$ to $m$ , and which is associative in the sense that the following diagram commutes

$\xymatrix{(M^*)^* \ar[r]^{flat} \ar[d]_{\pi^*} & M^* \ar[d]^\pi \\ M^* \ar[r]_\pi & M}$

where $flat$ flattens a word of words into a word in the obvious way, while $\pi^*$ 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 $\infty$ . This requires a new flattening operation

$\mathrm{flat} : (M^\infty)^\infty \to M^\infty$

which we illustrate on three examples:

$\begin{eqnarray*} (aba) (\epsilon) (aa) (b) & \quad \mapsto \quad & abaaab \\ (aaa \cdots) (bbb \cdots) & \quad \mapsto \quad & aaa \cdots \\ (\epsilon) (\epsilon) (\epsilon) & \quad \mapsto \quad & \epsilon \end{eqnarray*}$

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, $\infty$ -monoids are defined below.

Definition. An $\infty$ -monoid consists of a unierse $M$ together with a product operation

$\pi : M^\infty \to M$

which is the identity on one letter words and which is associative in the sense that the following diagram commutes

$\xymatrix{(M^\infty)^\infty \ar[r]^{flat} \ar[d]_{\pi^\infty} & M^\infty \ar[d]^\pi \\ M^\infty \ar[r]_\pi & M}$

It is not difficult to see that $\Sigma^\infty$ , with flattening as the monoid operation, is an $\infty$ -monoid. Here is an example of an $\infty$ -monoid with a finite universe.

Example. This $\infty$ -monoid is going to recognize the $\infty$ -words over alphabet $\set{a,b}$ which contain infinitely many $a$ ‘s. The universe is

$M = \set{\epsilon, a, b, a^\omega, b^\omega}$

The product operation is defined as follows. To define $\pi(w)$ with $w \in M^\infty$ , we do the following. First, remove all $\epsilon$ letters from $w$ . If the result is empty, return $\epsilon$ . If there is a letter of the form $a^\omega$ or $b^\omega$ , then return the $a^\omega$ or $b^\omega$ , whichever comes first in $w$ . Otherwise, if the result is an infinite word, then return $a^\omega$ if there are infinitely many $a$ ‘s and $b^\omega$ otherwise. Otherwise, return $a$ if there is at least one $a$ and $b$ otherwise. $\Box$

Homomorphism. Define a homomorphism of $\infty$ -monoids $M$ and $N$ to be a function $h$ between their universes which respects the structure of $\infty$ -morphisms in the sense that the following diagram commutes

$\xymatrix{M^\infty \ar[r]^{h^\infty} \ar[d]_{\pi_M} & N^\infty \ar[d]^{\pi_N} \\ M \ar[r]^h & N}$

Compositional functions. As with normal monoids, instead of defining an associative product operation on a universe $N$ , it is sometimes easier to give a compositional function from an existing $\infty$ -monoid to $N$ , and get the $\infty$ -monoid structure on $N$ automatically from that. We describe this now. Suppose that $M$ is an $\infty$ -monoid and $N$ is a set. A function

$h : M \to N$

is called compositional if every words $w,v \in M^\infty$ satisfy

$h^\infty(w) = h^\infty(v) \qquad \text{implies} \qquad h(\pi(w)) = h(\pi(v))$

Lemma. If $h : M \to N$ is compositional, then there is a multiplication operation on $N$ which turns it into an $\infty$ -monoid, and which turns $h$ into a homomorphism of $\infty$ -monoids.

Proof. Compositionality can be rephrased as saying that there is some function $\sigma$ which makes the following diagram commute

$\xymatrix{M^\infty \ar[r]^{h^\infty} \ar[d]_{\pi} & N^\infty \ar[d]^\sigma \\ M \ar[r]^h & N}$

The above diagram then shows that $h$ is a homomorphism, assuming that $\sigma$ yields a structure of an $\infty$ -monoid on $N$ , i.e. it is associative. Associativity is not difficult to show. $\Box$

zajęcia / courses

7. Algebra for infinite words

Leave a Reply