Content deleted Content added
m →State complexity of operations for finite automata: task, replaced: Soviet Mathematics Doklady → Soviet Mathematics - Doklady using AWB |
→The 2DFA vs. 2NFA problem and logarithmic space: html math formatting doesn't work inside the unsolved template |
||
Line 59:
===The 2DFA vs. 2NFA problem and logarithmic space===
{{unsolved|computer science|Does every <math>n</math>-state 2NFA have an equivalent <math>\operatorname{poly}(n)</math>-state 2DFA?}}
It is an open problem whether all 2NFAs can be converted to 2DFAs
with polynomially many states, i.e. whether there is a polynomial <math>p(n)</math>
| |||