State complexity: Difference between revisions

Revision as of 01:41, 24 March 2017

Revision as of 07:14, 24 March 2017

Line 204:

* NFA to DFA: <math>g(n)+O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />

* 2DFA to DFA: <math>g(n)+O(n)</math> states, see Chrobak<ref name="Chrobak1986" /> and Kunc and Okhotin.<ref name="KuncOkhotin2011KuncOkhotin2011b">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=Describing Periodicity in Two-Way Deterministic Finite Automata Using Transformation Semigroups|volume=6795|year=2011|pages=324–336|issn=0302-9743|doi=10.1007/978-3-642-22321-1_28}}</ref>

* 2NFA to DFA: <math>O(g(n))</math> states, see Mereghetti and [[Giovanni Pighizzini|Pighizzini]].<ref name="MereghettiPighizzini2001">{{cite journal|last1=Mereghetti|first1=Carlo|last2=Pighizzini|first2=Giovanni|title=Optimal Simulations between Unary Automata|journal=SIAM Journal on Computing|volume=30|issue=6|year=2001|pages=1976–1992|issn=0097-5397|doi=10.1137/S009753979935431X}}</ref> and [[Viliam Geffert|Geffert]], Mereghetti and Pighizzini.<ref name="GeffertMereghetti2003">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Converting two-way nondeterministic unary automata into simpler automata|journal=Theoretical Computer Science|volume=295|issue=1-3|year=2003|pages=189–203|issn=0304-3975|doi=10.1016/S0304-3975(02)00403-6}}</ref>

* NFA to 2DFA: at most <math>O(n^2)</math> states, see Chrobak.<ref name="Chrobak1986" />

Line 246:

* UFA: <math>(n-1)^2+1</math> states, see Okhotin.<ref name="Okhotin2012" />

* 2DFA: <math>\Theta((g(n))^2)</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />

* 2DFA2NFA: <math>\Theta(g(n))</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />

==Further reading==