Ensemble rationnel

Modèle:Confusion 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

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

$A^{*}=\bigcup _{i=0}^{\mathrm{\infty }}{A}^i\in \mathrm{R}\mathrm{a}\mathrm{t}(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

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.

Propriétés

Un théorème dû à McKnight 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 $\varphi :N\to M$ morphisme, si $S\in \mathrm{R}\mathrm{a}\mathrm{t}(N)$ alors $\varphi (S)=\{\varphi (x)\mid x\in S\}\in \mathrm{R}\mathrm{a}\mathrm{t}(M)$ .

La famille $\mathrm{R}\mathrm{a}\mathrm{t}(N)$ n'est pas fermée par complémentation comme le montre l'exemple suivant : 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

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

Parties rationnelles de groupes

Les parties rationnelles de groupes ont fait l'objet de nombreuses études. Une synthèse est présentée dans Modèle:Harv. 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

Bibliographie

• Modèle:Ouvrage
• Modèle:Lien web.
• Modèle:Article.
• Modèle:Ouvrage
• Modèle:Chapitre

Articles liés

• Modèle:Lien
• Modèle:Lien
• Modèle:Lien
• Transduction rationnelle
• Théorème de Kleene