Université Paris Est - Marne-la-Vallée

REGAL : Random and Exhaustive Generators for Automata - Library

What is REGAL?

REGAL is a C++ package which allows to generate ICDFAs randomly or exhaustively. The main goal is to provide to the community a toolbox to:
• test implementations of various algorithms applied on automata
• check properties on automata
• make analysis in the average case in order to establish edible conjectures

The Library

Access to documentation.
Contact: Julien.David@univ-paris-est.fr

Download :
• NEW VERSION: REGAL v1.08.0929.
• REGAL v1.08.0501.
• REGAL v1.07.0820, REGAL v1.07.0709, REGAL v1.07.0625.
• REGAL v1.0.0.
If you have any question, feel free to use the forum

The Program: PREGA

PREGA is a program developped for non-programming users.
Its uses the library REGAL in order to generate automata.

The user describes what he wants in an XML file that PREGA interprets.
The results are given on the standard output, in a format specified by the user (Gastex, DoT, XML, hopefully soon tikz).
PREGA requieres dpkg and the libxml++ library to be installed on your computer.

Download :
• NEW VERSION (01/19/11 - Minor corrections) : PREGA.
(I would like to thanks Ines Klimann and Alois Dreyfus who warned me about some compilation problems)

What is new?

Version 1.08.0929 : main generators have been improved, using a new bijection.

Version 1.08.0501 : correction made on several classes. New generator for ICDFAs, without the completeness constraint.
Generator for minimal complete ICDFA accelerated.
Associated Article:
• Frederique Bassino, Julien David, and Cyril Nicaud - Random generation of possibly incomplete deterministic automata (PUMA'08)

Version 1.07.0820 : Generator for Co-accessibles ICDFAs, bugs fixed on the Exhaustive generator
Version 1.07.0709 : The user may now change the probability for a state to be final in the random generator.
Version 1.07.0625 : Includes an Histogram Maker and a new generator for Strongly Connected ICDFAs.
Version 1.0.0 : Tested with g++ 3.3.5 and 4.1.1
Associated Articles:
• Frederique Bassino, Julien David, and Cyril Nicaud - REGAL: a library to randomly and exhaustively generate automata (CIAA'07) (2 pages)
• Julien David - REGAL: une bibliotheque pour la generation des automates deterministes (MAJECSTIC'07)(10 pages, in French)
• Frederique Bassino and Cyril Nicaud - Enumeration and Random Generation of Accessible Automata (TCS'07).

List of Random Generators

• Random Complete Deterministic Accessible Automata:
  Options: Minimal, Strongly connected, Co-Accessible, possibility to change the probability of a state to be final.
• Random Possibly Incomplete Deterministic Deterministic automata
  Options: Minimal, Strongly connected, Co-Accessible, possibility to change the probability of a state to be final.
• Random Tree Automata