Reducing nondeterministic finite automata with SAT solvers

Geldenhuys J. ; Van Der Merwe B. ; Van Zijl L. (2010)

Conference Paper

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.

Please refer to this item in SUNScholar by using the following persistent URL:
This item appears in the following collections: