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

Cours-MPRI.2.16-2021-2022

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 2021-2022

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

Attention, en raison du lundi 13/09 banalisé et du lundi 01/11 férié, il y aura un léger décalage. En particulier, l'examen pour la première période est programmé le lundi suivant les deux semaines normalement réservées. Voir le calendrier détaillé ci-dessous.

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

Calendrier des cours

 Date  Contenu Enseignant
20 Sept. Automates à multiplicité et transducteurs (1) Petrisan
27 Sept. Automates à multiplicité et transducteurs (2) Petrisan
04 Oct. Automates à multiplicité et transducteurs (3) Petrisan
11 Oct. Automates à multiplicité et transducteurs (4) Petrisan
18 Oct. Automates à multiplicité et transducteurs (TD) Petrisan
25 Oct. Automates, monoïdes, et logique (1) van Gool
01 Nov. pas cours
08 Nov. Automates, monoïdes, et logique (2) van Gool
15 Nov. Automates, monoïdes, et logique (3) van Gool
22 Nov. Automates, monoïdes, et logique (4) van Gool
29 Nov. Automates, monoïdes, et logique (TD) van Gool
06 Déc. Examen (1)

 Date  Contenu Enseignant
13 Déc. Automates probabilistes et chaînes de Markov (1) Pouly
03 Janv. Automates probabilistes et chaînes de Markov (2) Pouly
10 Janv. Automates probabilistes et chaînes de Markov (3) Pouly
17 Janv. Automates probabilistes et chaînes de Markov (4) Pouly
24 Janv. Automates probabilistes et chaînes de Markov (TD) Pouly
31 Janv. Automates, semigroupes, dualité (1) Picantin
07 Fév. Automates, semigroupes, dualité (2) Picantin
14 Fév. Automates, semigroupes, dualité (3) Picantin
21 Fév. Automates, semigroupes, dualité (4) Picantin
28 Fév. Automates, semigroupes, dualité (TD) Picantin
07 Mars Examen (2)


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 will be based on selected chapters from the two books below; references to precise sections will be made available on this page as the course progresses.



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)


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