NFA minimization
In automata theory (a branch of theoretical computer science), NFA minimization is the task of transforming a given nondeterministic finite automaton (NFA) into an equivalent NFA that has a minimum number of states, transitions, or both. While efficient algorithms exist for DFA minimization, NFA minimization is PSPACE-complete. No efficient (polynomial time) algorithms are known, and under the standard assumption P ≠ PSPACE, none exist. The most efficient known algorithm is the Kameda‒Weiner algorithm.
Q214526
automata theory
Concept
Q2878974
theoretical computer science
Concept
Q617295
nondeterministic finite automaton
Concept
Q5204896
DFA minimization
UNK
Q905967
PSPACE-complete
LOC
Q846354
P
MISC
Q500716
PSPACE
ORG
Q97358379
NFA minimization
UNK
Q97358379
NFA minimization
UNK
part of