Ensemble rationnel

Soit ${\displaystyle N}$ un monoïde avec élément neutre ${\displaystyle e}$. L'ensemble ${\displaystyle \mathrm {Rat} (N)}$ des sous-ensembles rationnels ou parties 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 {Rat} (N)}$ alors ${\displaystyle A\cup B\in \mathrm {Rat} (N)}$
• produit: si ${\displaystyle A,B\in \mathrm {Rat} (N)}$ alors ${\displaystyle AB=\{ab\mid a\in A,b\in B\}\in \mathrm {Rat} (N)}$
• étoile de Kleene : si ${\displaystyle A\in \mathrm {Rat} (N)}$ alors

${\displaystyle A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {Rat} (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^{*}}$ de mots sur ${\displaystyle A}$ est un monoïde pour la concaténation. Les sous-ensembles rationnels de ${\displaystyle A^{*}}$ sont exactement les langages réguliers sur l'alphabet ${\displaystyle A}$. En effet, les langages réguliers peuvent être définis par une expression régulière.

Les sous-ensembles rationnels du monoïde additif ${\displaystyle \mathbb {N} }$ des entiers naturels sont les ensembles d'entiers ultimement périodiques, unions finies de progressions arithmétiques. Plus généralement, les sous-ensembles rationnels de ${\displaystyle \mathbb {N} ^{k}}$ sont les ensembles 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 par morphisme : étant donné ${\displaystyle N}$ et ${\displaystyle M}$ deux monoïdes et un morphisme ${\displaystyle \phi :N\rightarrow M}$ morphisme, si ${\displaystyle S\in \mathrm {Rat} (N)}$ alors ${\displaystyle \phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {Rat} (M)}$ .

La famille ${\displaystyle \mathrm {Rat} (N)}$ n'est pas fermée par complémentation comme le montre l'exemple suivant[1] : Soient ${\displaystyle N=\{a\}^{*}\times \{b,c\}^{*}}$ ; les ensembles ${\displaystyle R=(a,b)^{*}(1,c)^{*}=\{(a^{n},b^{n}c^{m})\mid n,m\in \mathbb {N} \}}$ et ${\displaystyle S=(1,b)^{*}(a,c)^{*}=\{(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.

Une relation binaire entre les monoïdes M et N est une relation rationnelle si le graphe de la relation, considéré comme un sous-ensemble de M × N est un ensemble rationnel dans le monoïde produit. Une fonction de M à N est une fonction 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 :

Un sous-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).

• Volker Diekert, Manfred Kufleitner, Gerhard Rosenberg et Ulrich Hertrampf, 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é le 12 décembre 2020) : « Chapter IV: Recognisable and Rational sets ».
• Samuel Eilenberg et Marcel-Paul Schützenberger, « Rational Sets in Commutative Monoids », Journal of Algebra,‎ 1969.
• Jacques Sakarovitch, 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