Recognizable set

{{For|other uses of the word "recognizable"|Recognizable (disambiguation)}}

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$ 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$ .

Example

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.

Properties

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{{cn|date=June 2021}} 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{{cn|date=June 2021}} 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.{{cite book|editor1=C.M. Campbell |editor2=M.R. Quick |editor3=E.F. Robertson |editor4=G.C. Smith|title=Groups St Andrews 2005 Volume 2|year=2007|publisher=Cambridge University Press|isbn=978-0-521-69470-4|page=376|chapter=Groups and semigroups: connections and contrasts |author=John Meakin}} [http://www.math.unl.edu/~jmeakin2/groups%20and%20semigroups.pdf preprint]

References

{{cite book |last1=Diekert |first1=Volker |last2=Kufleitner |first2=Manfred |last3=Rosenberg |first3=Gerhard |last4=Hertrampf |first4=Ulrich |title=Discrete Algebraic Methods |date=2016 |publisher=Walter de Gruyther GmbH |location=Berlin/Boston |isbn=978-3-11-041332-8 | chapter = Chapter 7: Automata}}

Jean-Éric Pin, [http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf Mathematical Foundations of Automata Theory], Chapter IV: Recognisable and rational sets

Recognizable set

Definition

Example

Properties

See also

References

Further reading