CIAA 2017

22nd International Conference Implementation and Application of Automata

27--30 June 2017, Université Paris-Est Marne-la-Vallée

The FAdo system aims to provide an open source extensible software library for the symbolic manipulation of regular languages and other formal languages. FAdo is implemented in Python and currently includes most standard operations for the manipulation of regular languages through finite automata (Python classes DFA, NFA, or GFA) and regular expressions (reex). Elementary regular language operations, such as, union, intersection, complementation, concatenation, iteration, and reverse are implemented for each class. Many combined operations have specialized algorithms. Witness families for several operational complexity lower bounds are defined and canonical representations are supported. Several conversions between representations are implemented: NFA to DFA, NFA to reex, GFA to reex, reex to NFA, etc.. For DFA, several minimization (and hyperminimazation) algorithms are available: Moore, Hopcroft, Brzozowski, and some incremental algorithms. NFA minimization via universal automata is implemented but with the inherent inefficiency. Extended regular expressions modulo some algebraic properties are also supported. Some support is provided for computing syntactic semigroups. There are several algorithms for language equivalence based on bisimulation-like algorithms. Finite languages can also be represented, by tries, AFA (acyclic finite automata) and cover automata. Exact and random generators for some classes of automata and regular expressions are also available.

Several methods for transducers in standard form (SFT) are implemented, such as rational operations (union, inverse, reversal, composition, concatenation, star); product operations (input and output intersection); test and witness of non functionality. A language property is a set of languages. Given a property specified by a transducer, several language tests are possible with application in code theory: satisfaction i.e. if a language satisfies the property;maximality i.e. the language satisfies the property and is maximal; properties implemented by transducers include: input preserving, input altering, trajectories, and fixed properties.

GUItar is a graphical user interface for automata drawing and manipulation. Its functionalities include visualization and interactive editing, i.e. automatic and assisted diagram drawing; and export/import filters that allow the interaction with several symbolic manipulators.