Conference paper

Publication year: 2015

Pages: 113-137

Journal: Fundamenta Informaticae

Volume number: 136

Issue number: 1-2

ISSN: 0169-2968

eISSN: 1875-8681

DOI Link: https://doi.org/10.3233/FI-2015-1146

Conference: 5th Workshop on Non-Classical Models of Automata and Applications (NCMA)

Publisher: SAGE Publications

Abstract: 
We show how to minimize biautomata with adaptations of classical minimization algorithms for ordinary deterministic finite automata and moreover by a Brzozowski-like minimization algorithm by applying reversal and power-set construction twice to the biautomaton under consideration. Biautomata were recently introduced in [O. KLIMA, L. POLAK: On biautomata. RAIRO-Theor. Inf. Appl., 46(4), 2012] as a generalization of ordinary finite automata, reading the input from both sides. The correctness of the Brzozowski-like minimization algorithm needs a little bit more argumentation than for ordinary finite automata since for a biautomaton its dual or reverse automaton, built by reversing all transitions, does not necessarily accept the reversal of the original language. To this end we first use the recently introduced notion of nondeterminism for biautomata [M. HOLZER, S. JAKOBI: Nondeterministic Biautomata and Their Descriptional Complexity. In: 15th DCFS, Number 8031 of LNCS, 2013] and take structural properties of the forward-and backward-transitions of the automaton into account. This results in a variety of biautomata models, the accepting power of which is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.

Harvard Citation style: Holzer, M. and Jakobi, S. (2015) Minimization and Characterizations for Biautomata, Fundamenta Informaticae, 136(1-2), pp. 113-137. https://doi.org/10.3233/FI-2015-1146

APA Citation style: Holzer, M., & Jakobi, S. (2015). Minimization and Characterizations for Biautomata. Fundamenta Informaticae. 136(1-2), 113-137. https://doi.org/10.3233/FI-2015-1146