Giessener Elektronische Bibliothek

GEB - Giessener Elektronische Bibliothek

Minimal and hyper-minimal biautomata

Holzer, Markus ; Jakobi, Sebastian


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


Bitte beziehen Sie sich beim Zitieren dieses Dokumentes immer auf folgende
URN: urn:nbn:de:hebis:26-opus-110561
URL: http://geb.uni-giessen.de/geb/volltexte/2014/11056/

Bookmark bei Connotea Bookmark bei del.icio.us


Freie Schlagwörter (Englisch): biautomata , almost-equivalence , hyper-minimization , computational complexity
CCS - Klassifikation: F.1.1 , F.1.3 , F.2.2 , F.4.3
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 ; 1401 / 2014
Sprache: Englisch
Erstellungsjahr: 2014
Publikationsdatum: 03.09.2014
Kurzfassung auf Englisch: We compare deterministic finite automata (DFAs) and biautomata under the following two aspects: structural similarities between minimal and hyper-minimal automata, and computational complexity of the minimization and hyper-minimization problem. Concerning classical minimality, the known results such as isomorphism between minimal DFAs, and NL-completeness of the DFA minimization problem carry over to the biautomaton case. But surprisingly this is not the case for hyper-minimization: the similarity between almostequivalent hyper-minimal biautomata is not as strong as it is between almost-equivalent hyper-minimal DFAs. Moreover, while hyper-minimization is NL-complete for DFAs, we prove that this problem turns out to be computationally intractable, i.e., NP-complete, for biautomata.
Lizenz: Veröffentlichungsvertrag für Publikationen ohne Print on Demand