en>Bearcat: /* External links */

2012-11-11T21:32:31Z

External links

New page

In [[computer science]], more precisely in automata theory, a '''rational set''' of a [[monoid]] is an element of the minimal class of subsets of this monoid which contains all finite subsets and is closed under [[set union|union]], product and [[Kleene star]]. Rational sets are useful in [[automata theory]], [[formal language]]s and [[algebra]].

==Definition==
Let <math>N</math> be a [[monoid]]. The set <math>\mathrm{RAT}(N)</math> of rational subsets of <math>N</math> is the smallest set that contains every finite set and is closed under
* [[set union|union]]: if <math>A,B\in \mathrm{RAT}(N)</math> then <math>A\cup B\in \mathrm{RAT}(N)</math>
* product: if <math>A,B\in \mathrm{RAT}(N)</math> then <math>A\times B=\{a\times b\mid a\in A,b\in B\}\in\mathrm{RAT}(N)</math>
* [[Kleene star]] if <math>A\in \mathrm{RAT}(N)</math> then <math>A^*=\bigcup_{i=1}^\infty A^i \in\mathrm{RAT}(N)</math> where <math>A^1=A</math> and <math>A^{n+1}=A^n\times A</math>.

This means that any rational subset of <math>N</math> can be obtained by taking a finite number of finite subsets of <math>N</math> and applying the union, product and Kleene star operations a finite number of times.

In general the rational subsets of a monoid do not form a submonoid of this monoid.

==Example==
Let <math>A</math> be an [[alphabet (computer science)|alphabet]], the set <math>A^*</math> of words over <math>A</math> is a monoid. The rational subset of <math>A^*</math> are precisely the [[regular language]]s. Indeed this language may be defined by a finite [[regular expression]].

The rational subsets of <math>\mathbb N</math> are the ultimately periodic sets of integers. More generally, the rational subsets of <math>\mathbb N^k</math> are the [[semilinear set]]s.<ref>[http://www.liafa.jussieu.fr/~jep/MPRI/MPRI.html Mathematical Foundations of Automata Theory]</ref>

== Property ==
[[McKnight's theorem]] states that if <math>N</math> is finitely generated then its [[recognizable set|recognizable subset]] are rational sets.
This is not true in general, i.e. <math>\mathrm{RAT}(N)</math> is not closed under [[intersection (set theory)|complement]]. Let <math>N=\{a\}^*\times\{b,c\}^*</math>, the sets <math>U=\{(a^n,b^nc^m)\mid n,m\in\mathbb N\}</math> and <math>V=\{(a^n,b^mc^n)\mid n,m\in\mathbb N\}</math> are recognizable but <math>W=U\cap V=\{(a^n,b^nc^n)\mid n\in\mathbb N\}</math> is not because its projection to the second element <math>\{b^nm^n\mid n\in\mathbb N\}</math> is not rational.

The intersection of a rational subset and of a recognizable subset is rational.

Rational sets are closed under morphism: given <math>N</math> and <math>M</math> two monoids and <math>\phi:N\rightarrow M</math> a morphism, if <math>S\in\mathrm{RAT}(N)</math> then <math>\phi(S)=\{\phi(x)\mid x\in S\}\in\mathrm{RAT}(M) </math>.

==See also==

* [[Recognizable set]]

==References==
*{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page=79 }}
*[http://www.liafa.jussieu.fr/~jep/PDF/MPRI/MPRI.pdf Mathematical Foundations of Automata Theory]
*[http://genome.univ-mlv.fr/~berstel/Mps/Travaux/A/1969-3RationalSetsCommutativeMonoids.pdf Rational Sets in Commutative Monoids]
{{reflist}}

[[Category:Automata theory]]

Mean-periodic function - Revision history

en>Bearcat: /* External links */