Myhill-Nerode theorem for semigroups

Let $S$ be a semigroup. $X\subseteq S$ is recognizable if it is union of classes of a congruence $\chi$ such that $S/\chi$ is finite.

In the rest of the entry, ${\equiv }_X$ will be the syntactic congruence of $X$, and ${𝒩}_X$ its Nerode equivalence.

Theorem 1 (Myhill-Nerode theorem for semigroups)

Let $S$ be a semigroup and let $X\mathrm{\subseteq }S$. The following are equivalent.

1. $X$ is recognizable.

2. There exist a finite semigroup $T$ and a morphism $\varphi :S\to T$ such that $X={\varphi }^{-1}(\varphi (X))$.

3. The syntactic semigroup of $X$ is finite.

4. There exists an equivalence relation $\sim$ on $S$ such that

   • $S/\sim$ is finite and

   • $s_1\sim s_2$ implies $s_{1}t\sim s_{2}t$.

5. The quotient set $S/{𝒩}_X$ is finite.

Theorem 1 generalizes Myhill-Nerode theorem for languages to subsets of generic, not necessarily free, semigroups. In fact, as a consequence of Theorem 1, a language on a finite alphabet is recognizable in the sense given above if and only if it is recognizable by a DFA.

The equivalence of points 1, 2 and 3 is attributed to John Myhill, while the equivalence of points 1, 4 and 5 is attributed to Anil Nerode.

Proof of Theorem 1.

1 $\Rightarrow$ 2. Given a congruence $\chi$ such that and $X$ is union of classes of $\chi$, choose $T$ as the quotient semigroup $S/\chi$ and $\varphi$ as the natural homomorphism mapping $s$ to ${[s]}_{\chi }$.

2 $\Rightarrow$ 3. Given a morphism of semigroups $\varphi :S\to T$ with $T$ finite and $X={\varphi }^{-1}(\varphi (X))$, put $s\chi t$ iff $\varphi (s)=\varphi (t)$.

Since $\varphi$ is a morphism, $\chi$ is a congruence; moreover, $X={\varphi }^{-1}(\varphi (X))$ means that $X$ is union of classes of $\chi$-equivalence. By the maximality property of syntactic congruence, the number of classes of ${\equiv }_X$ does not exceed the number of classes of $\chi$, which in turn does not exceed the number of elements of $T$.

3 $\Rightarrow$ 1. Straightforward from $X$ being union of classes of ${\equiv }_X$.

3 $\Rightarrow$ 4. Straightforward from ${\equiv }_X$ satisfying the second requirement.

4 $\Rightarrow$ 5. Straightforward from the maximality property of Nerode equivalence.

5 $\Rightarrow$ 3. Let

$$S/{𝒩}_X=\{{[{\xi }_1]}_{{𝒩}_X},\mathrm{\dots },{[{\xi }_K]}_{{𝒩}_X}\}.$$ (1)

Since $s_1{\equiv }_X{s}_2$ iff $\mathrm{\ell }{s}_1{𝒩}_X\mathrm{\ell }{s}_2$ for every $\mathrm{\ell }\in S$, determining ${[s]}_{{\equiv }_X}$ is the same as determining ${[\mathrm{\ell }s]}_{{𝒩}_X}$ as $\mathrm{\ell }$ varies in $S$, plus the class ${\mathrm{[}s\mathrm{]}}_{{\mathrm{N}}_X}$. (This additional class takes into account the possibility that $s\notin {[\mathrm{\ell }s]}_{{𝒩}_X}$ for any $\mathrm{\ell }\in S$, which cannot be excluded a priori: do not forget that $S$ is not required to be a monoid.)

But since $s_1{𝒩}_X{s}_2$ implies $s_{1}t{𝒩}_X{s}_{2}t$, if ${[{\mathrm{\ell }}_1]}_{{𝒩}_X}={[{\mathrm{\ell }}_2]}_{{𝒩}_X}$ then ${[{\mathrm{\ell }}_{1}s]}_{{𝒩}_X}={[{\mathrm{\ell }}_{2}s]}_{{𝒩}_X}$ as well. To determine ${[s]}_{{\equiv }_X}$ it is thus sufficient to determine the ${[{\xi }_{i}s]}_{{𝒩}_X}$ for $1\le i\le K$, plus ${[s]}_{{𝒩}_X}$.

We can thus identify the class ${[s]}_{{\equiv }_X}$ with the sequence $({[{\xi }_{1}s]}_{{𝒩}_X},\mathrm{\dots },{[{\xi }_{K}s]}_{{𝒩}_X},{[s]}_{{𝒩}_X}).$ Then the number of classes of ${\equiv }_X$ cannot exceed that of $(K+1)$-ples of classes of ${𝒩}_X$, which is $K^{K+1}$. $\mathrm{\square }$

Title	Myhill-Nerode theorem for semigroups
Canonical name	MyhillNerodeTheoremForSemigroups
Date of creation	2014-05-14 17:29:14
Last modified on	2014-05-14 17:29:14
Owner	Ziosilvio (18733)
Last modified by	Ziosilvio (18733)
Numerical id	5
Author	Ziosilvio (18733)
Entry type	Theorem
Classification	msc 20M35
Classification	msc 68Q70
Defines	recognizable subset of a semigroup