Article ID Journal Published Year Pages File Type
4952302 Theoretical Computer Science 2017 11 Pages PDF
Abstract
Nondeterministic finite automata with don't care states, namely states which neither accept nor reject, are considered. A characterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. It is proved that the problem of minimizing deterministic don't care automata is NP-complete and PSPACE-hard in the nondeterministic case. The restriction to the unary case is also considered.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, , ,