Improved SAT models for NFA learning
This work addresses grammatical inference for automata learning, but it is incremental as it focuses on optimizing existing SAT-based methods for NFA learning.
The authors tackled the problem of learning Nondeterministic Finite Automata (NFA) of size k from word samples by formulating it as a SAT model, and they proposed improvements that significantly reduced instance sizes in terms of variables, clauses, and clause size, though at the cost of longer generation times.
Grammatical inference is concerned with the study of algorithms for learning automata and grammars from words. We focus on learning Nondeterministic Finite Automaton of size k from samples of words. To this end, we formulate the problem as a SAT model. The generated SAT instances being enormous, we propose some model improvements, both in terms of the number of variables, the number of clauses, and clauses size. These improvements significantly reduce the instances, but at the cost of longer generation time. We thus try to balance instance size vs. generation and solving time. We also achieved some experimental comparisons and we analyzed our various model improvements.