Holzer, MarkusMarkusHolzerJakobi, SebastianSebastianJakobi2022-09-122014-09-032022-09-122014http://nbn-resolving.de/urn:nbn:de:hebis:26-opus-110561https://jlupub.ub.uni-giessen.de/handle/jlupub/7530http://dx.doi.org/10.22029/jlupub-6964We 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.enIn Copyrightbiautomataalmost-equivalencehyper-minimizationcomputational complexityddc:004