Encyclopedia

Recognizable set

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated March 1, 2024

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.

01Definition

Let $N$ be a monoid, a subset $S\subseteq N$ is recognized by a monoid $M$ if there exists a homomorphism $\phi$ from $N$ to $M$ such that $S=\phi ^{-1}(\phi (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\setminus S$ is in $M\setminus T$ .

02Example

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 $\mathbb {N}$ are the ultimately periodic sets of integers.

03Properties

A subset of $N$ is recognizable if and only if its syntactic monoid is finite.

The set $\mathrm {REC} (N)$ of recognizable subsets of $N$ is closed under:

Mezei's theorem states that if $M$ is the product of the monoids $M_{1},\dots ,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}\times \cdots \times R_{n}$ , where each $R_{i}$ is a recognizable subset of $M_{i}$ . For instance, the subset $\{1\}$ of $\mathbb {N}$ is rational and hence recognizable, since $\mathbb {N}$ is a free monoid. It follows that the subset $S=\{(1,1)\}$ of $\mathbb {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, since the whole $N$ is always recognizable but it is not rational if $N$ is infinitely generated.

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

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

Watch videos about Recognizable setExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Recognizable set”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Recognizable set

01Definition

02Example

03Properties

Sources and credits

Related topics

Rational set

Rational monoid