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 submonoid that can be mapped in a certain sense to some finite monoid through some morphism. 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 submonoid 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/S is in M/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.

Rational sets are closed under inverse morphism. I.e. if N and M are monoid 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.