The Automata Standard Template Library

Welcome to the Automata Standard Template Library home page. ASTL is a set of generic and efficient C++ components for automata manipulation. It provides a collection of new concepts and header files which one can reuse under the terms of the Lesser GNU Public License. The library has been designed and tested with the latest versions of g++.


The library design is inspired by generic programming techniques in C++ which involves template programming for reusability and efficiency,  rigorous concept definitions à la STL like algorithms, cursors and automata containers.

The library provides a number of fundamental algorithms on automata like minimisation (acyclic/cyclic, static/dynamic), determinisation, set operations, construction from a regular expression and more. All these algorithms are made independant from the containers they apply to thanks to the concept of the iterators on automata : the cursors. Moreover, a variety of automata containers make the algorithms adaptable to many different constraints of time and memory space.

These design choices result in a set of highly efficient and reusable software tools acting as a base for any development involving automata like computational linguistics, text processing and pattern matching.

Proof of Concept

ASTL boasts one of the fastest regular expression engine ever. Take a look at these performance comparisons.


Link to the doxygen HTML code documentation of ASTL. Still uncomplete.

These two articles give an overview of the concepts related to automata programming and their implementation in the source code of ASTL :

Some things more technical:


This is the developer's page on sourceforge.

This is the access to the SVN source tree browser

This is the tarball of the ASTL SVN repository

The documentation is still uncomplete but a few code examples are provided. They should help get a quick start. The code has grown mature and is now almost bug free. You will need a version 3 or more of g++ to compile the code as-is (version 4 recommended). It also has been succesfully compiled with VC++ 2005 and g++-4 under Cygwin. Check the readme file at the root of the trunk for getting started.


Vincent Le Maout,