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.
Let N be a monoid, a subset S ⊆ N is recognized by a monoid M if there exists a morphism ϕ from N to M such that S = ϕ − 1 ( ϕ ( 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 ∖ S is in M ∖ T .
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 N are the ultimately periodic sets of integers.
A subset of N is recognizable if and only if its syntactic monoid is finite.
The set R E C ( N ) of recognizable subsets of N is closed under:
unionintersectioncomplementright and left quotientA finite subset of N is not necessarily recognizable. For instance, the set { 0 } is not a recognizable subset of Z .
Mezei's theorem states that if M is the product of the monoids M 1 , … , 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 × ⋯ × R n , where each R i is a recognizable subset of M i . For instance, the subset { 1 } of N is rational and hence recognizable, since N is a free monoid. It follows that the subset S = { ( 1 , 1 ) } of 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, i.e. R E C ( N ) is not closed under Kleene star. For instance, the set S = { ( 1 , 1 ) } is a recognizable subset of N 2 , but S ∗ = { ( n , n ) ∣ n ∈ 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 N and M are monoids and ϕ : N → M is a morphism then if S ∈ R E C ( M ) then ϕ − 1 ( S ) = { x ∣ ϕ ( x ) ∈ S } ∈ R E C ( 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.
