|
2.16. Modèles de calcul et automates finis (48h, 6 ECTS)Responsable : Matthieu PicantinÉquipe pédagogique : Daniela Petrisan, Matthieu Picantin, Amaury Pouly, et Sam van Gool. 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 2022-2023
PlanningLe cours a lieu le mercredi 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 coursSam van Gool fera cours en anglais. Les autres 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. Sam van Gool will teach his part in English. The other 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. Calendrier des cours
Description détaillée du coursLes sujets abordés dans ce cours sont détaillés ci-dessous. 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 (Sam van Gool)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. Examen (1/2)The first exam will take place on November 30, 2022 between 8:45 and 11:45 in the usual lecture room, 1004. The exam will consist of two equal parts, corresponding to the lectures of Petrisan and of van Gool, respectively. Any notes on paper are allowed to be consulted, no electronic devices.Automates probabilistes et chaînes de Markov (Amaury Pouly)Les automates finis probabilistes (AFP) sont une généralisation des automates finis non-déterministes avec des probabilités de transitions. Un AFP associe à chaque mot la probabilité d'atteindre un état final. Une question naturelle est de savoir si un AFP accepte au moins un mot avec probabilité 0.5 ou plus. Nous établirons l'indécidabilité de ce problème.Un cas particulier important des AFP est celui des chaînes de Markov: il s'agit du cas où l'alphabet est unaire (autrement dit, on ne distingue plus les mots mais seulement les états). Nous verrons que même dans ce cas, le problème de savoir si un état est accessible avec probabilité 0.5 ou plus reste difficile. Pour cela, nous montrerons le lien entre ce problème et celui dit du Skolem. Ce problème très connu concernant les suites récurrentes linéaires est ouvert depuis plus de 70 ans. Nous prouverons le théorème de Skolem–Mahler–Lech qui décrit la structure des zéros des suites récurrentes linéaires. Nous verrons pourquoi ce théorème, non-constructif, ne permet pas en général de répondre de façon algorithmique au problème posé. Plus d'informations ici. 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
Examen (2/2)The second exam will take place on March 1, 2023 between 8:45 and 11:45 in the usual lecture room, 1004. The exam will consist of two equal parts, corresponding to the lectures of Pouly and of Picantin, respectively. Any notes on paper are allowed to be consulted, no electronic devices.Informations complémentairesÉquipe pédagogique
|