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.

This notion is different from the notion of recognizable language. Indeed, the term "recognizable" has a different meaning in computability theory.

Definition

Let N {\displaystyle N} be a monoid, a subset S ⊆ N {\displaystyle S\subseteq N} is recognized by a monoid M {\displaystyle M} if there exists a homomorphism ϕ {\displaystyle \phi } from N {\displaystyle N} to M {\displaystyle M} such that S = ϕ − 1 ( ϕ ( S ) ) {\displaystyle S=\phi ^{-1}(\phi (S))}, and recognizable if it is recognized by some finite monoid. This means that there exists a subset T {\displaystyle T} of M {\displaystyle M} (not necessarily a submonoid of M {\displaystyle M}) such that the image of S {\displaystyle S} is in T {\displaystyle T} and the image of N ∖ S {\displaystyle N\setminus S} is in M ∖ T {\displaystyle M\setminus T}.

Example

Let A {\displaystyle A} be an alphabet: the set A ∗ {\displaystyle A^{*}} of words over A {\displaystyle A} is a monoid, the free monoid on A {\displaystyle A}. The recognizable subsets of A ∗ {\displaystyle 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 {\displaystyle \mathbb {N} } are the ultimately periodic sets of integers.

Properties

A subset of N {\displaystyle N} is recognizable if and only if its syntactic monoid is finite.

The set R E C ( N ) {\displaystyle \mathrm {REC} (N)} of recognizable subsets of N {\displaystyle N} is closed under:

Mezei's theorem[citation needed] states that if M {\displaystyle M} is the product of the monoids M 1 , … , M n {\displaystyle M_{1},\dots ,M_{n}}, then a subset of M {\displaystyle M} is recognizable if and only if it is a finite union of subsets of the form R 1 × ⋯ × R n {\displaystyle R_{1}\times \cdots \times R_{n}}, where each R i {\displaystyle R_{i}} is a recognizable subset of M i {\displaystyle M_{i}}. For instance, the subset { 1 } {\displaystyle \{1\}} of N {\displaystyle \mathbb {N} } is rational and hence recognizable, since N {\displaystyle \mathbb {N} } is a free monoid. It follows that the subset S = { ( 1 , 1 ) } {\displaystyle S=\{(1,1)\}} of N 2 {\displaystyle \mathbb {N} ^{2}} is recognizable.

McKnight's theorem[citation needed] states that if N {\displaystyle N} is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole N {\displaystyle N} is always recognizable but it is not rational if N {\displaystyle N} is infinitely generated.

Conversely, a rational subset may not be recognizable, even if N {\displaystyle N} is finitely generated. In fact, even a finite subset of N {\displaystyle N} is not necessarily recognizable. For instance, the set { 0 } {\displaystyle \{0\}} is not a recognizable subset of ( Z , + ) {\displaystyle (\mathbb {Z} ,+)}. Indeed, if a homomorphism ϕ {\displaystyle \phi } from Z {\displaystyle \mathbb {Z} } to M {\displaystyle M} satisfies { 0 } = ϕ − 1 ( ϕ ( { 0 } ) ) {\displaystyle \{0\}=\phi ^{-1}(\phi (\{0\}))}, then ϕ {\displaystyle \phi } is an injective function; hence M {\displaystyle M} is infinite.

Also, in general, R E C ( N ) {\displaystyle \mathrm {REC} (N)} is not closed under Kleene star. For instance, the set S = { ( 1 , 1 ) } {\displaystyle S=\{(1,1)\}} is a recognizable subset of N 2 {\displaystyle \mathbb {N} ^{2}}, but S ∗ = { ( n , n ) ∣ n ∈ N } {\displaystyle 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 {\displaystyle N} and M {\displaystyle M} are monoids and ϕ : N → M {\displaystyle \phi :N\rightarrow M} is a homomorphism then if S ∈ R E C ( M ) {\displaystyle S\in \mathrm {REC} (M)} then ϕ − 1 ( S ) = { x ∣ ϕ ( x ) ∈ S } ∈ R E C ( N ) {\displaystyle \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.

Recognizable set

Definition

Example

Properties

See also

Further reading