Bibliographie References

J'utilise mon livre Elements of Automata Theory (Cambridge University Press, 2009) comme texte de base pour toutes les références aux sections et exercices ci-dessous. On y trouvera, ainsi que dans les notes de cours, des références bibliographiques.

As a background, I use my book Elements of Automata Theory (Cambridge University Press, 2009) for all references to sections and exercices below.

Ce livre est la version anglaise corrigée de Eléments de théorie des automates (Vuibert, 2003) où les mêmes références peuvent être trouvées également. Mais cet ouvrage est épuisé et, de toutes façons, doit être accompagné d'un erratum dont la dernière version est malheureusement loin d'être à jour.

This book is the corrected English translation of Eléments de théorie des automates (Vuibert, 2003) where the same references are to be found as well. But this book is out of print now, and it should anyhow be accompanied by an errata, the last version of which is far from being up to date.

Une version plus récente d'une partie des chapitres III et IV de Elements of Automata Theory et qui couvre l'essentiel de ce cours a été écrite pour le chapitre 4 du Handbook of Weighted Automata publié par Springer en 2009. Par autorisation spéciale, une copie de ce chapitre, réécrit avec les notations utilisées dans le cours peut être trouvée ici à la condition de ne pas être redistribuée.

A more recent version of a part of Chapter III of EAT has been written for Chapter 4 of the Handbook of Weighted Automata published by Springer in 2009. By special authorisation, a copy of this chapter, rewritten with the notation used in the lectures, is to be found here under the condition it will not be further distributed.

Notes de cours Lecture notes

Des notes de cours, ainsi que des feuilles d'exercices, accompagnent chaque leçon.

Lecture notes, as well as exercise sheets, are available for every lecture.

Prérequis Prerequisite

Même si le cours est autosuffisant et si toutes les notions utilisées seront redéfinies, on attend des étudiants une certaine familiarité avec la théorie «élémentaire» des automates finis. Ils pourront la vérifier en faisant un petit test.

Even though the course is self-contained and every used notion will be defined, students are expected to have some familiarity with basic finite automata theory. They can test it by answering these few questions.

Plan des leçons Lecture outline

Les cinq séances sont réparties en deux séquences. la première porte sur les automates à multiplicité, la seconde sur les transducteurs.

Le plan qui suit est seulement indicatif, et sans doute très optimiste. Il se peut fort bien que tous les sujets ne soient pas traités.

Cette partie de la page sera mise à jour après chaque séance (en tous cas c'est mon intention) pour garder la trace de ce qui aura effectivement été traité en cours.

PartiePart 1.— Automates finis à multiplicité. Weighted finite automata.

LeçonLecture I     —     5/12/18.     Rationalité et reconnaissabilité. Rationality and recognisability.

Cette leçon a pour objectifs:
(i) d'introduire, ou de rappeler, les notions d'automate à multiplicité et de représentation qui sont les sujets des cours suivants;
(ii) de donner la preuve de leur équivalence dans le cas des monoïdes libres;
(iii) et de fixer la terminologie et les notations.

The aims of this lectures are:
(i) to introduce, or to recall, the notions of weighted automata and of representations which will be the subjects of the following lectures;
(ii) to give the proof of their equivalence in the case of free monoids;
(iii) and to fix the terminology and notation.

• Matière traitée Presented content

1. Le modèle des K-automates.     La définition par graphes.
2. The K-automaton model.     The graph definition.
3. Rationalité.     Séries rationnelles.   La description matricielle des K-automates.   Le théorème fondamental des automates finis (énoncé sans preuve).
4. Rationality.     Rational series.   The matrix description of K-automata.   The fundamental theorem of finite automata (statement without proof).
5. Reconnaissabilité.     Représentation et séries reconnaissables.   Le théorème de Kleene-Schützenberger.
6. Recognisability.     Representation and recognisable series.   Kleene-Schützenberger Theorem.
7. Produit de Hadamard.     Le théorème de Schützenberger.
8. Hadamard product.     Schützenberger Theorem.

• Notes de cours Lecture Notes   Lecture I   (en anglais)(in English).   Version 7/12/18

• Feuille d'exercices Exercise sheet   Exercises I   (en anglais)(in English).   Version 2/12/18

• Transparents traitant du sujet de cette leçon: Sets of slides dealing with the topics of this lecture:
   Rationality, pp.1-107 etand Recognisability, pp.1-31, deux tutoriels sur les automates à multiplicité two tutorials on weighted automata   (en anglais)(in English).

 

LeçonLecture II     —     12/12/18.     Morphismes. Morphisms.

Dans cette leçon, on va traiter du problème suivant: étant donné un automate A, trouver un automate B plus petit qui garde la même structure, c'est à dire tel qu'il y a une correspondance entre les calculs de l'un et ceux de l'autre.

En fait, l'opération inverse sera au moins aussi intéressante: étant donné A, trouver B, plus gros, mais dans lequel les calculs sont moins enchevêtrés de telle sorte qu'ensuite, par d'autres opérations, on puisse faire des choix parmi ces calculs.

In this lecture, we tackle the following problem: given an automaton A, find a smaller automaton B which keeps the same structure, that is, such that there is a correspondence between the computations of the former and those of the latter.

The inverse construction will be indeed as interesting: given an automaton A, find a larger automaton B the computations of which are in correspondence with those of A but less entangled in such a way that it is then possible to make choices between them, by means of other operations.

• Matière traitée Presented content

1. Morphismes d'automates booléens.     Le cas des automates déterministes.   Le cas des automates (booléens) généraux.  
2. Morphisms of Boolean automata.     The case of deterministic automata.   The case of general Boolean automata.  
3. Propriétés locales des morphismes.   Le revêtement de Schützenberger.
4. Local properties of morphisms.   The Schützenberger covering.
5. Morphismes d'automates à multiplicité.     Conjugaison.   Out-morphismes, In-morphismes.   Quotient minimal.
6. Morphisms of weighted automata.     Conjugacy.   Out-morphisms, In-morphisms.   Minimal quotient.

• Notes de cours Lecture Notes   Lecture II   (en anglais)(in English).   Version 14/12/18

• Feuille d'exercices Exercise sheet   Exercises II   (en anglais)(in English).   Version 7/12/18

 

LeçonLecture III   —    19/12/18.     Réduction. Reduction.

Etant donné un automate à multiplicité, on veut construire un automate équivalent de dimension inférieure, si possible de dimension minimale. Dans cette leçon, on va fonder cette construction sur le comportement de l'automate, par opposition à la leçon précédente où on avait traité le même problème, mais en voulant préserver la structure des calculs.

Given a weighted automaton, we want to construct an equivalent automaton of smaller dimension, of minimal dimension if possible. In this lecture, the construction will be based on the behaviour of the automaton, in contrast with the previous lecture where we addressed the same problem, but with the constraint of keeping the structure of the computations.

• Matière traitée Presented content

1. Action d'un monoïde sur un ensemble.
2. Action of a monoid on a set.
3. Commande.     Ensemble d'accessibilité.   Espace d'états   Commandabilité.
4. Control.     Accessibility set.   State space   Controlability.
5. Observation.     Quotient de séries.   Morphisme d'observation. Stabilité.  Observabilité.
6. Observation.     Quotient of a series.   Observation morphism.   Stability.   Observability.
7. Réduction d'une representation dans un corps (gauche)     Rang d'une série.   Représentation réduite.  
8. Reduction of a representation in a (skew) field.     Rank of a series.   Reduced representation.  

• Notes de cours Lecture Notes   Lecture III   (en anglais)(in English).   Version 13/12/18

• Feuille d'exercices Exercise sheet   Exercises III   (en anglais)(in English).   Version 13/12/18

• Transparents traitant du sujet de cette leçon: Sets of slides dealing with the topics of this lecture:   Recognisability, (cf. ci-dessus, pp.32-99, en anglais). (cf. above, pp.32-99, in English).

• Document relatif au sujet de cette leçon: Document related to the topics of this lecture:
   EAT IV.7, Séries de Malcev—Neumann (pour prouver la décidabilité de l'équivalence des transducteurs déterministes à k bandes). Malcev—Neumann series (for establishing the decidability of equivalence of deterministic k-tape transducers) equivalence.

 

PartiePart 2.— Transducteurs. Transducers.

Les transducteurs, ou automates avec sortie (dans un monoïde libre) peuvent être vus de deux points de vue différents: comme des automates booléens sur des produits directs de monoïdes libres (monoïde non libre) ou comme des automates sur un monoïde libre à multiplicité dans les langages, ou séries, rationnelles sur un monoïde libre. La spécificité du monïde de base d'une part, de la "multiplicité" d'autre part, donne lieu à des développements bien particuliers.

Transducers, or automata with output (in a free monoid), can be seen from two distinct points of view: either as automata over direct products of free monoids (which are non free monoids) or as weighted automata over a free monoid whose weights are rational languages or more generally rational series. The specificity of the base monoid on one hand side, of the weights on the other, gives rise to very particular results.

LeçonLecture IV     —     9/01/19.     Transducteurs (1) – Réalisation par automates. Transducers (1) – Realisation by automata.

• Matière traitée Presented content

• (Suite et fin de la leçon III)
• (Lecture III continued and concluded)

1. Calcul effectif des représentations réduites.
2. Effective computation of reduced representations.
3. Décidabilité de l'équivalence des séries reconnaissables.
4. Decidability of the equivalence of recognisable series.

• Leçon IV
• Lecture IV

1. Relations entre mots réalisées par automates. Définition et exemples. Relations rationnelles.
2. Word relations realised by automata. Definition and examples. Rational relations.
3. Bonnes et mauvaises nouvelles.
4. Good news, bad news.
5. Résultats d'indécidabilité.
6. Undecidability results.
7. Composition des relations rationnelles.
8. Composition of rational relations.

• Notes de cours Lecture Notes   Lecture IV   (en anglais)(in English).   Version 01/01/19

LeçonLecture V     —     16/01/19.     Transducteurs (2) – Réalisation par représentations. Transducers (1) – Realisation by representations.

• Matière prévue Planned content :

1. Réalisation des relations rationnelles par représentations. Théorème de Kleene-Schützenberger. Théorème de composition.
2. Realisation of rational relations by representations. Kleene-Schützenberger Theorem. Composition Theorem.
3. Uniformisation des relations rationnelles.
4. Uniformisation of rational relations.
5. Relations rationnelles fonctionnelles. Relations rationnelles séquentielles.
6. Functional rational relations. Sequential relations.

• Notes de cours Lecture Notes   Lecture V   (en anglais)(in English).   Version 15/01/19 (corrections à la version du 10/01/19)(typo corrections to 10/01/19 version).

Travaux dirigésTutorial class B     —     23/01/19.    

• Feuille d'exercices Exercise sheet   RecueilCollection des exercices des leçons I à V. of exercises from lectures I to V.   —   Version 23/01/19
                                     avecwith correction (tous les exercices ne sont pas corrigés; les corrections sont en français). (not all exercices are given solution; solutions are in French).

Documentation

• Notes de cours Lecture Notes   RecueilCollection des notes pour les leçons I à V. of lectures notes I to V.   —   Version 23/01/19

Annales des partiels des années précédentes. Record of exams from past years.

N.B. La plupart des questions posées dans ces partiels ont été traitées comme des exercices dans les cours ou les travaux dirigés. Most of the questions asked in these exams appear in the exercise sheets.

• 2017—2018   ExamenWritten exam (en français)(in French),    (en anglais)(in English).
• 2014—2015   ExamenWritten exam (en français)(in French),    avecwith correction.
• 2013—2014   ExamenWritten exam (en français)(in French),    avecwith correction.
• 2012—2013   ExamenWritten exam (en français)(in French),    (en anglais)(in English).
• 2011—2012   ExamenWritten exam (en français)(in French).
• 2010—2011   ExamenWritten exam (en français)(in French),    (en anglais)(in English),    avecwith correction (en français)(in French).