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 morphism to a finite monoid. Recognizable sets are useful in automata theory, formal languages and algebra.

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

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:

• union
• intersection
• complement
• right and left quotient

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, 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 morphism ${\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 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]

See also

• Rational set
• Rational monoid

References

1. John Meakin (2007). "Groups and semigroups: connections and contrasts". In C.M. Campbell; M.R. Quick; E.F. Robertson; G.C. Smith (eds.). Groups St Andrews 2005 Volume 2. Cambridge University Press. p. 376. ISBN 978-0-521-69470-4. preprint

• 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-Eric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets

Further reading

• 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.