Content deleted Content added
Wrote about 2NFA and the complexity of transforming two-way automata to one-way. |
m →State complexity tradeoffs: Corrected the 2FA to NFA tradeoff |
||
Line 60:
| year = 2005
| conference = MFCS 2005
| editor =
| volume = 3618
| book-title = Mathematical Foundations of Computer Science
Line 66:
| ___location =
| pages = 544-555
| doi = 10.1007/11549345_47
}}</ref> determined that transforming an <math>n</math>-state 2DFA to an equivalent DFA requires <math>n(n^n-(n-1)^n)</math> states in the worst case. If an <math>n</math>-state 2DFA or a 2NFA is transformed to an NFA, the worst-case number of states required is <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>.
==Two-way quantum finite automaton==
| |||