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.
Optimal state reductions of automata with partially specified behaviors / N. Moreira, G. Pighizzini, R. Reis. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 658(2017), pp. 235-245. ((Intervento presentato al convegno Meeting of the Italian-National-PRIN Project on Formal Languages and Automata - Model, Methods and Applications tenutosi a Napoli nel 2016 [10.1016/j.tcs.2016.05.002].
Optimal state reductions of automata with partially specified behaviors
G. Pighizzini
;
2017
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.
| File | Dimensione | Formato | |
|---|---|---|---|
|
tcsrestivo.pdf
accesso aperto
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
353.01 kB
Formato
Adobe PDF
|
353.01 kB | Adobe PDF | Visualizza/Apri |
|
1-s2.0-S0304397516301153-main.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
466.91 kB
Formato
Adobe PDF
|
466.91 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.
