Ma thèse intitulée "Automates sur les ordres linéaires : Complémentation" a été soutenue le 7 décembre 2004.

Les membres du jury :

-Dominique Perrin, IGM, Université de Marne-la-Vallée (Président)

-Didier Caucal, CNRS, IRISA, Rennes (Rapporteur)

-Jean-Eric Pin, LIAFA, Université Paris 7 (Rapporteur)

-Jean Berstel, IGM, Université de Marne-la-Vallée (Examinateur)

-Véronique Bruyère, Université de Mons-Hainaut, Belgique (Examinateur)

-Olivier Carton, LIAFA, Université Paris 7 (Directeur de thèse)

Résumé de la thèse

Cette thèse traite des ensembles rationnels de mots indexés par des ordres linéaires et en particulier du problème de la fermeture par complémentation.

Dans un papier fondateur de 1956, Kleene initie la théorie des langages en montrant que les automates sur les mots finis et les expressions rationnelles ont le même pouvoir d'expression. Depuis, ce résultat a été étendu à de nombreuses structures telles que les mots infinis (Büchi, Muller), bi-infinis (Beauquier, Nivat, Perrin), les mots indexés par des ordinaux (Büchi, Bedon), les traces, les arbres... Plus récemment, Bruyère et Carton ont introduit des automates acceptant des mots indexés par des ordres linéaires et des expressions rationnelles correspondantes. Ces structures linéaires comprennent les mots infinis, les mots indexés par des ordinaux et leurs miroirs. Le théorème de Kleene a été généralisé aux mots indexés par les ordres linéaires dénombrables et dispersés, c'est-à-dire les ordres ne contenant pas de sous-ordre isomorphe à Q.

Pour la plupart des structures, la classe des ensembles rationnels forme une algèbre de Boole. Cette propriété est nécessaire pour traduire une logique en automates. La fermeture par complémentation restait un problème ouvert. Dans cette thèse, on résout ce problème de façon positive: on montre que le complément d'un ensemble rationnel de mots indexés par des ordres linéaires dispersés est rationnel. La méthode classique pour obtenir un automate acceptant le complémentaire d'un ensemble rationnel se fait par déterminisation. Nous montrons que cette méthode ne peut-être appliquée dans notre cas: tout automate n'est pas nécessairement équivalent à un automate déterministe. Nous avons utilisé d'autres approches. Dans un premier temps, nous généralisons la preuve de Büchi, basée sur une congruence de mots, et obtenons ainsi la fermeture par complémentation dans le cas des ordres linéaires de rang fini. Pour obtenir le résultat dans le cas général, nous utilisons l'approche algébrique. Nous développons une structure algébrique qui étend la reconnaissance classique par semigroupes finis : les semigroupes sont remplacés par les diamant-semigroupes qui possèdent un produit généralisé. Nous prouvons qu'un ensemble est rationnel si et seulement s'il est reconnu par un diamant-semigroupe fini. Nous montrons aussi qu'un diamant-semigroupe canonique, appelé diamant-semigroupe syntaxique, peut être associé à chaque ensemble rationnel. Notre preuve de la complémentation est effective.

Le théorème de Schützenberger établit qu'un ensemble de mots finis est sans étoile si et seulement si son semigroupe syntaxique est fini et apériodique. Pour finir, nous étendons partiellement ce résultat au cas des ordres de rang fini.

Manuscrit de thèse à téléchager

version pdf, version pdf gzippé, version ps, version ps gzippé.

Travaux de DEA

Comme pour les familles de langages rationnels, une hiérarchie de graphes infinis existe. Si on code les sommets d'un graphe par des mots et que les arcs sont définis par des relations entre les sommets, chaque famille de graphe est caractérisée par un type de relation. Ainsi pour les graphes rationnels, chaque étiquette est définie par une relation rationnelle, c'est-à-dire un transducteur. Les traces d'un graphe (étiquettes des chemins menant d'un ensemble fini de sommets à un autre) constituent un lien entre la hiérarchie des graphes infinis et celle des langages rationnels de Chomsky. Par exemple, Morvan et Stirling ont montré que les traces des graphes rationnels sont exactement les langages contextuels. On montre que ce résultat reste vrai lorsqu'on se restreint aux graphes rationnels synchronisés, définis par des transducteurs lettre-à-lettre suivis de relations reconnaissables.