Objectifs
Les automates finis sont le modèle le plus simple de machines, de machines qui calculent, le premier dans la hiérarchie des 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.
L'objectif est d'élargir le champ de la théorie des automates finis, enrichis par la notion de multiplicité. Ils constituent alors un modèle assez puissant pour exprimer des propriétés non triviales et sont utilisés comme outil dans des domaines aussi variés que le traitement de l'information, le traitement des langues naturelles, la combinatoire sur les mots, la vérification de systèmes et des protocoles, etc.. Les problèmes rencontrés dans chacun de ces domaines, une fois correctement formalisés, relèvent souvent de la théorie des automates et ne se heurtent pas immédiatement au mur de l'indécidabilité: il y a de l'espace pour des résultats profonds. Ainsi, cette théorie est-elle un chapitre de base de l'informatique; elle le structure, elle l'organise; la connaître permet de s'y orienter.
La théorie classique, ou plutôt élémentaire, des automates finis traite d'automates qui acceptent, ou n'acceptent pas, des mots. Dans ce cours nous allons être à la fois plus précis et plus général. Plus précis car nous allons compter les calculs qui font qu'un mot est accepté par l'automate. Plus général parce qu'on ne va pas s'en tenir là et si on compte les calculs, on peut aussi bien affecter chaque transition de l'automate d'une sortie qui peut être un coefficient ou un mot (ou un ensemble de mots). En faisant varier le type de la sortie, on va décrire une variété de situations --- des plus courts chemins d'un graphe aux systèmes à événements discrets en passant par l'ambiguïté des grammaires ou les relations entre mots --- qui couvrent le champ de l'informatique. Dans tous les cas, le cadre mathématique commun permettra de traiter d'un même mouvement des propriétés qui paraissaient distinctes, révélera des parentés, suggérera des méthodes.
Un des objectifs de ce cours est de présenter les bases théoriques et des résultats qui sont utilisés dans de nombreux autres cours du master.
Programme et organisation
Plan du cours et intervenants prévus pour 2010-2011
- Automates à coûts
(18h, Thomas Colcombet)
- Classification des transductions. (15h,
Christian Choffrut)
- Automates finis avec multiplicité.
(15h, Jacques Sakarovitch)
Planning
Chaque séance comprendra (en gros) 2 heures de cours et 1 heure consacrée à des exercices.
Les séances de Travaux dirigés seront essentiellement consacrées à des exercices; les compléments qui pourront y être abordés ne seront pas au programme des examens.
| Date |
Contenu |
Enseignant |
| 17 Sept. |
Automates à coûts I
|
Colcombet |
| 24 Sept. |
Automates à coûts II
|
Colcombet |
| 1 Oct. |
Automates à coûts III
|
Colcombet |
| 8 Oct. |
Automates à coûts IV
|
Colcombet |
| 15 Oct. |
Automates à coûts V
|
Colcombet |
| 22 Oct. |
Travaux dirigés facult. A
|
Colcombet |
| 29 Oct. |
Classification des relations I
|
Choffrut |
| 5 Nov. |
Classification des relations II
|
Choffrut |
| 12 Nov. |
Classification des relations III
|
Choffrut |
| 19 Nov. |
Classification des relations IV
|
Choffrut |
| 26 Nov. |
Relâche
|
|
| 3 Déc. |
Examen (1)
|
|
| 10 Déc. |
Classification des relations V
|
Choffrut |
| 17 Déc. |
Relâche
|
|
| 7 Jan. |
Automates avec multiplicité I
|
Sakarovitch |
| 14 Jan. |
Automates avec multiplicité II
|
Sakarovitch |
| 21 Jan. |
Automates avec multiplicité III
|
Sakarovitch |
| 28 Jan. |
Travaux dirigés facult. B
|
Sakarovitch |
| 4 Fév. |
Automates à coûts VI
|
Colcombet |
| 11 Fév. |
Automates avec multiplicité IV
|
Sakarovitch |
| 18 Fév. |
Automates avec multiplicité V
|
Sakarovitch |
| 25 Fév. |
Travaux dirigés facult. C
|
Sakarovitch |
| 4 Mars |
Travaux dirigés facult. D
|
Colcombet |
| 11 Mars |
Examen (2)
|
|
Langue du cours
Le cours est donné a priori en français, mais si des étudiants non francophones le demandent,
le cours aura lieu en anglais.
Contrôle des connaissances
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.
Description du cours
Nous étudierons trois variantes des automates finis qui permettent d'enrichir leurs capacités
modélisatrices:
les automates à coûts,
les automates sur des produits cartésiens de monoïdes libres, qui réalisent des relations entre mots,
et les automates à multiplicité.
Automates à coûts (Thomas Colcombet)
p&
Dans la partie précédente de ce cours, nous avons vu comment il était possible
de rendre quantitatifs des automates en les enrichissant de multiplicités.
Cette partie du cours sera l'occasion de présenter une autre variante
quantitative des automates finis.
-->
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.
Classification des relations entre mots réalisées par automate fini (Christian Choffrut)
On s'intéresse aux relations d'arité quelconque entre mots, c'est-à-dire
aux ensembles de $n$-uplets de mots, ou dit encore autrement aux
sous-ensembles d'un produit cartésien de monoïdes libres.
Thèmes abordés:
- Généralités sur les familles de parties rationnelles et reconnaissables d'un produit cartésien de monoïdes libres. Il s'agit en particulier de voir les limites de l'extension de la théorie classique: que devient l'équivalence entre automates finis et langages rationnels?
- Etude de sous-familles particulières de relations rationnelles. En ordre d'inclusion décroissante: déterministes, synchrones, spéciales. Dans ces deux derniers cas on montrera que les familles sont exactement les modèles de structures dans des logiques très naturelles.
- Le cas où les composantes du produit cartésien sont toutes isomorphes au monoïde additif des entiers positifs nécessite un traitement particulier. Nous donnerons une caractérisation algébrique des sous-ensembles rationnels et démontrerons que ce sont exactement les ensembles définissables dans la logique de Presburger. Nous évoquerons les problèmes de complexité.
Quelques
notes de cours. Voir aussi ma
page oueb .
Automates finis avec multiplicité (Jacques Sakarovitch)
Après la généralisation des définitions de base des automates aux automates avec multiplicité, en particulier le 'théorème fondamental des automates finis', on traitera successivement des points principaux suivants:
- Séries reconnaissables et théorème de Kleene-Schützenberger. Réduction de la représentation des séries reconnaissables sur un corps.
- Morphismes, quotients et revêtements d'automates avec multiplicité (bisimulation des systèmes de transitions). Conjugaison et équivalence pour les automates sur Z et N .
- Revêtements d'automates. Revêtement de Schützenberger, revêtement lexicographique. Théorème du paludier.
- Fonctions rationnelles. Uniformisation des relations rationnelles. Théorème de structure des fonctions rationnelles.
- Séquentialité. Algorithme universel de séquentialisation. Décidabilité et non décidabilité de la séquentialité.
N.B. Le cours 'Automates à coût VI' sera consacré à l'exposé de l'indécidabilité de l'équivalence des automates à multiplicité dans (N,min,+) -- théorème de Krob -- qui vient naturellement après les premiers cours sur les automates à multiplicité où sera établi, entre autres, la décidabilité de l'équivalence des automates à multiplicité dans un corps.
Prérequis
Théorie élémentaire des automates finis: théorème de Kleene, déterminisation, minimisation, expressions régulières.
Informations complémentaires
Bibliographie
- Jacques Sakarovitch,
Éléments de théorie des automates,
Vuibert, 2003.
Il est fortement conseillé de télécharger
la liste d'errata,
malheureusement assez longue.
Une version anglaise, et corrigée: Elements of Automata Theory, Cambridge, 2009, est également disponible.
Des exemplaires de cet ouvrage, en français, ou en anglais, pourront être prêtés aux étudiants pour l'année.
Liens sur les pages web des années précédentes
Equipe pédagogique
| Ch. Choffrut | PU | Paris 7 | LIAFA |
| Th. Colcombet | CR | CNRS | LIAFA |
| J. Sakarovitch | DR | CNRS | ENST |
