Journal article

Publication year: 2014

Pages: 837-855

Journal: International Journal of Foundations of Computer Science

Volume number: 25

Issue number: 7

ISSN: 0129-0541

eISSN: 1793-6373

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

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