Akim Demaille

Derived-term automata of multitape expressions with composition

By Akim Demaille

2017-12-29

In Scientific Annals of Computer Science

Abstract Rational expressions are powerful tools to define automata, but often restricted to single-tape automata. Our goal is to unleash their expressive power for transducers, and more generally, any multitape automaton; for instance $(a^+\mathbin{\vert} x + b^+\mathbin{\vert} y)^*$. We generalize the construction of the derived-term automaton by using expansions. This approach generates small automata, and even allows us to support a composition operator.

Continue reading

Derived-term automata of weighted rational expressions with quotient operators

By Akim Demaille, Thibaud Michaud

2017-07-05

In Proceedings of the thirteenth international colloquium on theoretical aspects of computing (ICTAC)

Abstract Quotient operators have been rarely studied in the context of weighted rational expressions and automaton generation—in spite of the key role played by the quotient of words in formal language theory. To handle both left- and right-quotients we generalize an expansion-based construction of the derived-term (or Antimirov, or equation) automaton and rely on support for a transposition (or reversal) operator. The resulting automata may have spontaneous transitions, which requires different techniques from the usual derived-term constructions.

Continue reading

Derived-term automata for extended weighted rational expressions

By Akim Demaille

2016-07-06

In Proceedings of the thirteenth international colloquium on theoretical aspects of computing (ICTAC)

Abstract We present an algorithm to build an automaton from a rational expression. This approach introduces support for extended weighted expressions. Inspired by derived-term based algorithms, its core relies on a different construct, rational expansions. We introduce an inductive algorithm to compute the expansion of an expression from which the automaton follows. This algorithm is independent of the size of the alphabet, and actually even supports infinite alphabets. It can easily be accommodated to generate deterministic (weighted) automata.

Continue reading

Derived-term automata of multitape rational expressions

By Akim Demaille

2016-04-26

In Proceedings of implementation and application of automata, 21st international conference (CIAA’16)

Abstract We introduce (weighted) rational expressions to denote series over Cartesian products of monoids. To this end, we propose the operator $\mid$ to build multitape expressions such as $(a^+\mid x + b^+\mid y)^*$. We define expansions, which generalize the concept of derivative of a rational expression, but relieved from the need of a free monoid. We propose an algorithm based on expansions to build multitape automata from multitape expressions.

Continue reading

Type-checking of heterogeneous sequences in Common Lisp

By Jim Newton, Akim Demaille, Didier Verna

2016-03-25

In ELS 2016, the 9th european lisp symposium

Abstract We introduce the abstract concept of rational type expression and show its relationship to rational language theory. We further present a concrete syntax, regular type expression, and a Common Lisp implementation thereof which allows the programmer to declaratively express the types of heterogeneous sequences in a way which is natural in the Common Lisp language. The implementation uses techniques well known and well founded in rational language theory, in particular the use of the Brzozowski derivative and deterministic automata to reach a solution which can match a sequence in linear time.

Continue reading

A type system for weighted automata and rational expressions

By Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Luca Saiu, Jacques Sakarovitch

2014-05-20

In Proceedings of implementation and application of automata, 19th international conference (CIAA’14)

Abstract We present a type system for automata and rational expressions, expressive enough to encompass weighted automata and transducers in a single coherent formalism. The system allows to express useful properties about the applicability of operations including binary heterogeneous functions over automata. We apply the type system to the design of the platform, a library dedicated to the computation with finite weighted automata, in which genericity and high efficiency are obtained at the lowest level through the use of template metaprogramming, by letting the template system play the role of a static type system for automata.

Continue reading

Implementation concepts in Vaucanson 2

By Akim Demaille, Alexandre Duret-Lutz, Sylvain Lombardy, Jacques Sakarovitch

2013-05-02

In Proceedings of implementation and application of automata, 18th international conference (CIAA’13)

Abstract Vaucanson is an open source C++ platform dedicated to the computation with finite weighted automata. It is generic: it allows to write algorithms that apply on a wide set of mathematical objects. Initiated ten years ago, several shortcomings were discovered along the years, especially problems related to code complexity and obfuscation as well as performance issues. This paper presents the concepts underlying Vaucanson 2, a complete rewrite of the platform that addresses these issues.

Continue reading

TWEAST: A simple and effective technique to implement concrete-syntax AST rewriting using partial parsing

By Akim Demaille, Roland Levillain, Benoît Sigoure

2008-10-11

In Proceedings of the 24th annual ACM symposium on applied computing (SAC’09)

Abstract ASTs are commonly used to represent an input/output program in compilers and language processing tools. Many of the tasks of these tools consist in generating and rewriting ASTs. Such an approach can become tedious and hard to maintain for complex operations, namely program transformation, optimization, instrumentation, etc. On the other hand, concrete syntax provides a natural and simpler representation of programs, but it is not usually available as a direct feature of the aforementioned tools.

Continue reading

Compiler construction as an effective application to teach object-oriented programming

By Akim Demaille, Roland Levillain

2008-09-15

In

Abstract Compiler construction, a course feared by most students, and a competence seldom needed in the industry. Yet we claim that compiler construction is wonderful topic that benefits from virtually all the computer-science topics. In this paper we show in particular why compiler construction is a killer example for Object-Oriented Programming, providing a unique opportunity for students to understand what it is, what it can be used for, and how it works.

Continue reading

An XML format proposal for the description of weighted automata, transducers, and regular expressions

By Akim Demaille, Alexandre Duret-Lutz, Florian Lesaint, Sylvain Lombardy, Jacques Sakarovitch, Florent Terrones

2008-07-28

In Post-proceedings of the seventh international workshop on finite-state methods and natural language processing (FSMNLP’08)

Abstract We present an XML format that allows to describe a large class of finite weighted automata and transducers. Our design choices stem from our policy of making the implementation as simple as possible. This format has been tested for the communication between the modules of our automata manipulation platform Vaucanson, but this document is less an experiment report than a position paper intended to open the discussion among the community of automata software writers.

Continue reading

Search

Tags