# On pseudovarieties

Samuel Eilenberg, Marcel-Paul Schützenberger

► To cite this version:

Samuel Eilenberg, Marcel-Paul Schützenberger. On pseudovarieties. [Research Report] IRIA-RR-151, IRIA. 1975, pp.9. hal-04716102

HAL Id: hal-04716102

https://inria.hal.science/hal-04716102v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
RIA
laboria

ARCHIVES

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tel. 954.90.20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_2.png" /></figure>

On pseudovarieties

S. Eilenberg,
M.P. Schützenberger

Rapport de Recherche n°151
Décembre 1975
# ON PSEUDOVARIETIES

S. Eilenberg, M.P. Schützenberger

## RÉSUMÉ :

On modifie un théorème classique de G. Birkhoff en vue d'application à la théorie des automates finis.

## ABSTRACT :

One studies a variant of Birkhoff's theorem that has applications to finite automata.
ON PSEUDOVARIETIES

by

Samuel Eilenberg* and M. P. Schützenberger

Columbia University and IRIA

Dedicated to Garrett Birkhoff

Birkhoff's Theorem (1935) asserts that a family of algebras is an equational variety if and only if the family is closed under the operations of passing to subalgebras and quotient algebras and also under arbitrary direct products. The objective of this paper is to study what happens to this notion and the theorem above if one restricts ones attention to finite algebras only. This is motivated by applications to the theory of automata.

In the body of the paper we shall only consider monoids. At the end we shall remark how the results can be extended to more general species of algebras.

A family $V$ of finite monoids is called a *pseudovariety* if the following conditions hold

(1) If $S \in V$ and $T$ is a submonoid of $S$ then $T \in V$.

(2) If $S \in V$ and $T$ is a homomorphic image of $S$, then $T \in V$.

(3) If $S, T \in V$, then $S \times T \in V$.

<figure><img src="image_3.png" /></figure>

<footnote>*Research partially supported by NSF Grant DCR 72-03703 A01</footnote>
There are two points in which this definition differs from that of a (Birkhoffian) variety. One is that all the monoids in $V^{\mathbb{N}}$ are assumed to be *finite*. The second one (implied by the first) is that $V^{\mathbb{N}}$ is closed only under finite direct products. For example finite groups form a pseudovariety, but groups do not form a variety of monoids. Indeed, a sub-monoid of an (infinite) group need not be a group. It should however be noted that a finite monoid $S$ is a group if and only if, for all $n$ sufficiently large, and for all $x \in S$ the equation

$$x^{\overline{n}} = 1$$

holds, where $\overline{n}$ is the least common multiple of all the integers $1 < i \le n$. The objective of this paper is to show that such a phenomenon holds for all pseudovarieties.

Let $\Xi^*$ be the free monoid generated by the infinite sequence of letters $x_1, \dots, x_n, \dots$ and let $u, v \in \Xi^*$. We shall say that a monoid $S$ *satisfies* $(u, v)$ (or that the equation $u = v$ *holds* in $S$) if $u\varphi = v\varphi$ for every morphism $\varphi: \Xi^* \to S$. Finite monoids satisfying $(u, v)$ clearly from a pseudovariety that we shall denote by $V(u, v)$.

Given a sequence of pairs

$$(u_i, v_i) \in \Xi^* \times \Xi^*, \quad i \ge 1$$
we may consider two pseudovarieties

$$ V' = \bigcap_{i=1}^{\infty} V(u_i, v_i) $$

$$ V = \bigcup_{k=1}^{\infty} \bigcap_{i=k}^{\infty} V(u_i, v_i) $$

A (finite) monoid is in $V'$ if it satisfies all of the equations $u_i = v_i$, while it is in $V$ if it satisfies the equations $u_i = v_i$ for all $i$ sufficiently large. We shall say that $V'$ is *defined* by the equations $u_i = v_i$ and that $V$ is *ultimately defined* by the equations $u_i = v_i$.

Our main result is

**Theorem 1.** Each non-empty pseudovariety $V$ is ultimately defined by a sequence of equations.

We denote by $\Xi_n^*$ the submonoid of $\Xi^*$ generated by the letters $x_1, \dots, x_n$. In $\Xi_n^*$ we shall consider congruences. Such a congruence $\sim$ in $\Xi_n^*$ is said to be finite provided the quotient monoid $\Xi_n^*/\sim$ is finite. An important fact in the proof of Theorem 1 is

**Proposition 2.** A finite congruence $\sim$ in $\Xi_n^*$ is finitely generated, i.e., there exists a finite set $W \subseteq \Xi_n^* \times \Xi_n^*$ such that $u \sim v$ for all $(u,v) \in W$ and that $\sim$ is the smallest congruence with this property.

**Proof.** Since the congruence $\sim$ is finite, there exists an integer $k > 0$ such that each congruence class contains an
element $w$ with length $|w| < k$. Define

$$W = \{(u,v) | u \sim v, |u| \le k, |v| < k\}$$

Clearly $\text{card } W < (1+n)^{2k-1}$. Let $\equiv$ be the congruence generated by $W$. Clearly $u \equiv v$ implies $u \sim v$. To prove the opposite implication we need the following assertion

$$ (4) \quad \text{For each } w \in \Xi_n^*, \text{ there exists } w' \in \Xi_n^* \\ \text{such that } |w'| < k \text{ and } w \equiv w'. $$

We prove this by induction with respect to $|w|$. If $|w| < k$ there is nothing to prove since $(w,w) \in W$. Assume now that $\ell > k$ and that (4) holds for all $w$ with $|w| < \ell$. Consider $w \in \Xi_n^*$, $|w| = \ell$. Then $w = u\sigma$ with $|u| = \ell - 1$. Consequently $u \equiv u'$ for some $u'$ with $|u'| < k$. This implies $w \equiv u'\sigma$. Since $|u'\sigma| = k$, the definition of $W$ implies that $(u',w') \in W$ for some $w'$ such that $|w'| < k$. It follows that $w \equiv w'$ as required.

Now assume $u \sim v$. By (4) we have $u \equiv u'$ and $v \equiv v'$ with $|u'| < k, |v'| < k$. Since $u' \sim v'$ it follows that $(u',v') \in W$ and thus $u' \equiv v'$. Consequently $u \equiv v$. This proves that $\sim$ and $\equiv$ coincide and thus $\sim$ is finitely generated.

Having proved Proposition 2 we now proceed with the proof of Theorem 1.

We first construct a sequence

$$S_1, S_2, \dots, S_n, \dots$$
in $V$ with the following two properties

$$ \text{[<---]} \quad (5) \quad S_n \text{ is isomorphic to a quotient of } S_{n+1} $$

(6) If $S \in \mathcal{V}$, the $S$ is isomorphic to a quotient of $S_n$ for some $n \ge 1$.

To construct such a sequence, we write a sequence $T_1, T_2, \dots, T_n, \dots$ which contains all the elements of $V$ up to an isomorphism and then define $S_n = T_1 \times \dots \times T_n$.

For each $n \ge 1$ we define the congruence $\sim_n$ in $\Xi_n^*$ as follows: $u \sim_n v \iff u\phi = v\phi$ for all morphisms $\phi: \Xi_n^* \to S_n$. Consider the monoid $V_n = \Xi_n^*$. The following facts are clear

$\text{[<---]}$ (7) $V_n$ is isomorphic to a submonoid of some finite product of $S_n$ with itself.

This implies

$$ \text{[<---]} \quad (8) \quad V_n \in \mathcal{V} $$

Since $V_n$ is finite, Proposition 2 may be applied to the congruence $\sim_n$, yielding a finite set $W_n \subset \Xi_n^* \times \Xi_n^*$ such that $\sim_n$ is generated by $W_n$. Since $\Xi_n^*$ is a subset of $\Xi^*$ we obtain the countable set

$$ W = \bigcup_{n=1}^{\infty} W_n $$

in $\Xi^* \times \Xi^*$. We assert that $W$ ultimately defines $V$.
First assume that $S \in V$. Since $S$ is isomorphic to a quotient of $S_n$ for some $n \ge 1$, and since $S_n$ satisfies the equations $W_n$, it follows that $S$ satisfies the equations $W_n$. However $S_n$ is isomorphic to a quotient of $S_{n+k}$ for all $k \ge 0$ and thus $S$ also satisfies all the equations $W_{n+k}$ for all $k \ge 0$. Thus $S$ satisfies all but a finite number of equations in $W$.

Conversely assume that $S$ is a finite monoid satisfying all but a finite number of equations in $W$. Choose $n \ge 1$ with the following two properties

$$ \left[ \begin{array}{l} (9) \quad n \ge \text{card } S \\ (10) \quad S \text{ satisfies the equations } W_n \end{array} \right. $$

Let

$$ \varphi: \Xi_n^* \to S $$

be a surjective morphism. If $(u,v) \in W_n$ then $u\varphi = v\varphi$ since $S$ satisfies the equation $u = v$. Since the pairs $(u,v)$ in $W_n$ generate the congruence $\sim_n$, it follows that $u \sim_n v$ implies $u\varphi = v\varphi$. This implies that $\varphi$ admits a factorization

$$ \Xi_n^* \to V_n \xrightarrow{\psi} S $$

and that $\psi$ is a surjective morphism. Since $V_n \in V$ it follows that $S \in V$. This concludes the proof of Theorem 1.

A pseudovariety $V$ is said to be *equational* if it is
defined by a family of equations. This holds if and only if $V$ is the class of all finite monoids in some (Birkhoffian) variety of monoids. However two distinct varieties may yield the same pseudovariety.

An immediate consequence of Theorem 1 is

Corollary 3. Each pseudovariety is the union of an ascending sequence of equational pseudovarieties.

A pseudovariety $V$ is said to be **finitely generated**, if there exists a finite sequence of monoids $M_1, \dots, M_k$ such that $V$ is the smallest pseudovariety containing $M_1, \dots, M_k$. Replacing this sequence by the single monoid $M = M_1 \times \dots \times M_k$ shows that each finitely generated pseudovariety is generated by a single monoid $M$. A consequence of Corollary 3 is

Corollary 4. Each finitely generated pseudovariety is equational.

The remarks above lead in a natural way to consider the following two properties of a finite monoid $M$

(11) The variety generated by $M$ is defined by
a finite number of equations.

(12) The pseudovariety generated by $M$ is defined
by a finite number of equations.

The implication (11) ⇒ (12) is clear. Whether the
implication (12) ⇒ (11) holds is an open question. Oates and
Powell (1964) have shown that (11) holds for any finite group.
This easily implies (12) for any finite group. Perkins (1968)
has constructed a monoid containing six elements for which (11) fails. It is an open question whether (12) holds for this monoid. Perkins' monoid may be described as the monoid of all partial functions $f: \{0,1\} \rightarrow \{0,1\}$ but excluding the function which interchanges 0 and 1.

Although we have limited our attention to monoids, the entire development can be carried out for any algebraic theory based on a finite number of finitary operations. The role of $\Sigma^*$ and $\Sigma_n^*$ is then taken over by the free algebras generated by $x_1, \dots, x_n, \dots$ and by $x_1, \dots, x_n$. For $u \in \Sigma^*$ or $u \in \Sigma_n^*$ the integer $|u|$ must be defined in such a way that the proof of Proposition 2 remains valid. A fact needed in this proof is the finiteness of the sets $\{u | u \in \Sigma^*, |u| \le k\}$. This follows from the assumption that there is only a finite number of basic operations.

Pseudovarieties of monoids and of semigroups have applications in the theory of automata. The interested reader is referred to Eilenberg (1975), where the ultimate equations of many interesting pseudovarieties are derived.

In connection with pseudovarieties of semigroups the following interesting fact should be noted. Finite groups form a pseudovariety $G$ of monoids. However $G$ is not a pseudovariety of semigroups because it does not contain the empty semigroup. If however the empty semigroup is adjoined to $G$, a pseudovariety $G'$ of semigroups is obtained. Its
ultimate equations are obtained by replacing each equation
$x^{\overline{n}} = 1$ used to ultimately define $G$ by the pair of equations
$x^{\overline{n}} y = y = yx^{\overline{n}}$. These new equations ultimately define $G'$ as
a pseudovariety of semigroups and $G$ as a pseudovariety of
monoids. This method of eliminating the unit element is quite
general.

References

Garrett Birkhoff, On the structure of abstract algebras, Proc. Cambridge Phil. Soc., 31(1935), 433-454.

Samuel Eilenberg, *Automata, Languages and Machines, Volume B*, Academic Press, New York (1975).

Sheila Oates and M.B. Powell, Identical relations in finite groups,
J. of Algebra 1(1964), 11-39.

Peter Perkins, Bases for equational theories of semigroups,
J. of Algebra 11(1968), 298-314.