VaucansonOverview

Vaucanson is a finite state machine manipulation platform, initiated by Jacques Sakarovitch and Sylvain Lombardy in 2001. A finite state machine (also called automaton) is a computing tool useful in langage processing or automation.

In the past, such platforms were intended to work either at an industrial scale, specialized in weighted letter automaton (FSM) to be efficient, or in a pure abstract way (FSA). Using static and generic C++ programming, Vaucanson tries to respond to these two trends.

Indeed, our framework is the set of automata with multiplicity over any semiring: a general algorithm is written just once and can be statically instantiated to any particular kind of automaton. As a result, we obtain efficient code from algorithms written in an abstract way using basic primitives taken from the C++ library.

Vaucanson is work in progress, some features have not yet been heavily tested.

Library features

The C++ library provides:

• Generic algebraic structures, including:
  • efficient polynomials as maps from monoid values to weights
  • efficient rational expressions as binary trees
• Automaton structures, using a graph structure that ensures minimum complexity for most operations
• Algorithms
• Generic testsuites for user-made extensions