Next: Autres applications
de
Up: Home Page
Previous: Logique et
automates
Je travaille sur les mots infinis depuis 1984 [31] et je prépare actuellement un livre sur ce sujet avec D. Perrin [78]. J'ai mentionné plus haut l'article [45], écrit en collaboration avec D. Perrin, qui permet d'étendre aux mots infinis le résultat de W. Thomas qui relie la hiérarchie de la logique du premier ordre aux hiérachies de concaténation sur les langages de mots finis. L'article [55], écrit avec D. Beauquier contient lui aussi plusieurs résultats sur les mots infinis. Le résultat central sur les ensembles reconnaissables de mots infinis est incontestablement le difficile théorème de McNaughton, qui établit l'équivalence entre les automates non-déterministes de Büchi et les automates déterministes de Muller. J'ai proposé avec B. Le Saec et P. Weil, une preuve entièrement nouvelle de ce résultat, basée sur la résolution d'une conjecture de théorie des semigroupes formulée par B. Le Saec [67,68]. Enfin, la préparation du livre a conduit D. Perrin et moi-même à de très nombreux nouveaux résultats, qui ne sont pour la plupart pas encore publiés à ce jour. J'ai toutefois publié en 1995 [90] un contre-exemple à une conjecture de Wilke. L'un de ses résultats est l'extension aux mots infinis des méthodes élégantes utilisant des semigroupes. Reprenant des travaux antérieurs d'Arnold, Pécuchet et Wilke, j'ai montré que le bon concept était celui de semigroupe muni de produits infinis. La théorie s'en trouve simplifiée et peut se généraliser à d'autres structures (ordinaux). Il y a là un vaste programme d'unification et probablement le sujet de quelques thèses.