To: seminaire-gallium-moscova@inria.fr
From: Francois.Pottier@inria.fr
Subject: SEM - INRIA : Gallium - 23/11/07 - Paris - FR

           Vous pouvez vous abonner à nos annonces de séminaires
                    http://pauillac.inria.fr/seminaires/

                             S E M I N A I R E
       __                                  
      / _`  _   /  /  o                       /| /|   __  __  __ __    _  _
     /   ) __) /  /  / /  / /\/|    -----    / |/ |  /  )(_  /  /  ) ) ) __)
    (___/ (_/ (_ (_ / (__/ /   |            /     | (__/ __)(_ (__/ (_/ (_/
                                                
                          I N R I A - Rocquencourt
                         Amphi Turing du bâtiment 1

                         Vendredi 23 novembre, 14h

                                ------------
                                Benoît Razet
                                ------------

                                   INRIA

                      ===============================
                      Les machines d'Eilenberg finies
                      ===============================

Samuel Eilenberg introduisit en 1974 une notion de machine
généralisant aussi bien les automates finis, que les transducteurs,
les automates à piles, les machines de Turing. Ces dispositifs sont
utilisés traditionnellement pour résoudre des problèmes en théorie des
langages formels. Ce qui leur est commun est d'avoir un contrôle
représenté par un graphe orienté avec des étiquettes représentant des
opérations sur un espace de données (bandes, piles etc...). Une
machine d'Eilenberg consiste principalement en la donnée d'un graphe
(pour le contrôle) étiqueté par des relations au sens mathématique
(pour manipuler les données). Une telle machine définit une relation
de calcul qui peut se retrouver comme étiquette d'une autre machine,
c'est pour cette raison qu'on parle de modularité des machines
d'Eilenberg.

Le modèle calculatoire associé à de telles machines est général et
pose le problème de leur simulation à l'aide d'un langage de
programmation. Nous introduirons donc une restriction que nous
appellons "machines d'Eilenberg finies" pour lesquelles nous
fournissons un processus de simulation en ocaml inspiré de la machine
réactive de Gérard Huet. Cette simulation est prouvée correcte et
complète vis-à-vis de n'importe quelle machine d'Eilenberg finie.
Nous discuterons d'applications de telles machines autour d'exemples
empruntés aux automates et transducteurs rationnels.