Recognizable set explained

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

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

REC (N) of recognizable subsets of N is closed under:

• union
• intersection
• complement
• right and left quotient

Mezei's theorem states that if

M is the product of the monoids M _{1,} ... , 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} x … x R _{n} , where each R _{i} is a recognizable subset of M _{i} . For instance, the subset \{ 1 \} of N is rational and hence recognizable, since N is a free monoid. It follows that the subset S = \{( 1 , 1 )\} of 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 ( Z, + ) . Indeed, if a homomorphism \phi from Z to M satisfies \{ 0 \} = \phi ^{-1} (\phi(\{ 0 \})) , then \phi 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 N ^{2} , but S ^{*=\{(n,} n)\mid n\in 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 → M is a homomorphism then if S\in REC (M) then \phi ^{-1} (S) = \{x\mid \phi(x)\in S\}\in 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

• Rational set
• Rational monoid

References

• Book: Diekert . Volker . Kufleitner . Manfred . Rosenberg . Gerhard . Hertrampf . Ulrich . Discrete Algebraic Methods . 2016 . Walter de Gruyther GmbH . Berlin/Boston . 978-3-11-041332-8 . Chapter 7: Automata.

• Jean-Éric Pin, Mathematical Foundations of Automata Theory, Chapter IV: Recognisable and rational sets

Further reading

• Book: Sakarovitch, Jacques . Elements of automata theory . Translated from the French by Reuben Thomas . Cambridge . Cambridge University Press . 2009 . 978-0-521-84425-3 . 1188.68177 . Part II: The power of algebra .

Notes and References

1. Book: C.M. Campbell . M.R. Quick . E.F. Robertson . G.C. Smith. Groups St Andrews 2005 Volume 2. 2007. Cambridge University Press. 978-0-521-69470-4. 376. Groups and semigroups: connections and contrasts . John Meakin. preprint