Ne pas confondre avec l’ensemble desnombres rationnels

Eninformatique théorique, plus particulièrement enthéorie des automates, unensemble rationnel dans unmonoïde est un élément de la plus petite famille de sous-ensembles de ce monoïde qui contient toutes les parties finies et qui est fermée parunion, produit etétoile de Kleene. Les ensembles rationnels interviennent enthéorie des automates, enthéorie des langages formels et enalgèbre.

La notion d'ensemble rationnel étend la notion delangage rationnel ou régulier en tant qu'ensemble défini par uneexpression régulière à des monoïdes qui ne sont pas nécessairement libres.

Soit${\displaystyle N}$ unmonoïde avecélément neutre${\displaystyle e}$. L'ensemble${\displaystyle \mathrm{R}\mathrm{a}\mathrm{t}(N)}$ dessous-ensembles rationnels ouparties rationnelles de${\displaystyle N}$ est la plus petite famille de parties de${\displaystyle N}$ contenant les parties finie et fermé sous les opérations suivantes :

• union : si${\displaystyle A,B\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$ alors${\displaystyle A\cup B\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$
• produit: si${\displaystyle A,B\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$ alors${\displaystyle AB=\{ab\mid a\in A,b\in B\}\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$
• étoile de Kleene : si${\displaystyle A\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$ alors

${\displaystyle A^{\ast }=\bigcup _{i=0}^{\mathrm{\infty }}{A}^i\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$

où${\displaystyle A^0=\{e\}}$ est le singleton contenant l'élément d'identité, et${\displaystyle A^{n+1}=A^{n}A}$ .

En d'autres termes, tout sous-ensemble rationnel de${\displaystyle N}$ est obtenu en prenant un nombre fini de sous-ensembles finis de${\displaystyle N}$ et en appliquant les opérations d'union, de produit et d'étoile de Kleene un nombre fini de fois.

En général, un sous-ensemble rationnel d'un monoïde n'est pas un sous-monoïde.

Soit${\displaystyle A}$ un alphabet. L'ensemble${\displaystyle A^{\ast }}$ de mots sur${\displaystyle A}$ est un monoïde pour laconcaténation. Les sous-ensembles rationnels de${\displaystyle A^{\ast }}$ sont exactement leslangages réguliers sur l'alphabet${\displaystyle A}$. En effet, les langages réguliers peuvent être définis par uneexpression régulière.

Les sous-ensembles rationnels du monoïde additif${\displaystyle \mathbb{N}}$ desentiers naturels sont les ensembles d'entiers ultimement périodiques, unions finies deprogressions arithmétiques. Plus généralement, les sous-ensembles rationnels de${\displaystyle {\mathbb{N}}^k}$ sont lesensembles semi-liéaires^[1].

Un théorème dû à McKnight^[2] stipule que si${\displaystyle N}$ est un monoïde finiment engendré, alors ses sous-ensembles reconnaissables sont des ensembles rationnels. Cet énoncé n'est pas vrai en général, car l'ensemble${\displaystyle N}$ tout entier est toujours reconnaissable mais il n'est pas rationnel si${\displaystyle N}$ n'est pas finiment engendré.

Les ensembles rationnels sont fermés parmorphisme : étant donné${\displaystyle N}$ et${\displaystyle M}$ deux monoïdes et un morphisme${\displaystyle \varphi :N\to M}$ morphisme, si${\displaystyle S\in \mathrm{R}\mathrm{a}\mathrm{t}(N)}$ alors${\displaystyle \varphi (S)=\{\varphi (x)\mid x\in S\}\in \mathrm{R}\mathrm{a}\mathrm{t}(M)}$ .

La famille${\displaystyle \mathrm{R}\mathrm{a}\mathrm{t}(N)}$ n'est pas fermée parcomplémentation comme le montre l'exemple suivant^[1] : Soient${\displaystyle N=\{a{\}}^{\ast }\times \{b,c{\}}^{\ast }}$ ; les ensembles${\displaystyle R=(a,b{)}^{\ast }(1,c{)}^{\ast }=\{(a^n,b^n{c}^m)\mid n,m\in \mathbb{N}\}}$ et${\displaystyle S=(1,b{)}^{\ast }(a,c{)}^{\ast }=\{(a^n,b^m{c}^n)\mid n,m\in \mathbb{N}\}}$ sont rationnels mais leur intersection${\displaystyle R\cap S=\{(a^n,b^n{c}^n)\mid n\in \mathbb{N}\}}$ ne l'est pas parce que sa projection sur le deuxième élément${\displaystyle \{b^n{c}^n\mid n\in \mathbb{N}\}}$ n'est pas un langage rationnel.

L'intersection d'un sous-ensemble rationnel et d'un sous-ensemble reconnaissable est en revanche un ensemble rationnel.

Unerelation binaire entre les monoïdesM etN est unerelation rationnelle si le graphe de la relation, considéré comme un sous-ensemble deM ×N est un ensemble rationnel dans le monoïde produit. Une fonction deM àN est unefonction rationnelle si le graphe de la fonction est un ensemble rationnel^[3]

Les parties rationnelles de groupes ont fait l'objet de nombreuses études. Une synthèse est présentée dans (Cadilhac, Chistikov et Zetzsche 2020). Parmi les résultats les plus anciens, il y a :

Unsous-groupe${\displaystyle H}$ d'un groupe${\displaystyle G}$ est une partie reconnaissable de${\displaystyle G}$ si et seulement s'il est d'index fini.

Un sous-groupe${\displaystyle H}$ d'un groupe${\displaystyle G}$ est une partie rationnelle de${\displaystyle G}$ si et seulement s'il est finiment engendré.

Si${\displaystyle G}$ lui-même est finiment engendré, le théorème de McKnight cité plus haut implique que tout sous-groupe d'index fini est finiment engendré, un résultat habituellement attribué à Howson^[4]

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé« Rational set »(voir la liste des auteurs).

• VolkerDiekert, ManfredKufleitner, GerhardRosenberg et UlrichHertrampf,Discrete Algebraic Methods, Berlin/Boston, Walter de Gruyther GmbH,2016(ISBN 978-3-11-041332-8), « Chapter 7: Automata »
• Jean-Éric Pin, « Mathematical Foundations of Automata Theory », Irif(consulté le12 décembre 2020) :« Chapter IV: Recognisable and Rational sets ».
• Samuel Eilenberg etMarcel-Paul Schützenberger, « Rational Sets in Commutative Monoids »,Journal of Algebra,‎1969.
• JacquesSakarovitch,Elements of automata theory, Cambridge, Cambridge University Press,2009(ISBN 978-0-521-84425-3,zbMATH 1188.68177)
• Michaël Cadilhac, Dmitry Chistikov et Georg Zetzsche,« Rational Subsets of Baumslag-Solitar Groups », dans Artur Czumaj Anuj Dawar Emanuela Merelli (éditeurs),Actes de ICALP 2020, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,coll. « LIPIcs » (n^o 168),2020(DOI 10.4230/LIPIcs.ICALP.2020.116,arXiv 2006.11898 (version détaillée),lire en ligne),p. 116:1-116:16

• Série rationnelle (en)
• Ensemble reconnaissable (en)
• Monoïde rationnel (en)
• Transduction rationnelle
• Théorème de Kleene

• Portail de l'informatique théorique

• Théorie des automates
• Langage formel

• Article contenant un appel à traduction en anglais
• Portail:Informatique théorique/Articles liés
• Portail:Informatique/Articles liés
• Projet:Mathématiques/Articles