|
2.16. Modèles de calcul et automates finis (48h, 6 ECTS)Responsable : Matthieu PicantinÉquipe pédagogique : Thomas Colcombet, Peter Habermehl, Daniela Petrisan, et Matthieu Picantin. Table des matières
ObjectifsLes automates finis sont l'un des modèles les plus simples de machines qui calculent, le premier dans toute hiérarchie de machines de Turing plus ou moins contraintes. Cette simplicité en fait un objet robuste, susceptible de nombreuses définitions équivalentes relevant de la théorie de la complexité, de l'algèbre non-commutative et de la logique.La théorie classique des automates finis traite d'automates qui acceptent, ou n'acceptent pas, des mots. L'objectif de ce cours est de montrer comment introduire des notions sortant de ce cadre, et comment se servir de ces extensions dans différents contextes. Ainsi, nous verrons des machines à états finies permettant de calculer différentes sortes de fonctions ou des relations. Nous verrons également comment ce type d'outils sert dans l'analyse de structures infinies et en particulier des groupes. Plus précisément, les points suivants sont abordés dans ce cours:
Plan du cours et intervenants prévus pour 2024-2025
PlanningLe cours a lieu le mercredi de 12h45 à 15h45 en salle 1002 du bâtiment Sophie Germain. Chaque séance de cours comprendra (en gros) 2 heures de cours et 1 heure consacrée à des exercices. Les séances de travaux dirigés, facultatives, seront essentiellement consacrées à des exercices; les compléments qui pourront y être abordés ne seront pas au programme des examens. Langue du coursLes intervenants feront cours en français, sauf si des étudiants non francophones demandent que le cours soit donné en anglais. Des supports en anglais sont disponibles pour certaines parties du cours. The teachers will teach in French, unless non-French-speaking students ask for the course to be given in English. For certain parts of the course, notes in English will be made available. PrérequisIl est bon, avant d'aborder ce cours, de connaitre la théorie élémentaire des automates finis: théorème de Kleene, déterminisation, minimisation et expressions régulières. Cours associésBien qu'il n'existe pas de dépendance avec d'autres cours du MPRI, certains traitent de sujets reliés. Il s'agit en particulier des cours:
Contrôle des connaissanceLe contrôle des connaissances se fait en deux phases: un examen écrit à la fin de chacune des deux séquences et portant sur le programme vu pendant cette séquence. L'examen de la première partie aura lieu le Mercredi 11 décembre de 12h45 à 15h45 dans la salle 1002. L'examen aura deux parties de 1h30. Pour les deux parties tous les documents écrits non-électroniques sont autorisés. Calendrier des cours
Description détaillée du coursLes sujets abordés dans ce cours sont détaillés ci-dessous. Apprentissage symbolique d'automates (Peter Habermehl)Voir aussi la page de cette partie.Dans cette partie nous introduisons les techniques d'apprentissage symboliques pour les automates finis. Nous définissons le problème d'apprentissage passif où étant donné un échantillon de mots, l'apprenant doit inférer le langage (ou l'automate) duquel l'échantillon a été extrait. L'échantillon peut-être constitué uniquement de mots appartenant au langage (apprentissage par texte) ou aussi de mots n'appartenant pas au langage (apprentissage par informant). Les langages rationnels ne peuvent pas être appris uniquement par texte. Par contre, des sous-classes le peuvent. Nous en donnons quelques examples et des algorithmes d'apprentissage avec certaines garanties de complexité. Nous donnons également des algorithmes d'apprentissage par informant (l'algorithme de Gold et RPNI notamment). Nous montrons que le problème d'inférer un automate avec un nombre minimal d'états à partir d'un échantillon est NP-complet. Ensuite, nous étudions l'apprentissage actif (ou par requête) où l'apprenant peut poser des questions à un oracle. Par exemple, est-qu'un mot est dans le langage ? Est-ce que le langage recherché est le même qu'une certaine hypothèse ? Nous étudions en détail l'algorithme L* fondateur d'Angluin dans ce cadre ainsi que certaines variantes. Ensuite, certaines techniques sont étendues vers d'autres types d'automates pour les langages rationnels (non-déterministe, alternant) mais aussi des automates plus puissants (automates symboliques, temporisés, etc.) Nous donnons également quelques applications des méthodes étudiées. Quelques références:
Automates finis à multiplicité (Daniela Petrisan)Les automates à multiplicité sont un modèle de calcul très riche. Si les automates classiques acceptent des mots, les automates à multiplicité examinent le nombre de façons pour accepter ou les ressources nécessaires pour accepter des mots. Plus généralement, les automates à multiplicité sont des automates possédant une sortie dans un semi-anneau arbitraire. Cette génralisation permet de couvrir de nombreux modèles d'automates tels que les automates Min-Plus, les transducteurs ou des automates à pile. Dans ce cours, nous introduisons les automates à multiplicité et les notions de rationalité et reconnaissabilité. Après avoir discuté la relation entre ces notions et le théorème de Kleene-Schutzenberger, nous considérons les notions de bisimulation et les morphismes des automates et nous fournissons une approche algébrique pour la minimisation. Dans une deuxième partie, nous étudions plus particulièrement les transducteurs, c'est-à-dire les automates avec des mots en sortie. En particulier, nous étudierons les relations rationnelles et le théorème de composition assicié. Enfin, nous présenterons une approche algébrique pour la minimisation des transducteurs sous-séquentiels, basée sur une notion de congruence syntaxique pour les fonctions introduite par Choffrut, et une généralisation aux fonctions rationnelles due à Reutenauer et Schutzenberger. Fonctions régulières de coût (Thomas Colcombet)Les automates à coûts sont des automates finis équipés de compteurs que l'on peut remettre à zéro ou incrémenter. Un tel automate associe à chaque mot une valeur entière, son coût. Dans le cas des B-automates (l'une des formes d'automates à coût) il s'agit du minimum sur toutes les exécutions de la valeur maximale prise par les compteurs au cours de cette exécution. Le problême central que l'on cherche à résoudre sur ce type d'automates est la "limitedness". Il s'agit de décider, étant donné un B-automate, si la fonction qu'il calcule est bornée. Différents problèmes difficiles en théorie des langages se réduisent au problème de la "limitedness":
Au cours de cette partie du cours nous verrons:
Automates, semigroupes, dualité (Matthieu Picantin)Comme leur nom l'indique, les (semi)groupes d’automate et les (semi)groupes automatiques sont définis à partir d’un même objet: un automate ou, plus précisément, un transducteur lettre-à-lettre. En dépit de cette origine commune, ces deux théories restaient essentiellement distantes depuis plus de trente ans, que ce soit en terme de communauté ou en terme d’outils et de résultats.
Bibliographie
|