Abstract EN:

Dans cette thèse, nous nous appliquons à étendre les liens entre les modèles de représentation des langage rationnels que sont les automates, la logique et les monoïdes au travers de deux extensions de ces théories. La première contribution concerne les transducteurs bidirectionnels, qui sont une extension des automates, définissant des transformations de mots. Nous proposons tout d'abord la construction du monoïde de transitions des machines bidirectionnelles. Cela nous permet ensuite de définir la notion de transducteurs bidirectionnels apériodiques. Nous prouvons finalement la stabilité de cette classe par composition. La seconde contribution concerne la logique sur mots finis. Le problème de la définissabilité d'un fragment logique est de pouvoir décider si un langage est définissable par une formule de ce fragment. Nous étudions la décidabilité de cette question lorsqu'un fragment voit sa signature enrichie, ici par des prédicats traitant de l'information modulaire des positions. Grâce à des méthodes algébriques, nous obtenons des résultats de transfert de décidabilité vers les fragments enrichis, unifiant d'anciens résultats connus, tout en en obtenant de nouveaux.