|
2.16. Modèles de calcul et automates finis (48h, 6 ECTS)Responsable : Matthieu PicantinÉquipe pédagogique : Marie Fortin, 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 2023-2024
PlanningLe cours a lieu le lundi de 08h45 à 11h45 en salle 1004 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 27 novembre de 8h45 à 11h45 dans la salle 1004. L'examen aura deux parties de 1h30. Pour les deux parties tous les documents écrits non-éléctroniques 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. Automates, monoïdes, et logique (Marie Fortin)Cette partie du cours introduit un point de vue algébrique et logique sur les automates et les langages, en le reliant à la théorie des monoïdes finis et à la logique monadique du second ordre. Nous montrerons comment des classes de langages réguliers peuvent être caractérisées en utilisant des monoïdes finis. En particulier, nous démontrerons une telle caractérisation des langages sans étoile, un résultat classique de Schützenberger, qui nous permettra de montrer la décidabilité du problème de l'appartenance à cette classe. À partir de là, nous établirons un lien avec les descriptions logiques des langages réguliers et, si le temps le permet, nous montrerons certaines généralisations au mots infinis et aux problèmes de séparation, ce qui nous amènera à la frontière de la recherche actuelle dans ce domaine. Le contenu du cours sera basé sur une sélection de chapitres des deux livres ci-dessous ; les références aux sections précises seront disponibles sur cette page au fur et à mesure de l'avancement du cours. This part of the course introduces an algebraic and logical point of view on automata and languages, by connecting it to the theory of finite monoids and to monadic second order logic. We will show how classes of regular languages can be characterized using finite monoids. In particular, we show how a classical such characterization of star-free languages, due to Schützenberger, leads to the decidability of the membership problem of this class. From here, we will make a connection to logical descriptions of regular languages, and, if time permits, we will show some generalizations to infinite words and to separation problems, bringing us to the frontier of current research in this area. The contents of the course is based on selected chapters from the two books below; lecture notes are now also available.
Exercise sheet for the last class, Nov 16th. 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
|