Nondeterministic finite automata with don’t care states, [4] namely states which neither accept nor reject, are considered. A cha- racterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. Finally, it is proved that the problem of minimizing nondeterministic and deterministic don’t care automata is NP-complete.
Optimal State Reductions of Automata with Partially Specified Behaviors / N. Moreira, G. Pighizzini, R. Reis (LECTURE NOTES IN COMPUTER SCIENCE). - In: SOFSEM 2015: Theory and Practice of Computer Science / [a cura di] G.F. Italiano, T. Margaria-Steffen, J. Pokorný, J.-J. Quisquater, R. Wattenhofer. - New York : Springer, 2015. - ISBN 9783662460771. - pp. 339-351 (( Intervento presentato al 41. convegno SOFSEM tenutosi a Pec pod Sněžkou nel 2015 [10.1007/978-3-662-46078-8_28].
Optimal State Reductions of Automata with Partially Specified Behaviors
G. Pighizzini;
2015
Abstract
Nondeterministic finite automata with don’t care states, [4] namely states which neither accept nor reject, are considered. A cha- racterization of deterministic automata compatible with such a device is obtained. Furthermore, an optimal state bound for the smallest compatible deterministic automata is provided. Finally, it is proved that the problem of minimizing nondeterministic and deterministic don’t care automata is NP-complete.
| File | Dimensione | Formato | |
|---|---|---|---|
|
Moreira2015_Chapter_OptimalStateReductionsOfAutoma (1).pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
236.93 kB
Formato
Adobe PDF
|
236.93 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
