Jacques Sakarovitch

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. Between such a low-level layer and the interactive high-level interface, the type system plays the crucial role of a mediator and allows for a cleanly-structured use of dynamic compilation.

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

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

Inside Vaucanson

By Thomas Claveirole, Sylvain Lombardy, Sarah O’Connor, Louis-Noël Pouchet, Jacques Sakarovitch

2005-05-25

In Proceedings of implementation and application of automata, 10th international conference (CIAA)

Abstract

This paper presents some features of the Vaucanson platform. We describe some original algorithms on weighted automata and transducers (computation of the quotient, conversion of a regular expression into a weighted automaton, and composition). We explain how complex declarations due to the generic programming are masked from the user and finally we present a proposal for an XML format that allows implicit descriptions for simple types of automata.

Continue reading

Introducing Vaucanson

By Sylvain Lombardy, Yann Régis-Gianas, Jacques Sakarovitch

2004-11-01

In Theoretical Computer Science

Abstract

This paper reports on a new software platform called VAUCANSON and dedicated to the computation with automata and transducers. Its main feature is the capacity of dealing with automata whose labels may belong to various algebraic structures. The paper successively describes the main features of the VAUCANSON platform, including the fact that the very rich data structure used to implement automata does not weigh too much on the performance, shows how VAUCANSON allows to program algorithms on automata in a way which is very close to the mathematical expression of the algorithm and finally explains the main choices of the programming design that enable to achieve both genericity and efficiency.

Continue reading

Introducing Vaucanson

By Sylvain Lombardy, Raphaël Poss, Yann Régis-Gianas, Jacques Sakarovitch

2003-05-05

In Proceedings of implementation and application of automata, 8th international conference (CIAA’03)

Abstract

This paper reports on a new software platform dedicated to the computation with automata and transducers, called Vaucanson, the main feature of which is the capacity of dealing with automata whose labels may belong to various algebraic structures. The paper successively shows how Vaucanson allows to program algorithms on automata in a way which is very close to the mathematical expression of the algorithm, describes some features of the Vaucanson platform, including the fact that the very rich data structure used to implement automata does not weight too much on the performance and finally explains the main issues of the programming design that allow to achieve both genericity and efficiency.

Continue reading

Search

Tags