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

Soit un monoïde avec élément neutre . L'ensemble des sous-ensembles rationnels ou parties rationnelles de est la plus petite famille de parties de contenant les parties finie et fermé sous les opérations suivantes :

  • union : si alors
  • produit: si alors
  • étoile de Kleene : si alors
est le singleton contenant l'élément d'identité, et .

En d'autres termes, tout sous-ensemble rationnel de est obtenu en prenant un nombre fini de sous-ensembles finis de 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 un alphabet. L'ensemble de mots sur est un monoïde pour la concaténation. Les sous-ensembles rationnels de sont exactement les langages réguliers sur l'alphabet . En effet, les langages réguliers peuvent être définis par une expression régulière.

Les sous-ensembles rationnels du monoïde additif 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 sont les ensembles semi-liéaires[1].

Propriétés

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

Les ensembles rationnels sont fermés par morphisme : étant donné et deux monoïdes et un morphisme morphisme, si alors .

La famille n'est pas fermée par complémentation comme le montre l'exemple suivant[1] : Soient  ; les ensembles et sont rationnels mais leur intersection ne l'est pas parce que sa projection sur le deuxième élément 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[3]

Parties rationnelles de groupes

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

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

Si 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

  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,‎ , 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, , 379–406 p. (zbMATH 1031.20047), « Some relatives of automatic and hyperbolic groups ».
  4. John Meakin, Groups St Andrews 2005 Volume 2, Cambridge University Press, (ISBN 978-0-521-69470-4), « Groups and semigroups: connections and contrasts », p. 376 preprint.

Bibliographie


Articles liés