Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Minimization, characterizations, and nondeterminism for biautomata

Holzer, Markus ; Jakobi, Sebastian

Zum Volltext im pdf-Format: Dokument 1.pdf (277 KB)

Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-110545

Bookmark bei

Freie Schlagwörter (Englisch): deterministic and nondeterministic biautomata , cyclic languages , commutative languages , Brzozowski´s minimization algorithm
CCS - Klassifikation: F.1.3 , F.2.2 , F.4.2
Universität Justus-Liebig-Universität Gießen
Institut: Institut für Informatik
Fachgebiet: Informatik
DDC-Sachgruppe: Informatik
Dokumentart: ResearchPaper
Zeitschrift, Serie: IFIG Research Report ; 1301
Sprache: Englisch
Erstellungsjahr: 2013
Publikationsdatum: 03.09.2014
Kurzfassung auf Englisch: 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.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand