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.
≈ 4 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
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
edit edit sourceLet N be a monoid, a subset S⊆N is recognized by a monoid M if there exists a homomorphism ϕ from N to M such that S=ϕ−1(ϕ(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∖S is in M∖T.
Example
edit edit sourceLet 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 ℕ are the ultimately periodic sets of integers.
Properties
edit edit sourceA subset of N is recognizable if and only if its syntactic monoid is finite.
The set REC(N) of recognizable subsets of N is closed under:
Mezei's theorem[citation needed] states that if M is the product of the monoids M1,…,Mn, then a subset of M is recognizable if and only if it is a finite union of subsets of the form R1×⋯×Rn, where each Ri is a recognizable subset of Mi. For instance, the subset {1} of ℕ is rational and hence recognizable, since ℕ is a free monoid. It follows that the subset S={(1,1)} of ℕ2 is recognizable.
McKnight's theorem[citation needed] 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 (ℤ,+). Indeed, if a homomorphism ϕ from ℤ to M satisfies {0}=ϕ−1(ϕ({0})), then ϕ is an injective function; hence M is infinite.
Also, in general, REC(N) is not closed under Kleene star. For instance, the set S={(1,1)} is a recognizable subset of ℕ2, but S∗={(n,n)∣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 ϕ:N→M is a homomorphism then if S∈REC(M) then ϕ−1(S)={x∣ϕ(x)∈S}∈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.[1]
See also
edit edit sourceReferences
edit edit source- ^ John Meakin (2007). "Groups and semigroups: connections and contrasts". In C.M. Campbell; M.R. Quick; E.F. Robertson; G.C. Smith (eds.). Groups St Andrews 2005 Volume 2. Cambridge University Press. p. 376. ISBN 978-0-521-69470-4. preprint Wikipedia revision 1211319383, retrieved 2026-11-18
- Diekert, Volker; Kufleitner, Manfred; Rosenberg, Gerhard; Hertrampf, Ulrich (2016). "Chapter 7: Automata". Discrete Algebraic Methods. Berlin/Boston: Walter de Gruyther GmbH. ISBN 978-3-11-041332-8.
- Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets
Further reading
edit edit source- Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge: Cambridge University Press. Part II: The power of algebra. ISBN 978-0-521-84425-3. Zbl 1188.68177.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1211319383 under CC BY-SA 4.0; modifications have been made.