Name
Abstract | ||
|---|---|---|
We prove that minimizing finite automata is NP-hard for almost all classes of automata that extend the class of deterministic finite automata. More specifically, we show that minimization is NP-hard for all finite automata classes that subsume the class of @dNFAs which accept strings of length at most three. Here, @dNFAs are the finite automata that are unambiguous, allow at most one state q with a non-deterministic transition for at most one alphabet symbol a, and are allowed to visit state q at most once in a run. As a corollary, we also obtain that the same result holds for all finite automata classes that subsume that class of finite automata that are unambiguous, have at most two initial states, and accept strings of length at most two. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.jcss.2011.03.001 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
state q,finite automaton,finite automata class,alphabet symbol,non-deterministic transition,initial state,tractability frontier,deterministic finite automaton,nfa minimization,finite automata | Discrete mathematics,Quantum finite automata,Automata theory,Combinatorics,Nondeterministic finite automaton,Nested word,Mobile automaton,Deterministic finite automaton,Computer science,DFA minimization,ω-automaton | Journal |
Volume | Issue | ISSN |
78 | 1 | Journal of Computer and System Sciences |
Citations | PageRank | References |
19 | 0.72 | 33 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henrik Björklund | 1 | 311 | 20.41 |
| wim martens | 2 | 609 | 29.78 |