Implementations of the state merging operator in DFA learning

Abstract

DFA learning is an NP-Hard problem typically accomplished by means of state merging algorithms such as EDSM, automata teams and ed-beam. When running, these algorithms will perform many millions of merges and the deterministic state merging operation is a significant performance bottleneck. This project is motivated by the need to alleviate this bottleneck with a faster state merging operation. Achieving this would allow researchers to attempt harder problems, run more sophisticated heuristics and perform more meaningful analysis by running their tests on larger, more statistically significant pools of problems. To this end, we investigate the data structures used by implementations of the state merging algorithms and use deep profiling and various optimisation techniques to create a performant state merging operation. We also consider how it may be possible to take advantage of concurrency to perform many merges in parallel and build a novel GPU implementation of the merge operation. Our implementation was evaluated and benchmarked on a large pool of Abbadingo-style problems using Blue-Fringe EDSM. We compared our implementation to GI-Learning, LibLearn and FlexFringe and found that our final implementation is more than 5× faster than the next best.