Optimal State Reductions of Automata with Partially Specified Behaviors ☆

Research paper by Nelma Moreira, Giovanni Pighizzini, Rogério Reis

Indexed on: 13 May '16Published on: 12 May '16Published in: Theoretical Computer Science


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.

Figure 10.1016/j.tcs.2016.05.002.0.gif
Figure 10.1016/j.tcs.2016.05.002.1.gif
Figure 10.1016/j.tcs.2016.05.002.2.gif
Figure 10.1016/j.tcs.2016.05.002.3.gif
Figure 10.1016/j.tcs.2016.05.002.4.gif
Figure 10.1016/j.tcs.2016.05.002.5.gif
Figure 10.1016/j.tcs.2016.05.002.6.gif
Figure 10.1016/j.tcs.2016.05.002.7.gif