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.
This notion is different from the notion of recognizable language. Indeed, the term "recognizable" has a different meaning in computability theory.
Definition
Let [math]\displaystyle{ N }[/math] be a monoid, a subset [math]\displaystyle{ S\subseteq N }[/math] is recognized by a monoid [math]\displaystyle{ M }[/math] if there exists a morphism [math]\displaystyle{ \phi }[/math] from [math]\displaystyle{ N }[/math] to [math]\displaystyle{ M }[/math] such that [math]\displaystyle{ S=\phi^{-1}(\phi(S)) }[/math], and recognizable if it is recognized by some finite monoid. This means that there exists a subset [math]\displaystyle{ T }[/math] of [math]\displaystyle{ M }[/math] (not necessarily a submonoid of [math]\displaystyle{ M }[/math]) such that the image of [math]\displaystyle{ S }[/math] is in [math]\displaystyle{ T }[/math] and the image of [math]\displaystyle{ N \setminus S }[/math] is in [math]\displaystyle{ M \setminus T }[/math].
Example
Let [math]\displaystyle{ A }[/math] be an alphabet: the set [math]\displaystyle{ A^* }[/math] of words over [math]\displaystyle{ A }[/math] is a monoid, the free monoid on [math]\displaystyle{ A }[/math]. The recognizable subsets of [math]\displaystyle{ A^* }[/math] 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 [math]\displaystyle{ \mathbb N }[/math] are the ultimately periodic sets of integers.
Properties
A subset of [math]\displaystyle{ N }[/math] is recognizable if and only if its syntactic monoid is finite.
The set [math]\displaystyle{ \mathrm{REC}(N) }[/math] of recognizable subsets of [math]\displaystyle{ N }[/math] is closed under:
- union
- intersection
- complement
- right and left quotient
Mezei's theorem[citation needed] states that if [math]\displaystyle{ M }[/math] is the product of the monoids [math]\displaystyle{ M_1, \dots, M_n }[/math], then a subset of [math]\displaystyle{ M }[/math] is recognizable if and only if it is a finite union of subsets of the form [math]\displaystyle{ R_1 \times \cdots \times R_n }[/math], where each [math]\displaystyle{ R_i }[/math] is a recognizable subset of [math]\displaystyle{ M_i }[/math]. For instance, the subset [math]\displaystyle{ \{1\} }[/math] of [math]\displaystyle{ \mathbb N }[/math] is rational and hence recognizable, since [math]\displaystyle{ \mathbb N }[/math] is a free monoid. It follows that the subset [math]\displaystyle{ S=\{(1,1)\} }[/math] of [math]\displaystyle{ \mathbb N^2 }[/math] is recognizable.
McKnight's theorem[citation needed] states that if [math]\displaystyle{ N }[/math] is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole [math]\displaystyle{ N }[/math] is always recognizable but it is not rational if [math]\displaystyle{ N }[/math] is infinitely generated.
Conversely, a rational subset may not be recognizable, even if [math]\displaystyle{ N }[/math] is finitely generated. In fact, even a finite subset of [math]\displaystyle{ N }[/math] is not necessarily recognizable. For instance, the set [math]\displaystyle{ \{0\} }[/math] is not a recognizable subset of [math]\displaystyle{ (\mathbb Z, +) }[/math]. Indeed, if a morphism [math]\displaystyle{ \phi }[/math] from [math]\displaystyle{ \mathbb Z }[/math] to [math]\displaystyle{ M }[/math] satisfies [math]\displaystyle{ \{0\}=\phi^{-1}(\phi(\{0\})) }[/math], then [math]\displaystyle{ \phi }[/math] is an injective function, hence [math]\displaystyle{ M }[/math] is infinite.
Also, in general, [math]\displaystyle{ \mathrm{REC}(N) }[/math] is not closed under Kleene star. For instance, the set [math]\displaystyle{ S=\{(1,1)\} }[/math] is a recognizable subset of [math]\displaystyle{ \mathbb N^2 }[/math], but [math]\displaystyle{ S^*=\{(n, n)\mid n\in \mathbb N\} }[/math] 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 [math]\displaystyle{ N }[/math] and [math]\displaystyle{ M }[/math] are monoids and [math]\displaystyle{ \phi:N\rightarrow M }[/math] is a morphism then if [math]\displaystyle{ S\in\mathrm{REC}(M) }[/math] then [math]\displaystyle{ \phi^{-1}(S)=\{x\mid \phi(x)\in S\}\in\mathrm{REC}(N) }[/math].
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
References
- ↑ John Meakin (2007). "Groups and semigroups: connections and contrasts". 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.
 |  |
