Parisian Master of Research in Computer Science
Master Parisien de Recherche en Informatique (MPRI)

Cours-MPRI.2.16-2020-2021

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

Objectifs

Les 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:
  • Les automates finis probabilistes forment une instantiation d'importance des automates à multiplicités dont un cas particulier sont les chaînes de Markov. On s'intéressera aux questions de décidabilité les concernants.
  • Les monoïdes profinis permettent d'adopter un point de vue algébrique et topologique sur les automates et leurs langages. On s'interessera en particulier aux liens avec la dualité de Stone et la logique.
  • Les automates à multiplicité (ou automates pondérés) offrent aux machines à états finies la capacité de calculer des valeurs en sortie. Ce sont des objets génériques en ce sens qu'ils peuvent être spécialisés suivant l'univers de calcul utilisé (formellement un semi-anneau).
  • Les transducteurs sont un cas particulier d'automates pondérés de première importance. Ils calculent des fonctions des mots dans les mots ou des relations entre mots.
  • Les semi-groupes d'automates et les semi-groupes automatiques sont des semi-groupes en général infinis dont la description est donnée au moyen de transducteurs lettre-à-lettre (finis).

Plan du cours et intervenants prévus pour 2020-2021

  1. Automates probabilistes et chaînes de Markov (12h + 3h TD, Amaury Pouly)
  2. Automata and profiniteness (12h + 3h TD, Sam van Gool)
  3. Automates finis à multiplicité et transducteurs (12h + 3h TD, Daniela Petrisan)
  4. Semi-groupes et automates (12h + 3h TD, Matthieu Picantin)

Planning

Le cours a lieu le vendredi de 08h45 à 11h45 en salle 1013 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 cours

Sam van Gool fera cours en anglais. Les autres intervenants feront cours en français.

Si des étudiants non francophones le demandent, le cours aura lieu en anglais. Des supports en anglais sont disponibles pour certaines parties du cours.

Prérequis

Il 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és

Bien 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:

  • 1-18 Tree automata and applications
  • 1-22 Basics of verification
  • 2.9.1 Mathematical foundations of the theory of infinite transition systems 
  • 2.9.2 Algorithmic verification of programs
  • 2.20.2 Mathematical foundations of automata theory
  • 2.27.1 Computational structures and logics for natural language modelling

Contrôle des connaissance

Le 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.

Chacun de ces examens comptera pour moitié pour la note finale.

Calendrier des cours

 Date  Contenu Enseignant
18 Sept. Automates probabilistes et chaînes de Markov (1) Pouly
25 Sept. Automates probabilistes et chaînes de Markov (2) Pouly
02 Oct. Automates probabilistes et chaînes de Markov (3) Pouly
09 Oct. Automates probabilistes et chaînes de Markov (4) Pouly
16 Oct. Automates probabilistes et chaînes de Markov (TD) Pouly
23 Oct. Automata and profiniteness (1) van Gool
30 Oct. Automata and profiniteness (2) van Gool
06 Nov. Automata and profiniteness (3) van Gool
13 Nov. Automata and profiniteness (4) van Gool
20 Nov. Automata and profiniteness (TD) van Gool
27 Nov. pas cours
04 Déc. Examen (1)

 Date  Contenu Enseignant
11 Déc. Automates à multiplicité et transducteurs (1) Petrisan
18 Déc. Automates à multiplicité et transducteurs (2) Petrisan
08 Janv. Automates à multiplicité et transducteurs (3) Petrisan
15 Janv. Automates à multiplicité et transducteurs (4) Petrisan
22 Janv. Automates à multiplicité et transducteurs (TD) Petrisan
29 Janv. Semi-groupes et automates (1) Picantin
05 Fév. Semi-groupes et automates (2) Picantin
12 Fév. Semi-groupes et automates (3) Picantin
19 Fév. Semi-groupes et automates (4) Picantin
26 Fév. Semi-groupes et automates (TD) Picantin
05 Mars pas de cours
12 Mars Examen (2)


Description détaillée du cours

Les sujets abordés dans ce cours sont détaillés ci-dessous.

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.


Automata and profiniteness (Sam van Gool)

This part of the course introduces an algebraic and topological point of view on automata and languages, using the theory of profinite monoids. We will begin by explaining how the syntactic monoid of a regular language is related to a Boolean algebra canonically associated to that language. We will then show how this relationship plays a role in a classical result of Schützenberger, the decidability of the class of star-free languages through a characterization of their syntactic monoids. Stone duality will be introduced in order to place this result in a wider context, namely the correspondence between certain classes of regular languages and certain profinite monoids, yielding the modern point of view on Eilenberg-Reiterman variety theory. Building on this theory, we will make a connection to logic, and, if time permits, we will show some generalizations to the non-regular setting, bringing us to the frontier of current research in this area.

What follows is a rough planning of the four lectures in this part:
  1. Syntactic monoids as topological algebras; the dual equivalence between profinite monoids and Boolean algebras with residuation.
  2. Eilenberg-Reiterman correspondence theory, and a few particular cases, such as Schützenberger's Theorem: aperiodic = star-free.
  3. Connections to logic: monadic second order logic and the power space construction; pro-aperiodic monoids via model theory.
  4. Generalizing to non-regular languages: ultrafilter equations and measures.
These lectures will be delivered in English; lecture notes in English will be made available during the course.

References



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.



Semi-groupes et automates (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.

  • La première partie traitera des notions de formes normales et d’automaticité dans les semi-groupes: nous examinerons plusieurs constructions et étudierons le cas des formes normales quadratiques.
  • La deuxième partie sera consacrée aux semi-groupes d’automates: des outils différents, des questions différentes mais, toujours, des exemples de semi-groupes aux propriétés remarquables.
  • La troisième partie permettra d’établir une possible connexion entre « être un semi-groupe automatique » et « être un semi-groupe d’automate »: nous verrons les conditions pour que cela en fasse des propriétés duales.

Bibliographie

  • Un chapitre sur les groupes automatiques et les groupes d'automate:
    Groups defined by automata, L. Bartholdi, P. V. Silva.
    AutoMathA Handbook. J.-E. Pin (Ed)
    http://arxiv.org/abs/1012.1531 (2010)
  • Une référence sur la normalisation de Garside:
    Foundations of Garside theory, P. Dehornoy et al.
    EMS Tracts in Mathematics Volume 22 (2015)
  • Une référence sur les groupes d’automate:
    Self-similar Groups, V. Nekrashevych.
    AMS Mathematical Surveys and Monographs Volume 117 (2005)
  • Un chapitre sur les (semi)groupes d’automate:
    Automaton (semi)groups: Wang tilings and Schreier tries, I. Klimann, M. Picantin.
    Sequences, Groups, and Number Theory. V. Berthé M. Rigo (Eds) Trends in Mathematics (2018)
    https://www.irif.fr/~picantin/papers/chapitre10.pdf
  • L'article autour duquel ce cours s'articule:
    Automatic semigroups vs automaton semigroups, M. Picantin.
    46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
    http://drops.dagstuhl.de/opus/volltexte/2019/10700/pdf/LIPIcs-ICALP-2019-124.pdf
  • Un mémoire d'habilitation avec dessins et conjectures:
    Automates, (semi)groupes, dualités, M. Picantin.
    https://www.irif.fr/~picantin/papers/hdr_memoire.pdf (2017)


Informations complémentaires

Équipe pédagogique

D. Petrisan MC Paris 7 IRIF
M. Picantin MC HDR Paris 7 IRIF
A. Pouly CR CNRS IRIF
S. van Gool MC Paris 7 IRIF

 
Universités partenaires Université Paris-Diderot
Université Paris-Saclay
ENS Cachan École polytechnique Télécom ParisTech
ENS
Établissements associés Université Pierre-et-Marie-Curie CNRS INRIA CEA