state_complexity (449B)
1 # State complexity 2 3 https://en.wikipedia.org/wiki/State_complexity 4 5 - For [automaton_complement] of an [automaton] with n [states] on a binary alphabet you may need 2^n states 6 - [minimization] / [canonical_automata] 7 - for [DFAs]: can be done in [PTIME] 8 - (quibble about whether it should be [complete_automata] or not) 9 - for [NFAs]: [pspace]-complete 10 - [upward_closure_state_complexity] 11 - [downward_closure_state_complexity] 12 13 Up: [automata]