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

Cours-MPRI.2.16-2018-2019

2.16. Modèles de calcul et automates finis (48h, 6 ECTS)

Responsable : Thomas Colcombet

Équipe pédagogique : Thomas Colcombet, Daniela Petrisan, Matthieu Picantin et Amaury Pouly.

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 fonctions régulières de coût proposent une autre théorie cohérente impliquant automates, algèbre et logique, et permettant de manipuler des quantités. Son objectif est l'établissement systématique de résultats d'existence de bornes.
  • 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).
  • 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 automates finis probabilistes forment une autre 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.

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

  1. Fonctions régulières de coût (15h + 3h TD, Thomas Colcombet)
  2. Semi-groupes et automates (9h + 3h TD, Matthieu Picantin)
  3. Automates probabilistes et chaînes de Markov (9h + 3h TD, Amaury Pouly)
  4. Automates finis à multiplicité et transducteurs (15h + 3h TD, Daniela Petrisan)

Planning

Le cours a lieu les mardi de 12h45 à 15h45 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.

Pour des raisons d'organisation, la première séance sera un cours de rappel des prérequis de théorie des automates, facultatif mais fortement recommandé et la dernière séance de travaux dirigés de la première période aura lieu la première semaine de la première période d'examen.

Langue du cours

Tous les intervenants feront cours a priori en français.

Si des étudiants non francophones le demandent, le cours aura lieu en anglais. Des supports en anglais seront distribués 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
10 Sept. Fonctions régulières de coût (1) Colcombet
17 Sept. pas de cours
24 Sept. Fonctions régulières de coût (2) Colcombet
1 Oct. Fonctions régulières de coût (3) Colcombet
8 Oct. Fonctions régulières de coût (4) Colcombet
15 Oct. Fonctions régulières de coût (5) Colcombet
22 Oct. Semi-groupes et automates (1) Picantin
29 Oct. Semi-groupes et automates (2) Picantin
5 Nov. Semi-groupes et automates (3) Picantin
12 Nov. Semi-groupes et automates (TD) Picantin
19 Nov. pas de cours
26 Nov. Examen (1)

 Date  Contenu Enseignant
3 Déc. Automates probabilistes et chaînes de Markov (1) Pouly
10 Déc. Automates probabilistes et chaînes de Markov (2) Pouly
17 Déc. Automates probabilistes et chaînes de Markov (3) Pouly
7 Janv. Automates probabilistes et chaînes de Markov (TD) Pouly
14 Janv. Automates à multiplicité et transducteurs (1) Petrisan
21 Janv. Automates à multiplicité et transducteurs (2) Petrisan
28 Janv. Automates à multiplicité et transducteurs (3) Petrisan
4 Fév. Automates à multiplicité et transducteurs (4) Petrisan
11 Fév. Automates à multiplicité et transducteurs (5) Petrisan
18 Fév. Automates à multiplicité et transducteurs (TD) Petrisan
25 Fév. pas de cours
3 Mars Examen (2)


Description détaillée du cours

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

Fonctions régulières de coût (Thomas Colcombet)

Les automates à coûts sont des automates finis équipés de compteurs que l'on peut remettre à zéro ou incrémenter. Un tel automate associe à  chaque mot une valeur entière, son coût. Dans le cas des B-automates (l'une des formes d'automates à coût) il s'agit du minimum sur toutes les exécutions de la valeur maximale prise par les compteurs au cours de cette exécution. Le problême central que l'on cherche à résoudre sur ce type d'automates est la "limitedness". Il s'agit de décider, étant donné un B-automate, si la fonction qu'il calcule est bornée.

Différents problèmes difficiles en théorie des langages se réduisent au problème de la "limitedness":

  • La puissance finie: étant donné un langage régulier L, décider si L^n = L^* pour un certain entier n.
  • La substitution finie: étant donnés deux langages réguliers L, K, décider s'il existe une substitution s associant à chaque lettre un langage fini, telle que s(L)=K,
  • La hauteur d'étoile: étant donnés un langage régulier L et un entier k, décider si l'on peut exprimer L au moyen d'une expression régulière utilisant au plus k imbrications d'étoiles de Kleene.

Au cours de cette partie du cours nous verrons:

  • définitions des B-automates et de leur variante hiérarchique, exemples, propriétés de clôture, expressions B-régulières, équivalences des modèles,
  • modèle algébrique, stabilisation, et décidabilité du problème de la "limitedness",
  • l'une des applications citées ci-dessus,
  • d'autres modèles (en particulier les S-automates, dont le comportement est dual à celui des B-automates),
  • liens avec la logique.

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ématiques restaient essentiellement distantes depuis 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.
    http://arxiv.org/abs/1609.09364 (2016)
  • 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)

Sujets d'examen

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 probabilistes et chaînes de Markov (Amaury Pouly)

Les automates finis probabilistes (AFP) sont une généralisations 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 un état est accessible avec probabilité 0.5 ou plus reste difficile. Pour cela, nous montrerons le lien entre 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'information ici.

Informations complémentaires

Équipe pédagogique

Th. Colcombet DR CNRS IRIF
D. Petrisan MC Paris 7 IRIF
M. Picantin MC HDR Paris 7 IRIF
A. Pouly CR CNRS 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