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

Let   be a monoid, a subset   is recognized by a monoid   if there exists a homomorphism   from   to   such that  , and recognizable if it is recognized by some finite monoid. This means that there exists a subset   of   (not necessarily a submonoid of  ) such that the image of   is in   and the image of   is in  .

Example

edit

Let   be an alphabet: the set   of words over   is a monoid, the free monoid on  . The recognizable subsets of   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

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

The set   of recognizable subsets of   is closed under:

Mezei's theorem[citation needed] states that if   is the product of the monoids  , then a subset of   is recognizable if and only if it is a finite union of subsets of the form  , where each   is a recognizable subset of  . For instance, the subset   of   is rational and hence recognizable, since   is a free monoid. It follows that the subset   of   is recognizable.

McKnight's theorem[citation needed] states that if   is finitely generated then its recognizable subsets are rational subsets. This is not true in general, since the whole   is always recognizable but it is not rational if   is infinitely generated.

Conversely, a rational subset may not be recognizable, even if   is finitely generated. In fact, even a finite subset of   is not necessarily recognizable. For instance, the set   is not a recognizable subset of  . Indeed, if a homomorphism   from   to   satisfies  , then   is an injective function; hence   is infinite.

Also, in general,   is not closed under Kleene star. For instance, the set   is a recognizable subset of  , but   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   and   are monoids and   is a homomorphism then if   then  .

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

References

edit
  1. ^ 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

Further reading

edit
  • 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.