Recognizable set

Let ${\displaystyle N}$  be a monoid, a subset ${\displaystyle S\subseteq N}$  is recognized by a monoid ${\displaystyle M}$  if there exists a homomorphism ${\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}$ .

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.

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:

• union
• intersection
• complement
• right and left quotient

Mezei's theorem^{[citation needed]} 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^{[citation needed]} states that if ${\displaystyle N}$  is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole ${\displaystyle N}$  is always recognizable but it is not rational if ${\displaystyle N}$  is infinitely generated.

Conversely, a rational subset may not be recognizable, even if ${\displaystyle N}$  is finitely generated. In fact, even 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} ,+)}$ . Indeed, if a homomorphism ${\displaystyle \phi }$  from ${\displaystyle \mathbb {Z} }$  to ${\displaystyle M}$  satisfies ${\displaystyle \{0\}=\phi ^{-1}(\phi (\{0\}))}$ , then ${\displaystyle \phi }$  is an injective function; hence ${\displaystyle M}$  is infinite.

Also, in general, ${\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 homomorphisms. I.e. if ${\displaystyle N}$  and ${\displaystyle M}$  are monoids and ${\displaystyle \phi :N\rightarrow M}$  is a homomorphism 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]

• Rational set
• Rational monoid

• Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Chapter 7: Automata". Discrete Algebraic Methods. Berlin/Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
• Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets

• Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. Part II: The power of algebra. ISBN 978-0-521-84425-3. Zbl 1188.68177.