Date : 2007
Editeur / Publisher : [S.l.] : [s.n.] , 2007
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Théorie des automates mathématiques
Résumé / Abstract : L'objectif de cette thèse est de fournir de nouveaux outils algébriques afin d'étudier des familles de langages rationnels qui échappaient jusque là à l'approche algébrique et à son arsenal. Cette démarche est motivée par plusieurs problèmes ouverts issus de la théorie des langages (problème de la hauteur d'étoile généralisée par exemple), de la logique (décidabilité de certains niveaux de hiérarchies de concaténation) et de la dynamique symbolique (décidabilité de l'équivalence faible des systèmes sofiques) dans lesquels les familles de langages pertinentes ne peuvent pas être caractérisées avec les outils existants. Le cadre de ce travail est la toute jeune théorie des C-variétés, introduite par H. Straubing il y a quelques années, et que nous avons enrichie de nouveaux résultats. Notre attention s'est portée tout particulièrement sur l'extension du produit en couronne aux C-variétés et sur les applications de ce nouvel outil à la logique et à la dynamique symbolique.
Résumé / Abstract : The purpose of this PhD thesis is to provide new algebraic tools designed to study families of rational languages that could not be treated by algebraic methods until now. This approach was motivated by open several open problems in language theory (such as the generalized star-height problem), in logic (the decidability problem for some fragments of first-order logic on words), and in symbolic dynamics ( the decidability of weak equivalence between sofic subshifts). This work's framework is the new-born theory of C-varieties, introduced only a few years ago by Howard Straubing, and which we enriched with some new results. We particularly focused on the generalization of the wreath product operation to C-varieties, as well as its applications to logic and symbolic dynamics.