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/
Freie Schlagwörter (Englisch):
biautomata , almost-equivalence , hyper-minimization , computational complexity
CCS - Klassifikation:
F.4.3 , F.2.2 , F.1.3 , F.1.1
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
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
