In computer science, more precisely in automata theory, a recognizable set of a monoid is a submonoid that can be mapped in a certain sense to some finite monoid through some morphism. Recognizable sets are useful in automata theory, formal languages and algebra.
Let be a monoid, a submonoid is recognized by a monoid if there exists a morphism from to such that , and recognizable if it is recognized by some finite monoid. This means that there exists a subset of (not necessarily a submonoid of ) such that the image of is in and the image of is in .
Let be an alphabet: the set of words over is a monoid, the free monoid on . The recognizable subsets of 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 are the ultimately periodic sets of integers.
A subset of is recognizable if and only if its syntactic monoid is finite.
The set of recognizable subsets of contains every finite subset of and is closed under:
McKnight's theorem states that if is finitely generated then its recognizable subsets are rational subsets. This is not true in general, i.e. is not closed under Kleene star. Let , the set is finite, hence recognizable, but is not recognizable. Indeed its syntactic monoid is infinite.
The intersection of a rational subset and of a recognizable subset is rational.
Rational sets are closed under inverse morphism. I.e. if and are monoid and is a morphism then if then .
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.
- Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 8. ISBN 3-7643-3719-2. Zbl 0816.68086.
- Jean-Eric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets