english? Retour

Langages reconnaissables de mots indexés par des ordinaux

Thèse présentée le jeudi 15 janvier 1998.

Mots clefs

Langage, ordinal, automate, semigroupe, logique, variété de langages.

Jury

Résumé

Cette thèse traite des langages reconnaissables de mots indexés par des ordinaux.

Plusieurs classes d'automates qui reconnaissent de tels mots ont été introduites par Büchi. Elles diffèrent par la longueur des mots reconnus par les automates. Nous en utilisons quatre: la classe pour les mots de longueur $\omega$, celle pour les mots de longueur inférieure à $\omega^{n+1}$, où n est un entier naturel, celle pour les mots de longueur dénombrable, et celle pour les mots de longueur quelconque. Nous y ajoutons la classe des automates de Kleene traditionnelle, sur les mots finis. Nous remontrons que ces différentes définitions d'automates sont équivalentes, c'est-à-dire que données deux de ces classes et un automate d'une des deux, la restriction du langage reconnu par l'automate aux mots du domaine le plus petit des deux classes est la restriction du langage reconnu par un automate de l'autre classe au même domaine. Nous donnons également une présentation unifiée de la déterminisation pour chacune des classes qui reconnaît au plus des mots de longueur dénombrable.

Les semigroupes finis sont un formalisme équivalent aux automates pour définir des ensembles de mots finis. Perrin, Pin et Wilke ont introduits des structures algébriques adaptées à l'étude des langages de mots de longueur $\omega$, qui, quand elles sont finies, sont équivalentes aux automates. Nous généralisons l'approche algébrique de la théorie des langages reconnaissables de mots de longueur $\omega$ aux mots de longueur inférieure à $\omega^{n+1}$, puis aux mots de longueur dénombrable. Pour cela, nous définissons deux structures algébriques, les $\omega^n$-semigroupes et les $\omega_1$-semigroupes, qui, quand elles sont finies, sont équivalentes respectivement aux automates pour les mots de longueur inférieure à $\omega^{n+1}$ et aux automates pour les mots de longueur dénombrable. Comme pour le cas des mots de longueur $\omega$, une algèbre syntaxique peut être canoniquement associée à chaque langage reconnaissable. Nous définissons le produit de Schützenberger et le produit en couronne sur les $\omega_1$-semigroupes. Nous étendons également le théorème des variétés d'Eilenberg aux mots de longueur dénombrable.

Finalement, nous remontrons l'équivalence entre langages reconnus par automates et langages définis par énoncés de logique monadique du second ordre quand on s'intéresse aux mots de longueur dénombrable. Le théorème d'équivalence de Schützenberger entre langages sans étoile et semigroupes finis apériodiques est étendu aux mots de longueur inférieure à $\omega^{n+1}$, et le théorème d'équivalence entre langages sans étoile et langages définis par énoncés de logique du premier ordre de l'ordre linéaire de McNaughton et Papert est étendu aux mots de longueur quelconque.


Le document complet

Les transparents de l'exposé

Valid HTML 4.01!

My email address 25 January 2015 11:14:23