Konferenzpaper

Jahr der Veröffentlichung: 2016

Seiten: 161-185

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 27

Heftnummer: 2

ISSN: 0129-0541

eISSN: 1793-6373

DOI Link: https://doi.org/10.1142/S0129054116400050

Konferenz: 18th International Conference on Developments in Language Theory (DLT)

Verlag: World Scientific Publishing

Abstract: 
We compare deterministic finite automata (D.FAs) and biautomata under the following two aspects: structural similarities between minimal and hyper-minimal automata, and computational complexity of the minimization and hyper-minimization problem. Concerning classical minimality, the known results such as isomorphism between minimal DFAs, and NL-completeness of the DFA minimization problem carry over to the biautomaton case. But surprisingly this is not the case for hyper-minimization: the simrilarity between almost-equivalent hyper-minimal biautomata is not as strong as it is between almost-equivalent hyper-minimal DFAs. Moreover, while hyper-minimization is NL-complete for DFAs, we prove that this problem turns out to be computationally intractable, i.e., NP-complete, for biautomata.

Harvard-Zitierstil: Holzer, M. and Jakobi, S. (2016) Minimal and Hyper-Minimal Biautomata, International Journal of Foundations of Computer Science, 27(2), pp. 161-185. https://doi.org/10.1142/S0129054116400050

APA-Zitierstil: Holzer, M., & Jakobi, S. (2016). Minimal and Hyper-Minimal Biautomata. International Journal of Foundations of Computer Science. 27(2), 161-185. https://doi.org/10.1142/S0129054116400050