Report on the exact methods for finding minimum-sized DFA
- 7 September 2023
- journal article
- research article
- Published by Oxford University Press (OUP) in Logic Journal of the IGPL
- Vol. 32 (5) , 909-935
Abstract
This paper presents four state-of-art methods for the finite-state automaton inference based on a sample of labeled strings. The first algorithm is Exbar, and the next three are mathematical models based on ASP, SAT and SMT theories. The potentiality of using multiprocessor computers in the context of automata inference was our research’s primary goal. In a series of experiments, we showed that our parallelization of the exbar algorithm is the best choice when a multiprocessor system is available. Furthermore, we obtained a superlinear speedup for some of the prepared datasets, achieving almost a 5-fold speedup on the median, using 12 and 24 processes.Keywords
This publication has 20 references indexed in Scilit:
- A survey of grammatical inference in software engineeringScience of Computer Programming, 2014
- Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems withIDP3Theory and Practice of Logic Programming, 2014
- An overview of parallel SAT solvingConstraints, 2012
- A bibliographical study of grammatical inferencePattern Recognition, 2005
- Knowledge Representation, Reasoning and Declarative Problem Solving2003
- A new algorithm for exact reduction of incompletely specified finite state machinesIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1999
- Pattern discovery in biosequences1998
- Learning regular grammars to model musical style: Comparing different coding schemes1998
- Greed is good: Approximating independent sets in sparse and bounded-degree graphsAlgorithmica, 1997
- Complexity of automaton identification from given dataInformation and Control, 1978