Minimization, characterizations, and nondeterminism for biautomata

dc.contributor.authorHolzer, Markus
dc.contributor.authorJakobi, Sebastian
dc.date.accessioned2022-09-12T09:38:33Z
dc.date.available2014-09-03T10:27:11Z
dc.date.available2022-09-12T09:38:33Z
dc.date.issued2013
dc.description.abstractWe 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.en
dc.identifier.urihttp://nbn-resolving.de/urn:nbn:de:hebis:26-opus-110545
dc.identifier.urihttps://jlupub.ub.uni-giessen.de//handle/jlupub/7528
dc.identifier.urihttp://dx.doi.org/10.22029/jlupub-6962
dc.language.isoende_DE
dc.relation.ispartofseriesIFIG Research Report; 1301
dc.rightsIn Copyright*
dc.rights.urihttp://rightsstatements.org/page/InC/1.0/*
dc.subjectdeterministic and nondeterministic biautomataen
dc.subjectcyclic languagesen
dc.subjectcommutative languagesen
dc.subjectBrzozowski´s minimization algorithmen
dc.subject.ddcddc:004de_DE
dc.titleMinimization, characterizations, and nondeterminism for biautomataen
dc.typeworkingPaperde_DE
local.affiliationFB 07 - Mathematik und Informatik, Physik, Geographiede_DE
local.opus.fachgebietInformatikde_DE
local.opus.id11054
local.opus.instituteInstitut für Informatikde_DE

Dateien

Originalbündel
Gerade angezeigt 1 - 1 von 1
Lade...
Vorschaubild
Name:
Ifig_Report1301.pdf
Größe:
277.04 KB
Format:
Adobe Portable Document Format