Reducing nondeterministic finite automata with SAT solvers
Date
2010
Authors
Geldenhuys J.
Van Der Merwe B.
Van Zijl L.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
We consider the problem of reducing the number of states of nondeterministic finite automata, and show how to encode the reduction as a Boolean satisfiability problem. This approach improves on previous work by reducing a more general class of automata. Experimental results show that it produces a minimal automaton in almost all cases and that the running time compares favourably to the Kameda-Weiner algorithm. © 2010 Springer-Verlag Berlin Heidelberg.
Description
Keywords
Boolean satisfiability problems, General class, Minimal automaton, Nondeterministic finite automaton, Number of state, Running time, SAT solvers, Boolean functions, Computational linguistics, Natural language processing systems, Pipeline processing systems, Robots, Translation (languages), Finite automata
Citation
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
6062 LNAI
6062 LNAI