Chaining Heuristic and Exact Methods for DFA Identification
V. Chirov (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Sicco Verwer – Mentor (TU Delft - Algorithmics)
Simon Dieck – Mentor (TU Delft - Algorithmics)
Soham Chakraborty – Graduation committee member (TU Delft - Programming Languages)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
This paper investigates a hybrid approach to deterministic finite automata (DFA) identification by combining heuristic (EDSM) and exact (reduction to SAT) methods. The hybrid strategy implies first partially identifying the DFA heuristically and then minimizing it with an exact method. Two implementations of the hybrid approach are tested - one using binary search on the number of states of the intermediate model, and one that adjusts the SAT offset to control its search space. The results obtained on datasets from the STAMINA competition show that while the hybrid approach reduces the size of the inferred models compared to EDSM, this does not necessarily translate to better test performance. Nevertheless, the methods used in this work demonstrate how a hybrid approach can be applied to infer more compact models in DFA identification.