Induction of Non-Deterministic Finite Automata on Supercomputers


Wojciech Wieczorek ;
Proceedings of the Eleventh International Conference on Grammatical Inference, PMLR 21:237-242, 2012.


The problem of inducing automata of minimal size consistent with finite sets of examples and counter-examples is the combinatorial optimization task of grammatical inference and is known to be computationally hard. Both an exact and a heuristic method of finding a non-deterministic finite automaton (NFA) with a given number of states such that all examples are accepted and all counter-examples are rejected by the automaton will be evaluated. The methods are based on a translation of NFA identification into integer nonlinear programming.

Related Material