# 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 ${\displaystyle N}$ be a monoid, a subset ${\displaystyle S\subseteq N}$ is recognized by a monoid ${\displaystyle M}$ if there exists a morphism ${\displaystyle \phi }$ from ${\displaystyle N}$ to ${\displaystyle M}$ such that ${\displaystyle S=\phi ^{-1}(\phi (S))}$, and recognizable if it is recognized by some finite monoid. This means that there exists a subset ${\displaystyle T}$ of ${\displaystyle M}$ (not necessarily a submonoid of ${\displaystyle M}$) such that the image of ${\displaystyle S}$ is in ${\displaystyle T}$ and the image of ${\displaystyle N\setminus S}$ is in ${\displaystyle M\setminus T}$.

## Example

Let ${\displaystyle A}$ be an alphabet: the set ${\displaystyle A^{*}}$ of words over ${\displaystyle A}$ is a monoid, the free monoid on ${\displaystyle A}$. The recognizable subsets of ${\displaystyle 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 ${\displaystyle \mathbb {N} }$ are the ultimately periodic sets of integers.

## Properties

A subset of ${\displaystyle N}$ is recognizable if and only if its syntactic monoid is finite.

The set ${\displaystyle \mathrm {REC} (N)}$ of recognizable subsets of ${\displaystyle N}$ is closed under:

A finite subset of ${\displaystyle N}$ is not necessarily recognizable. For instance, the set ${\displaystyle \{0\}}$ is not a recognizable subset of ${\displaystyle \mathbb {Z} }$.

Mezei's theorem states that if ${\displaystyle M}$ is the product of the monoids ${\displaystyle M_{1},\dots ,M_{n}}$, then a subset of ${\displaystyle M}$ is recognizable if and only if it is a finite union of subsets of the form ${\displaystyle R_{1}\times \cdots \times R_{n}}$, where each ${\displaystyle R_{i}}$ is a recognizable subset of ${\displaystyle M_{i}}$. For instance, the subset ${\displaystyle \{1\}}$ of ${\displaystyle \mathbb {N} }$ is rational and hence recognizable, since ${\displaystyle \mathbb {N} }$ is a free monoid. It follows that the subset ${\displaystyle S=\{(1,1)\}}$ of ${\displaystyle \mathbb {N} ^{2}}$ is recognizable.

McKnight's theorem states that if ${\displaystyle N}$ is finitely generated then its recognizable subsets are rational subsets. This is not true in general, i.e. ${\displaystyle \mathrm {REC} (N)}$ is not closed under Kleene star. For instance, the set ${\displaystyle S=\{(1,1)\}}$ is a recognizable subset of ${\displaystyle \mathbb {N} ^{2}}$, but ${\displaystyle 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 morphisms. I.e. if ${\displaystyle N}$ and ${\displaystyle M}$ are monoids and ${\displaystyle \phi :N\rightarrow M}$ is a morphism then if ${\displaystyle S\in \mathrm {REC} (M)}$ then ${\displaystyle \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.[1]