Machines d'Eilenberg effectives
Institution:
Paris 7Disciplines:
Directors:
Abstract EN:
Automata theory bas been developed to overcome both theoretical and practical problems. Nowadays, automata are considered as basic knowledge by all computer scientists, and they are used in most softwares. In 1974, Samuel Eilenberg gave a new machine model unifying the most common automata such as transducers, pushdown automata, and even Turing machines. Eilenberg machines also have an interesting modularity property that is useful for applications modeled using different levels of automata; as may appear in computational linguistics. We propose an effective design of Eilenberg machines and study simulation techniques. Our Simulator is defined by a functional program that progressively enumerates solutions, exploring a research space according to various of strategies. We introduce the notion of finite Eilenberg machines, and formally prove the correction of the underlying simulation engine. The control component of an Eilenberg machine is defïned by a non-deterministic automaton; in this context, regular expressions may be used as syntax describing the automaton. In recent years, the concept of Brzozowski's derivatives has led to many novel and efficient algorithms that compile regular expressions into non-deterministic automata. We review these state of the art algorithms, give an efficient OCaml implémentation, and compare their efficiency in a common framework.
Abstract FR:
La théorie des automates est apparue pour résoudre des problèmes aussi bien pratiques que théoriques, et ceci dès le début de l'informatique. Désormais, les automates font partie des notions fondamentales de l'informatique, et se retrouvent dans la plupart des logiciels. En 1974, Samuel Eilenberg proposa un modèle de calcul qui unifie la plupart des automates (transducteurs, automates à pile et machines de Turing) et qui a une propriété de modularité intéressante au vu d'applications reposant sur différentes couches d'automates ; comme cela peut être le cas en linguistique computationnelle. Nous proposons de rendre effectif ce modèle en étudiant des techniques de simulation. Le simulateur est défini par un programme fonctionnel énumérant progressivement les solutions en explorant un espace de recherche selon différentes stratégies. Nous introduisons la notion de machines d'Eilenberg finies pour lesquelles nous fournissons une preuve formelle de correction de la simulation. La composante de contrôle d'une machine d'Eilenberg est un automate fini non-déterministe; dans ce contexte, on peut utiliser une expression régulière comme syntaxe pour décrire cet automate. Récemment, un ensemble de travaux approfondissant la notion de dérivées de Brzozowski, a été la source d'algorithmes efficaces de synthèse d'automates non-déterministes à partir d'expressions régulières. Ces algorithmes sont de nature algébrique et nous en faisons un état de l'art, tout en donnant une implémentation en OCaml permettant de les comparer les uns aux autres dans un cadre commun.