Théorie des Langages et automates

Langage géométrique
Langage géométrique

Le domaine de la théorie des langages est une thématique historique du LIFAR. Du point de vue de la recherche fondamentale, les problèmes étudiés portent sur le monoïde libre, les monoïdes partiellement commutatifs (les monoïdes de trace de Cartier-Foata) et la théorie des codes. Cette recherche a des applications à l’optimisation des programmes en compilation et en model checking.

Cependant une importante part de l’effort de recherche est principalement axée sur les applications.
Trois axes d’applications
  1. Validation d'applications temps-réel. Généralisation d’une classe de langages utilisée en validation hors-ligne d’applications temps-réel. Ceci peut être fait en utilisant un modèle basé sur des langages rationnels. Mais, à cause d’une propriété particulière de ces langages, on peut aussi utiliser un modèle basé sur la géométrie discrète et diminuer ainsi drastiquement le temps de calcul. Le but est le suivant : si on peut interpréter en termes de langages les propriétés qui font que le modèle géométrique est si efficace, on peut alors espérer obtenir de nouveaux algorithmes sur les automates avec de meilleures complexités. Outre les questions de théorie des langages et de géométrie discrète, cette problématique pose également des questions de combinatoire énumérative (énumération de polycubes par exemple).
  2. Théorie des jeux et apprentissage. Les méthodes à noyaux sont largement utilisées dans les techniques d’apprentissage statistique comme les SVMs (Support Vector Machines). Cortes, Haffner et Mohri ont introduit une famille générale de noyaux basée sur les transducteurs pondérés, les noyaux rationnels, qui étendent les méthodes à noyaux à l’analyse des séquences de longueur variable avec ou sans poids. Cette nouvelle technique de classification prend en compte la contrainte sur la longueur variable des séquences qui apparaît dans de nouvelles applications en traitement du texte et en reconnaissance de la parole. L’explosion du volume de données à traiter (extraction, classification, ...) dans des domaines comme le traitement automatique des langages naturels, l’ingénierie du web, ou encore l’ingénierie des documents digitaux, a suscité de nombreux travaux sur l’inférence grammaticale des séries rationnelles de mots et d’arbres. Il paraît donc d’un grand intérêt d’étudier les noyaux rationnels des langages rationnels stochastiques et ceux des langages rationnels d’arbres (pondérés ou non), en vue de l’apprentissage des familles de langages correspondants.
  3. Modélisation de structures arborescentes de document. Les automates d’arbres à multiplicités sont une généralisation à la fois des automates de mots à multiplicités et des automates d’arbres. Ils sont parfaitement adaptés pour la modélisation des structures de données arborescentes (pages web, documents digitaux) et sont de plus en plus utilisés comme modèles de langages en traitement automatique des langages naturels. Les défis posés par l’analyse de grandes masses de données, en extraction automatique en particulier, ont suscité de nouveaux travaux sur l’inférence grammaticale de ces automates.