Grammatical Inference as a Satisfiability Modulo Theories Problem
This work addresses grammatical inference for researchers in formal methods and machine learning, offering incremental improvements in model learning efficiency.
The paper tackled the problem of learning minimal consistent models from labeled symbol sequences by formulating it as a satisfiability modulo theories (SMT) problem, resulting in encodings for deterministic finite automata, Moore, and Mealy machines that improve upon state-of-the-art methods and are practical for learning small models.
The problem of learning a minimal consistent model from a set of labeled sequences of symbols is addressed from a satisfiability modulo theories perspective. We present two encodings for deterministic finite automata and extend one of these for Moore and Mealy machines. Our experimental results show that these encodings improve upon the state-of-the-art, and are useful in practice for learning small models.