Recognizable set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For other uses of the word "recognizable", see 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 morphism 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 N be a monoid, a subset S\subseteq N is recognized by a monoid M if there exists a morphism \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[edit]

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[edit]

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 contains every finite subset of N and is closed under:

McKnight's theorem states that if N is finitely generated then its recognizable subsets are rational subsets. This is not true in general, i.e. \mathrm{REC}(N) is not closed under Kleene star. Let N=\mathbb N^2, the set S=\{(1,1)\} is finite, hence recognizable, but S^*=\{(i,i)\mid i\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 morphism. I.e. if N and M are monoids and \phi:N\rightarrow M is a morphism then if S\in\mathrm{REC}(M) then \phi^{-1}(S)=\{x\mid \phi(x)\in S\}\in\mathrm{REC}(M) .

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