# Recognizable set

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism to a finite monoid. Recognizable sets 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 subset $S\subseteq N$ is recognized by a monoid $M$ if there exists a homomorphism $\phi$ from $N$ to $M$ such that $S=\phi ^{-1}(\phi (S))$, and recognizable if it is recognized by some finite monoid. 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\setminus S$ is in $M\setminus T$.

## Example

Let $A$ be an alphabet: the set $A^{*}$ of words over $A$ is a monoid, the free monoid on $A$. The recognizable subsets of $A^{*}$ are precisely the regular languages. Indeed, such a 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.

## Properties

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$ is closed under:
* union
* intersection
* complement
* right and left quotient
Mezei's theorem states that if $M$ is the product of the monoids $M_{1},\dots ,M_{n}$, then a subset of $M$ is recognizable if and only if it is a finite union of subsets of the form $R_{1}\times \cdots \times R_{n}$, where each $R_{i}$ is a recognizable subset of $M_{i}$. For instance, the subset $\{1\}$ of $\mathbb {N}$ is rational and hence recognizable, since $\mathbb {N}$ is a free monoid. It follows that the subset $S=\{(1,1)\}$ of $\mathbb {N} ^{2}$ is recognizable.
McKnight's theorem states that if $N$ is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole $N$ is always recognizable but it is not rational if $N$ is infinitely generated.
Conversely, a rational subset may not be recognizable, even if $N$ is finitely generated.
In fact, even a finite subset of $N$ is not necessarily recognizable. For instance, the set $\{0\}$ is not a recognizable subset of $(\mathbb {Z} ,+)$. Indeed, if a homomorphism $\phi$ from $\mathbb {Z}$ to $M$ satisfies $\{0\}=\phi ^{-1}(\phi (\{0\}))$, then $\phi$ is an injective function; hence $M$ is infinite.
Also, in general, $\mathrm {REC} (N)$ is not closed under Kleene star. For instance, the set $S=\{(1,1)\}$ is a recognizable subset of $\mathbb {N} ^{2}$, but $S^{*}=\{(n,n)\mid n\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.
Recognizable sets are closed under inverse of homomorphisms. I.e. if $N$ and $M$ are monoids and $\phi :N\rightarrow M$ is a homomorphism then if $S\in \mathrm {REC} (M)$ then $\phi ^{-1}(S)=\{x\mid \phi (x)\in S\}\in \mathrm {REC} (N)$.
For finite groups the following result of Anissimov and Seifert is well known: a subgroup H of a finitely generated group G is recognizable if and only if H has finite index in G. In contrast, H is rational if and only if H is finitely generated.