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 homomorphism to a finite monoid.

Recognizable sets are useful in automata theory, formal languages and algebra.

Indeed, the term "recognizable" has a different meaning in computability theory.

is recognized by a monoid

if there exists a homomorphism

, and recognizable if it is recognized by some finite monoid.

This means that there exists a subset

be an alphabet: the set

are precisely the regular languages.

Indeed, such a language is recognized by the transition monoid of any automaton that recognizes the language.

are the ultimately periodic sets of integers.

is recognizable if and only if its syntactic monoid is finite.

is closed under: Mezei's theorem[citation needed] states that if

is the product of the monoids

is recognizable if and only if it is a finite union of subsets of the form

is a free monoid.

McKnight's theorem[citation needed] states that if

is finitely generated then its recognizable subsets are rational subsets.

This is not true in general, since the whole

is infinitely generated.

Conversely, a rational subset may not be recognizable, even if

In fact, even a finite subset of

For instance, the set

is an injective function; hence

is not closed under Kleene star.

For instance, the set

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.

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.