Minimizing nfa's and regular expressions
| Autor: | Georg Schnitger, Gregor Gramlich |
|---|---|
| Rok vydání: | 2007 |
| Předmět: |
Discrete mathematics
Unary operation Computer Networks and Communications Applied Mathematics Theoretical Computer Science Computational complexity Combinatorics Deterministic finite automaton DFA minimization Computational Theory and Mathematics Approximability Quantum finite automata Automata and formal languages Nondeterministic finite automaton Regular expression Generalized nondeterministic finite automaton PSPACE Mathematics |
| Zdroj: | Journal of Computer and System Sciences. 73(6):908-923 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2006.11.002 |
| Popis: | We show inapproximability results concerning minimization of nondeterministic finite automata (nfa's) as well as of regular expressions relative to given nfa's, regular expressions or deterministic finite automata (dfa's).We show that it is impossible to efficiently minimize a given nfa or regular expression with n states, transitions, respectively symbols within the factor o(n), unless P=PSPACE. For the unary case, we show that for any δ>0 it is impossible to efficiently construct an approximately minimal nfa or regular expression within the factor n1−δ, unless P=NP.Our inapproximability results for a given dfa with n states are based on cryptographic assumptions and we show that any efficient algorithm will have an approximation factor of at least npoly(logn). Our setup also allows us to analyze the minimum consistent dfa problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect