## Minimizing finite automata is computationally hard

- 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.

Author: | Andreas Malcher |
---|---|

URN: | urn:nbn:de:hebis:30-71676 |

ISSN: | 1616-9107 |

Parent Title (German): | Frankfurter Informatik-Berichte ; Nr. 02,6 |

Series (Serial Number): | Frankfurter Informatik-Berichte (02, 6) |

Publisher: | Johann Wolfgang Goethe-Univ., Fachbereich Biologie und Informatik, Inst. für Informatik |

Place of publication: | Frankfurt am Main |

Document Type: | Working Paper |

Language: | English |

Year of Completion: | 2002 |

Year of first Publication: | 2002 |

Publishing Institution: | Universitätsbibliothek Johann Christian Senckenberg |

Release Date: | 2009/10/16 |

Page Number: | IV, 16 S. |

HeBIS-PPN: | 219726256 |

Institutes: | Informatik und Mathematik / Informatik |

Dewey Decimal Classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 004 Datenverarbeitung; Informatik |

Licence (German): | Deutsches Urheberrecht |