Conference paper

Publication year: 2016

Pages: 161-185

Journal: International Journal of Foundations of Computer Science

Volume number: 27

Issue number: 2

ISSN: 0129-0541

eISSN: 1793-6373

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

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

Publisher: 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 Citation style: 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 Citation style: 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