Minimization, characterizations, and nondeterminism for biautomata
Loading...
Date
Authors
Advisors/Reviewers
Further Contributors
Contributing Institutions
Publisher
Journal Title
Journal ISSN
Volume Title
Publisher
License
Quotable link
Abstract
We show how to minimize biautomata with a Brzozowski-like algorithm by applying reversal and powerset construction twice. Biautomata were recently introduced in[O. Klíma, L. Polák: 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 generalize the notion of biautomata to deal with nondeterminism and moreover, to take structural properties of the forward- and backward-transition of the automaton into account. This results in a variety of biautomata models, which accepting power is characterized. As a byproduct we give a simple structural characterization of cyclic regular and commutative regular languages in terms of deterministic biautomata.Link to publications or other datasets
Description
Notes
Original publication in
Original publication in
Anthology
Collections
URI of original publication
Forschungsdaten
Series
IFIG Research Report; 1301