Recognizable set

For other uses of the word "recognizable", see Recognizable (disambiguation)

In computer science, more precisely in automata theory, a recognizable set is a class of subsets of monoids that are useful in automata theory, formal languages and algebra.

This notion is different from the notion of recognizable language. Indeed, the term "recognizable" has a different meaning in computability theory.

Definition

Let $N$ be a monoid, a submonoid $S\subseteq N$ is recognizable if there exists a morphism $\phi$ from $N$ to a finite monoid $M$ such that $S=\phi ^{-1}(\phi (S))$. This means that there exists a subset $T$ of $M$ (not necessarily a submonoid of $M$) such that the image of $S$ is in $T$ and the image of $N/S$ is in $M/T$.

Example

Let $A$ be an alphabet, the set $A^{*}$ of words over $A$ is a monoid. The recognizable subset of $A^{*}$ are precisely the regular languages. Indeed this language is recognized by the transition monoid of any automaton that recognizes the language.

The recognizable subsets of $\mathbb {N}$ are the ultimately periodic sets of integers.

Property

A subset of $N$ is recognizable if and only if its syntactic monoid is finite.

The set $\mathrm {REC} (N)$ of recognizable subsets of $N$ contains every finite subset of $N$ and is closed under:

• union
• intersection
• complement
• right and left quotient

McKnight's theorem states that if $N$ is finitely generated then its recognizable subsets are rational subsets. This is not true in general, i.e. $\mathrm {REC} (N)$ is not closed under Kleene star. Let $N=\mathbb {N} ^{2}$, the set $S=\{(1,1)\}$ is finite, hence recognizable, but $S^{*}=\{(i,i)\mid i\in \mathbb {N} \}$ is not recognizable. Indeed its syntactic monoid is infinite.

The intersection of a rational subset and of a recognizable subset is rational.

Rational sets are closed under inverse morphism. I.e. if $N$ and $M$ are monoid and $\phi :N\rightarrow M$ is a morphism then if $S\in \mathrm {REC} (M)$ then $\phi ^{-1}(S)=\{x\mid \phi (x)\in S\}\in \mathrm {REC} (M)$.

References

• Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 79. ISBN 3-7643-3719-2. Zbl 0816.68086.
• [Mathematical Foundations of Automata Theory]