Content deleted Content added
Line 209:
* NFA to 2DFA: at most <math>O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />
* 2NFA to 2DFA: at most <math>n^{O(\log n)}</math> states, proved by implementing the method of [[Savitch's theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003" />
* UFA to DFA: <math>e^{\Theta(\sqrt[3]{n (\ln n)^2})}</math>, see Okhotin.<ref name="Okhotin2012">{{cite journal|last1=Okhotin|first1=Alexander|title=Unambiguous finite automata over a unary alphabet|journal=Information and Computation|volume=212|year=2012|pages=15–36|issn=0890-5401|doi=10.1016/j.ic.2012.01.003}}</ref>
* NFA to UFA: <math>g(n)+O(n^2)</math>, see Okhotin.<ref name="Okhotin2012" />
| |||