Using Forest Structures for Passive Automata Learning

We present an extension on a passive learning algorithm for deterministic finite automata (DFAs) and Mealy machines which is based on the regular positive and negative inference (RPNI) algorithm. The extension builds a structure which is inspired by random forests. Instead of building a single automaton, the forest builds several. The paper introduces two forest structures for learning DFAs, together with their respective extension for Mealy machines, where the choice of which to pick depends on the output to achieve, as well as the type of application. Following that, the empirical analysis shows which parameters yield better results than the basic RPNI passive learning approach. In our experiments, forest structures for passive learning of automata yield significant improvement over the standard RPNI algorithm of up to \(43\%\) in the total number of correct outputs when testing Mealy machines.