Langages formels, algèbres finies et automates.

点击翻译按钮获取中文摘要

Les algèbres associatives (semigroupes et monoïdes) et non-associatives (groupoïdes, quasigroupes, boucles) permettent de modéliser la reconnaissance de langages de mots, c'est-à-dire de décider si un mot reçu en donnée appartient à un ensemble prédéterminé. De même, on utilise les algèbres généralisées et les algèbres de forêts pour les données bidimensionnelles hiérarchiques que sont les arbres et les forêts. L'étude des relations qui peuvent exister entre différentes classes (variétés) d'algèbres et de langages est un important domaine de recherche en informatique théorique. Le projet que je propose est axé sur deux directions de recherche. La première consiste à étudier la reconnaissance de langages de mots par des algèbres non-associatives ; cela permet d'établir des descriptions, en termes non-associatifs, de variétés de langages de mots qui avaient été définies en des termes très différents. La seconde direction de recherche consiste à faire un travail analogue avec les algèbres et langages de forêts. Je veux en particulier étudier une manière de construire des algèbres de forêts, le produit contexte, et les limites sur la puissance des algèbres qui peuvent être obtenus de la sorte, en comparant les langages de forêts qu'elles reconnaissent avec des variétés de langages déjà définies en termes de logique formelle ou de variétés de monoïdes.