TY  - UNPD
A1  - Malcher, Andreas
T1  - Minimizing finite automata is computationally hard
T2  - Frankfurter Informatik-Berichte ; Nr. 02,6
N2  - It is known that deterministic finite automata (DFAs) can be algorithmically minimized, i.e., a DFA M can be converted to an equivalent DFA M' which has a minimal number of states. The minimization can be done efficiently [6]. On the other hand, it is known that unambiguous finite automata (UFAs) and nondeterministic finite automata (NFAs) can be algorithmically minimized too, but their minimization problems turn out to be NP-complete and PSPACE-complete [8]. In this paper, the time complexity of the minimization problem for two restricted types of finite automata is investigated. These automata are nearly deterministic, since they only allow a small amount of non determinism to be used. On the one hand, NFAs with a fixed finite branching are studied, i.e., the number of nondeterministic moves within every accepting computation is bounded by a fixed finite number. On the other hand, finite automata are investigated which are essentially deterministic except that there is a fixed number of different initial states which can be chosen nondeterministically. The main result is that the minimization problems for these models are computationally hard, namely NP-complete. Hence, even the slightest extension of the deterministic model towards a nondeterministic one, e.g., allowing at most one nondeterministic move in every accepting computation or allowing two initial states instead of one, results in computationally intractable minimization problems.
T3  - Frankfurter Informatik-Berichte - 02, 6 
Y1  - 2002
UR  - http://publikationen.ub.uni-frankfurt.de/frontdoor/index/index/docId/7183
UR  - https://nbn-resolving.org/urn:nbn:de:hebis:30-71676
SN  - 1616-9107
PB  - Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik
CY  - Frankfurt am Main
ER  -