LRDE Seminar : Vaucanson, 4 June 2003, EPITA

14h00 : DSL on Automata -- Loic Fosse^?

Keywords: automata, language conception, DSL, GPL, domain.

Abstract: For few years, Domain Specific Languages (DSL) has came back to foreground. These languages, which are built especially for a domain or a problem, can be a powerful alternative to General Purpose Language for their domain. Our problem is manipulating automata easily and quickly, in order to test algorithms, whether automaton is the goal or the tool of the algorithm. A DSL seems to be a good solution.

Two major points will be considered:

First, we will discuss about DSL in general. What are their weaknesses, their interest, why and when using one instead of standard languages like C++. A methodology for building such a language will be presented, illustrated by experiences given by MAL, our DSL concerning automata.

Next, MAL, our DSL dedicated to automaton manipulation, will be presented more precisely. Its syntax, its semantic was built in order to fit mathematical notations and way of thinking. It's one of links between MAL and Vaucanson, and others will be shown. But design and implementation are two distinct parts, and if the language is a powerful one, its implementation is consequently harder; so difficulties will be exposed to. Nevertheless, we hope MAL should become a powerful tool to test and manipulate automata. A usable one.

15h00 : Smart automaton implementations -- Thomas Claveirole^?

Keywords: Partial Determinization, Lazy Transition Evaluation, Regular Expression Search, Pattern Matching, Homogeneous Automaton, Navarro-Raffinot method, Bitset.

Abstract: Our aim is to present an overview of technics to optimize memory usage when constructing automaton from regular expressions. However, it is essential to keep a decent time complexity when processing text i.e. better than the classical O(l * n) [1] for non-deterministic automaton.

First, the notion of homogeneous automaton will be introduced and it will be shown that Glushkov's algorithm produces such automaton. Given the fact that a deterministic finite automaton (DFA) built from an homogeneous non-deterministic finite automaton (NFA) stays homogeneous, the Navarro-Raffinot method can then be used to decrease the amount of memory needed. Moreover, one can use partial determinization to tune the amount of memory and the time complexity of an automata. Combined with homogeneous automaton, it can lead to even better results. It is also possible to have a failsafe algorithm which decides by itself which parts of an automata to determinize, given a particular amount of memory, thus giving the fastest automaton inside a limited memory space. Those methods need an efficient bitset implementation.

Then, other technics will be discussed. Given an NFA, it is possible to build a lazy DFA, which transitions will be computed only when needed and stored in a cache. Another lazy method is to have a lazy construction of a DFA directly from a regular expression. It is even possible to perform pattern matching with a regular expression without building any automata ! The time and space complexity of those methods will be studied, and their advantages and drawbacks will be enlightened.

[1] With l the length of the text, and n the number of state.

16h00 : Mical, a grammar inference library -- Maxime Rey^?

Keywords: regular grammar inference, Vaucanson, incremental inference, lattice, RPNI

Abstract: Grammar Inference consist to infer a language from a set of words contain in this language, or not. In our particular case of regular grammar inference, the problem consist in fact to infer an automaton, due to the isomorphism between regular languages and finite state machine. Thanks to Vaucanson's power expression to automata's manipulation, it becomes possible to develop a library of regular grammar inference.

We will present Mical, a young library of regular grammar inference, whose aim is to make easier the writing of algorithms in this field. After a brief view of this library, we will interest first to present existing algorithms inside Mical (with and without negative sample). Different manipulations of the library will be exposed too.

Then we will explain by which reusable way the algorithms inside Mical are implemented, showing how Mical accomplish its aim : make it easier to implement regular grammar inference.

We will finish by a general consideration of Mical's actual situation, and of its future extensions.

Seminaire du LRDE : Vaucanson, 4 Juin 2003, EPITA

14h00 : Langage dédié sur les Automates -- Loic Fosse^?

Mots clefs: Automates, Conception de langage, DSL, GPL, Domaine.

Résumé: Depuis quelques années, les DSL ou Domain Specific Languages sont sur le devant de la scène. Ces langages, construits pour un domaine spécifique ou un problème donné, peuvent être une alternative puissante aux langages classiques, les GPL (General Purpose Language). Notre problème est de manipuler des automates facilement et rapidement, dans le but de tester des algorithmes les mettant en oeuvre. Concevoir un DSL semble une bonne solution.

Dans un premier temps, ce seront les DSL en général qui seront abordés. Quels sont leur intérêts, leur défauts, quand les utiliser à la place de langages plus standard comme le C++. Une méthodologie de conception sera exposée, illustrée par notre expérience dans la création de MAL, notre DSL sur les automates. Enfin MAL sera présenté plus en détails, avec sa syntaxe, sa sémantique, et sa philosophie qui colle le plus possible à celle mathématique. Mais plus un langage est puissant, plus son implémentation risque de l'être, et les points critiques de la construction de son interpréteur seront abordés. Nous verrons enfin quel avenir pourra être celui de MAL.

15h00 : Implémentations d'automates efficaces -- Thomas Claveirole^?

Mots clefs: Déterminisation partielle, Évaluation paresseuse de transition, Recherche d'expressions rationnelles, Pattern matching, Automate homogène, Méthode Navarro-Raffinot, Bitset.

Résumé: Le but de cet exposé est de présenter quelques techniques pour optimiser la quantité de mémoire nécessaire lors de la construction d'un automate à partir d'expressions rationnelles. Toutefois, il est essentiel de conserver au final une complexité en temps raisonnable, c'est à dire meilleure que le traditionnel O(l * n) [1] des automates non-déterministes.

D'abord nous introduirons la notion d'automates homogènes, et nous montrerons que l'algorithme de Glushkov produit de tels automates. Puisqu'un automate fini déterministe (AFD) obtenu à partir d'un automate fini non-déterministe (AFN) conserve son homogénéité, il est possible d'utiliser la méthode Navarro-Raffinot pour diminuer l'espace mémoire nécessaire.

D'un autre coté, il est possible de déterminiser partiellement un automate, et de trouver un compromis entre sa vitesse et la taille qu'il va prendre. Cette méthode, combinée avec des automates homogènes, donne des résultats encore meilleurs. En particulier, il est possible d'avoir un algorithme qui n'échoue jamais et qui calcule automatiquement quelles parties déterminiser pour avoir un automate le plus rapide possible étant donnée une certaine quantité limitée de mémoire. Toutes ces techniques nécessitent une implémentation efficace de bitset.

Par la suite d'autres méthodes seront étudiées. A partir d'un AFN, il est possible de construire un AFD paresseux, dont les transitions ne seront évaluées que lorsqu'on en a besoin, et stockées dans un cache. Une autre méthode paresseuse construit directement un AFD depuis une expression rationnelle. Il est même possible de rechercher des expressions rationnelles dans un texte sans même construire d'automates !

Les complexités en temps et en taille de toutes ces méthodes seront étudiées, et nous mettrons en évidence les avantages et les inconvénients de ces techniques.

[1] Avec l la taille du texte d'entrée et n le nombre d'états.

16h00 : Mical, une bibliothèque d'inférence grammaticale -- Maxime Rey^?

Mots clefs: Inférence Grammaticale Régulière, Vaucanson, pattern, treillis, inférence incrémentale, RPNI

Résumé: L'inférence grammaticale consiste à inférer un langage à partir de mots appartenant à ce langage, ou non. Dans le cas particulier de l'inférence grammaticale régulière, le problème revient à inférer un automate, par isomorphisme des langages réguliers et des automates à états finis. Disposant d'une bibliothèque puissante pour la manipulation des automates, Vaucanson, il devient dès lors envisageable de développer une bibliothèque d'inférence grammaticale régulière.

Nous présenterons Mical, une jeune bibliothèque d'inférence grammaticale régulière ayant pour but de faciliter l'écriture d'algorithmes dans ce domaine. Après un bref aperçu de la bibliothèque, nous nous soucierons tout d'abord de présenter les algorithmes proposés au sein de Mical (avec et sans échantillon négatif). Les différentes manipulations qu'elle permet seront aussi abordées.

Puis nous exposerons par quel mécanisme réutilisable les algorithmes de Mical sont implémentés, révélant ainsi comment Mical rempli son objectif : faciliter l'implémentation d'algorithmes en inférence grammaticale régulière.

Nous terminerons par une considération globale de la situation actuelle de Mical, et de ses extensions futures.

Reports and Slides

Reports and Slides are available from their own pages.

Reports

Thomas Claveirole. Smart Automaton Implementations. CSI Seminar 0304 May 2003

Loïc Fosse. Domain specific language on automata: Design and Implementation problems. CSI Seminar 0305 June 2003

Slides

Thomas Claveirole. Smart Automaton Implementations. CSI Seminar May 2003

Maxime Rey. Mical, a grammar inference library. CSI Seminar

Loïc Fosse. Domain Specific Language on automata. CSI Seminar 4 June 2003
to top