|Title||Optimal State Reductions of Automata with Partially Specified Behaviors|
|Publication Type||Articles in international peer reviewed journals|
|Year of Publication||2017|
|Authors||Moreira N, Pighizzini G, Reis R|
|Journal||Theoretical Computer Science|
|Keywords||Descriptional complexity; Don't care automata; Finite automata; Nondeterminism|
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.