Ensemble rationnel

En informatique théorique, plus particulièrement en théorie des automates, un ensemble rationnel dans un monoï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 par union, produit et étoile de Kleene. Les ensembles rationnels interviennent en théorie des automates, en théorie des langages formels et en algèbre.

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

Définition[modifier | modifier le code]

Soit $N$ un monoïde avec élément neutre $e$ . L'ensemble $\mathrm {Rat} (N)$ des sous-ensembles rationnels ou parties rationnelles de $N$ est la plus petite famille de parties de $N$ contenant les parties finie et fermé sous les opérations suivantes :

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

A^{*}=\bigcup _{i=0}^{\infty }A^{i}\in \mathrm {Rat} (N)

où

A^{0}=\{e\}

est le singleton contenant l'élément d'identité, et

A^{n+1}=A^{n}A

.

En d'autres termes, tout sous-ensemble rationnel de $N$ est obtenu en prenant un nombre fini de sous-ensembles finis de $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.

Exemples[modifier | modifier le code]

Soit $A$ un alphabet. L'ensemble $A^{*}$ de mots sur $A$ est un monoïde pour la concaténation. Les sous-ensembles rationnels de $A^{*}$ sont exactement les langages réguliers sur l'alphabet $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 $\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 $\mathbb {N} ^{k}$ sont les ensembles semi-liéaires^[1].

Propriétés[modifier | modifier le code]

Un théorème dû à McKnight^[2] stipule que si $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 $N$ tout entier est toujours reconnaissable mais il n'est pas rationnel si $N$ n'est pas finiment engendré.

Les ensembles rationnels sont fermés par morphisme : étant donné $N$ et $M$ deux monoïdes et un morphisme $\phi :N\rightarrow M$ morphisme, si $S\in \mathrm {Rat} (N)$ alors $\phi (S)=\{\phi (x)\mid x\in S\}\in \mathrm {Rat} (M)$ .

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

Relations rationnelles et fonctions rationnelles[modifier | modifier le code]

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]

Parties rationnelles de groupes[modifier | modifier le code]

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 $H$ d'un groupe $G$ est une partie reconnaissable de $G$ si et seulement s'il est d'index fini.

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

Si $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]

Notes et références[modifier | modifier le code]

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

↑ ^{a et b} Jean-Éric Pin.
↑ J. D. McKnight, « Kleene’s quotient theorem, Pacific J. Math, vol 14 (1964) 1343-1352. », Pacific J. Math, vol. 14,‎ 1964, p. 1343-1352 (MR 180612).
↑ Michael Hoffmann, Dietrich Kuske, Friedrich Otto et Richard M. Thomas, Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001, Singapore, World Scientific, 2002, 379–406 p. (zbMATH 1031.20047), « Some relatives of automatic and hyperbolic groups ».
↑ John Meakin, Groups St Andrews 2005 Volume 2, Cambridge University Press, 2007 (ISBN 978-0-521-69470-4), « Groups and semigroups: connections and contrasts », p. 376 preprint.

Bibliographie[modifier | modifier le code]

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

Articles liés[modifier | modifier le code]

Portail de l'informatique théorique

[jep-1] {a et b} Jean-Éric Pin.

[2] J. D. McKnight, « Kleene’s quotient theorem, Pacific J. Math, vol 14 (1964) 1343-1352. », Pacific J. Math, vol. 14,‎ 1964, p. 1343-1352 (MR 180612).

[3] Michael Hoffmann, Dietrich Kuske, Friedrich Otto et Richard M. Thomas, Semigroups, algorithms, automata and languages. Proceedings of workshops held at the International Centre of Mathematics, CIM, Coimbra, Portugal, May, June and July 2001, Singapore, World Scientific, 2002, 379–406 p. (zbMATH 1031.20047), « Some relatives of automatic and hyperbolic groups ».

[Campbell2007-4] John Meakin, Groups St Andrews 2005 Volume 2, Cambridge University Press, 2007 (ISBN 978-0-521-69470-4), « Groups and semigroups: connections and contrasts », p. 376 preprint.

[1]

[2]

[3]

[4]