Symmetry Breaking Predicates for SAT-based DFA Identification

Autor: Ulyantsev, Vladimir, Zakirzyanov, Ilya, Shalyto, Anatoly

It was shown before that the NP-hard problem of deterministic finite automata (DFA) identification can be effectively translated to Boolean satisfiability (SAT). Modern SAT-solvers can tackle hard DFA identification instances efficiently. We present

Externí odkaz: http://arxiv.org/abs/1602.05028

BFS-Based Symmetry Breaking Predicates for DFA Identification.

Autor: Ulyantsev, Vladimir, Zakirzyanov, Ilya, Shalyto, Anatoly

Publikováno v: Language & Automata Theory & Applications 9th International Conference, LATA 2015, Nice, France, March 2-6, 2015, Proceedings; 2015, p611-622, 12p