Anzeige
Erschienen in:
2019 | OriginalPaper | Buchkapitel
Learning Minimal DFA: Taking Inspiration from RPNI to Improve SAT Approach
verfasst von : Florent Avellaneda, Alexandre Petrenko
Erschienen in: Software Engineering and Formal Methods
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Inferring a minimal Deterministic Finite Automaton (DFA) from a learning sample that includes positive and negative examples is one of the fundamental problems in computer science. Although the problem is known to be NP-complete, it can be solved efficiently with a SAT solver especially when it is used incrementally. We propose an incremental SAT solving approach for DFA inference in which general heuristics of a solver for assigning free variables is replaced by that employed by the RPNI method for DFA inference. This heuristics reflects the knowledge of the problem that facilitates the choice of free variables. Since the performance of solvers significantly depends on the choices made in assigning free variables, the RPNI heuristics brings significant improvements, as our experiments with a modified solver indicate; they also demonstrate that the proposed approach is more effective than the previous SAT approaches and the RPNI method.