# Recognizable set

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

In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some morphism 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 morphism $\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$ contains every finite subset of $N$ and is closed under:

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.

Recognizable sets are closed under inverse morphism. I.e. if $N$ and $M$ are monoids 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)$.

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.[1]