Name
Abstract | ||
|---|---|---|
Deterministic finite automaton (DFA) is a fundamental concept in the theory of computation. The NP-hard DFA identification problem can be efficiently solved by translation to the Boolean satisfiability problem (SAT). Previously we developed a technique to reduce the problem search space by enforcing DFA states to be enumerated in breadth-first search (BFS) order. We proposed symmetry breaking predicates, which can be added to Boolean formulae representing various automata identification problems. In this paper we continue the study of SAT-based approaches. First, we propose new predicates based on depth-first search order. Second, we present three methods to identify all non-isomorphic automata of the minimum size instead of just one- the # P-complete problem which has not been solved before. Third, we revisited our implementation of the BFS-based approach and conducted new evaluation experiments. It occurs that BFS-based approach out-performs all other exact algorithms for DFA identification and can be effectively applied for finding all solutions of the problem. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1007/978-3-319-74781-1_9 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Grammatical inference,Automata identification Symmetry breaking,Boolean satisfiability | Grammar induction,Symmetry breaking,Deterministic finite automaton,Computer science,Boolean satisfiability problem,Automaton,Theoretical computer science,Real-time computing,Predicate (grammar),Parameter identification problem,Theory of computation | Conference |
Volume | ISSN | Citations |
10729 | 0302-9743 | 2 |
PageRank | References | Authors |
0.38 | 13 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ilya Zakirzyanov | 1 | 12 | 1.97 |
| Anatoly Shalyto | 2 | 98 | 20.06 |
| Vladimir Ulyantsev | 3 | 60 | 12.44 |