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

Cours-MPRI.2.16-2022-2023

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 à 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 monoïdes finis et la logique monadique de second ordre permettent d'adopter un point de vue algébrique et logique sur les automates et leurs langages.
  • 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 semigroupes d'automates et les semigroupes automatiques sont des semigroupes 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 2022-2023

  1. Automates finis à multiplicité et transducteurs (12h + 3h TD, Daniela Petrisan)
  2. Automates, monoïdes, et logique (12h + 3h TD, Sam van Gool)
  3. Automates probabilistes et chaînes de Markov (12h + 3h TD, Amaury Pouly)
  4. Automates, semigroupes, dualité (12h + 3h TD, Matthieu Picantin)

Planning

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

Sam 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é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.2 Algorithmic verification of programs
  • 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.

Calendrier des cours

 Date  Contenu Enseignant
14 Sept. Automates à multiplicité et transducteurs (1) Petrisan
21 Sept. Automates à multiplicité et transducteurs (2) Petrisan
28 Sept. Automates à multiplicité et transducteurs (3) Petrisan
5 Oct. Automates à multiplicité et transducteurs (4) Petrisan
12 Oct. Automates à multiplicité et transducteurs (TD) Petrisan
19 Oct. Automates, monoïdes, et logique (1) van Gool
26 Oct. Automates, monoïdes, et logique (2) van Gool
2 Nov. Automates, monoïdes, et logique (3) van Gool
9 Nov. Automates, monoïdes, et logique (4) van Gool
16 Nov. Automates, monoïdes, et logique (TD) van Gool
30 Nov. Examen (1/2) Petrisan/van Gool
 Date  Contenu Enseignant
07 Déc. Automates probabilistes et chaînes de Markov (1) Pouly
14 Déc. Automates probabilistes et chaînes de Markov (2) Pouly
04 Janv. Automates probabilistes et chaînes de Markov (3) Pouly
11 Janv. Automates probabilistes et chaînes de Markov (4) Pouly
18 Janv. Automates probabilistes et chaînes de Markov (TD)
25 Janv. Automates, semigroupes, dualité (1) Picantin
01 Fév. Automates, semigroupes, dualité (2) Picantin
08 Fév. Automates, semigroupes, dualité (3) Picantin
15 Fév. Automates, semigroupes, dualité (4) Picantin
22 Fév. Automates, semigroupes, dualité (TD)
01 Mars Examen (2/2)
Pouly/Picantin

Description détaillée du cours

Les 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.
Lecture notes summarizing this part's contents.

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.

  • La première partie traitera des notions de formes normales et d’automaticité dans les semigroupes: nous examinerons plusieurs constructions et étudierons le cas des formes normales quadratiques.
  • La deuxième partie sera consacrée aux semigroupes d’automates: des outils différents, des questions différentes mais, toujours, des exemples de semigroupes aux propriétés remarquables.
  • La troisième partie permettra d’établir une possible connexion entre « être un semigroupe automatique » et « être un semigroupe 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)

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

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