flexfringe is a passive automata learning model with an emphasis on flexibility in merge heuristic and model type. You can access the respository with all code here.

Building flexfringe

To build flexfringe,  you need to have the libpopt-dev library (libpopt-dev packagein Ubuntu) for argument parsing. Some heuristic functions bring their own dependencies: We provide an implementation of a likelihood-based merge function for probabilistic DFAs. It needs the GNU scientific library (development) package (e.g. the libgsl-dev package in Ubuntu). You can remove the likelihood-based cpp files from the evaluation directory to build flexfringe without it.

If you want to use the reduction to SAT and automatically invoke the SAT solver, you need to provide the path to the solver binary. flexfringe has been tested with lingeling (which you can get from and run its

You can build and compile the flexfringe project by running

$ make clean all

in the main directory to build the executable named flexfringe.

We typically build and use flexfringe on MacOS and Ubuntu. If you encounter any build errors, please email us your problem, and include some details of the system and compiler you’re using.

A Brief Note on the Branches in the Repository

The branch oldstable contains

Running flexfringe

Run ./flexfringe –help to get help.

The script together with some .ini files provides a shortcut to storing


$ ./ mealy-batch.ini data/simple.traces

See the .ini files for details of parameters and flags used.

flexfringe will output some .dot files. You can visualize them using the script or running dot explicitly

$ dot -Tpdf -o outfile.pdf or $ ./

You can checkout the latest version of flexfringe over at bitbucket.

Here is a short demonstration.

Is it fast?

flexfringe is built both for extensibility as well as speed of inference. While the core, its red-blue fringe state-merging algorithm is fast, calling complicated merge heuristics can be expensive and slow down the inference considerably. The following graph shows a call profile running on a stamina competition problem containing software traces, using the overlap-driven heuristic. The heuristic itself is fairly inexpensive but needs to check for overlapping transitions of all merge candidates. As you can see, most time and calls are spent in the test_merge method.

Profiling graph of a run of flexfringe on a dataset from stamina.
Profiling graph of a run of the overlap heuristic on data from the Stamina competition. Click to enlarge and see in original size.

Extending flexfringe

To learn your own versions of extended finite state machines using flexfringe, you need to create your own evaluation heuristic consisting of an evaluation_function and evaluation_data class. You can derive objects from the templates provided in the evaluation/ directory. The doxygen documentation provides some further information on the necessary methods and data structures.

A more detailed guide is under preparation.