Journalartikel

Jahr der Veröffentlichung: 2014

Seiten: 837-855

Zeitschrift: International Journal of Foundations of Computer Science

Bandnummer: 25

Heftnummer: 7

ISSN: 0129-0541

eISSN: 1793-6373

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

Verlag: World Scientific Publishing

Abstract: 
We investigate the descriptional complexity of no ndeterministic biautomata, which are a generalization of biautomata [O. Klima, L. Polak : On biautomata. RAIRO - Theor. Inf. Appl., 46(4), 2012]. Simply speaking, biautomata are finite automata reading the input from both sides; although the head movement is nondeterministic, additional requirements enforce biautomata to work deterministically. First we study the size blow-up when determinizing nondeterministic biautomata. Further, we give tight bounds on the number of states for nondeterministic biautomata accepting regular languages relative to the size of ordinary finite automata, regular expressions, and syntactic monoids. It turns out that as in the case of ordinary finite automata nondeterministic biautomata are superior to biautomata with respect to their relative succinctness in representing regular languages.

Harvard-Zitierstil: Holzer, M. and Jakobi, S. (2014) NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY, International Journal of Foundations of Computer Science, 25(7), pp. 837-855. https://doi.org/10.1142/S0129054114400115

APA-Zitierstil: Holzer, M., & Jakobi, S. (2014). NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY. International Journal of Foundations of Computer Science. 25(7), 837-855. https://doi.org/10.1142/S0129054114400115