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 be a monoid, a subset 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 such that the image of is in and the image of is in.

Example

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.

Properties

A subset of is recognizable if and only if its syntactic monoid is finite.
The set of recognizable subsets of is closed under:
Mezei's theorem states that if is the product of the monoids, then a subset of is recognizable if and only if it is a finite union of subsets of the form, where each is a recognizable subset of. For instance, the subset of is rational and hence recognizable, since is a free monoid. It follows that the subset of is recognizable.
McKnight's theorem states that if is finitely generated then its recognizable subsets are rational subsets.
This is not true in general, since the whole is always recognizable but it is not rational if is infinitely generated.
Conversely, a rational subset may not be recognizable, even if is finitely generated.
In fact, even a finite subset of is not necessarily recognizable. For instance, the set is not a recognizable subset of. Indeed, if a morphism from to satisfies, then is an injective function, hence is infinite.
Also, in general, is not closed under Kleene star. For instance, the set is a recognizable subset of, but 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 and are monoids 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.