Recognizable set
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism 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.
In computer science, more precisely in automata theory, a recognizable set of a monoid is a subset that can be distinguished by some homomorphism 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 homomorphism \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 is closed under: union intersection complement right and left quotient Mezei's theorem states that if M is the product of the monoids M_1, \dots, M_n , then a subset of M is recognizable if and only if it is a finite union of subsets of the form R_1 \times \cdots \times R_n , where each R_i is a recognizable subset of M_i . For instance, the subset \{1\} of \mathbb N is rational and hence recognizable, since \mathbb N is a free monoid. It follows that the subset S=\{(1,1)\} of \mathbb N^2 is recognizable. McKnight's theorem states that if N is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole N is always recognizable but it is not rational if N is infinitely generated. Conversely, a rational subset may not be recognizable, even if N is finitely generated. In fact, even a finite subset of N is not necessarily recognizable. For instance, the set \{0\} is not a recognizable subset of (\mathbb Z, +) . Indeed, if a homomorphism \phi from \mathbb Z to M satisfies \{0\}=\phi^{-1}(\phi(\{0\})) , then \phi is an injective function; hence M is infinite. Also, in general, \mathrm{REC}(N) is not closed under Kleene star. For instance, the set S=\{(1,1)\} is a recognizable subset of \mathbb N^2 , but 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 N and M are monoids and \phi:N\rightarrow M is a homomorphism then if S\in\mathrm{REC}(M) then \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.
See also
Rational set Rational monoid
References
Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets
Text derived from https://en.wikipedia.org/w/index.php?oldid=1211319383 under CC BY-SA 4.0; modifications have been made.