Recognizable set

{{For|other uses of the word "recognizable"|Recognizable (disambiguation)}} {{Refimprove|date=June 2021}}

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 <math>N</math> be a monoid, a subset <math>S\subseteq N</math> is '''recognized by''' a monoid <math>M</math> if there exists a homomorphism <math>\phi</math> from <math>N</math> to <math>M</math> such that <math>S=\phi^{-1}(\phi(S))</math>, and '''recognizable''' if it is recognized by some finite monoid. This means that there exists a subset <math>T</math> of <math>M</math> (not necessarily a submonoid of <math>M</math>) such that the image of <math>S</math> is in <math>T</math> and the image of <math>N \setminus S</math> is in <math>M \setminus T</math>.

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

==Properties== A subset of <math>N</math> is recognizable if and only if its syntactic monoid is finite.

The set <math>\mathrm{REC}(N)</math> of recognizable subsets of <math>N</math> is closed under: * union * intersection * complement * right and left quotient

Mezei's theorem{{cn|date=June 2021}} states that if <math>M</math> is the product of the monoids <math>M_1, \dots, M_n</math>, then a subset of <math>M</math> is recognizable if and only if it is a finite union of subsets of the form <math>R_1 \times \cdots \times R_n</math>, where each <math>R_i</math> is a recognizable subset of <math>M_i</math>. For instance, the subset <math>\{1\}</math> of <math>\mathbb N</math> is rational and hence recognizable, since <math>\mathbb N</math> is a free monoid. It follows that the subset <math>S=\{(1,1)\}</math> of <math>\mathbb N^2</math> is recognizable.

McKnight's theorem{{cn|date=June 2021}} states that if <math>N</math> is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole <math>N</math> is always recognizable but it is not rational if <math>N</math> is infinitely generated.

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

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

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.<ref name="Campbell2007">{{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]</ref>

==See also==

* Rational set * Rational monoid

==References== {{Reflist}} *{{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

== Further reading == * {{cite book | last=Sakarovitch | first=Jacques | title=Elements of automata theory | others=Translated from the French by Reuben Thomas | location=Cambridge | publisher=Cambridge University Press | year=2009 | isbn=978-0-521-84425-3 | zbl=1188.68177 | at = Part II: The power of algebra }}

Category:Automata (computation)