Content deleted Content added
Misprints corrected |
Added a section on one-letter alphabet |
||
Line 217:
* 2DFA: between <math>n+1</math> and <math>n+2</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008" />
==Finite automata over a unary alphabet==
State complexity of finite automata with a one-letter (''unary'') alphabet, pioneered by [[Marek Chrobak|Chrobak]],<ref name="Chrobak1986">{{cite journal|last1=Chrobak|first1=Marek|title=Finite automata and unary languages|journal=Theoretical Computer Science|volume=47|year=1986|pages=149–158|issn=03043975|doi=10.1016/0304-3975(86)90142-8}}</ref> is different from the multi-letter case.
Let <math>g(n)=e^{\Theta(\sqrt{n \ln n})}</math> be [[Landau's function]].
===Transformation between models===
For a one-letter alphabet, transformations between different types of finite automata are sometimes more efficient than in the general case.
* 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="KuncOkhotin2011">{{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" />
* 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" />
* NFA to UFA: <math>g(n)+O(n^2)</math>, see Okhotin.<ref name="Okhotin2012" />
===Union===
* DFA: <math>mn</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>m+n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 2DFA: between <math>m+n</math> and <math>2m+n+4</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012">{{cite journal|last1=Kunc|first1=Michal|last2=Okhotin|first2=Alexander|title=State complexity of operations on two-way finite automata over a unary alphabet|journal=Theoretical Computer Science|volume=449|year=2012|pages=106–118|issn=03043975|doi=10.1016/j.tcs.2012.04.010}}</ref>
* 2NFA: <math>m+n</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />
===Intersection===
* DFA: <math>mn</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: <math>mn</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 2DFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />
===Complementation===
* DFA: <math>n</math> states.
* NFA: <math>g(n)+O(n^2)</math> states, Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* UFA: at least <math>n^{2-o(1)}</math> and at most <math>e^{\Theta(\sqrt[3]{n (\ln n)^2})}</math> states, see Okhotin.<ref name="Okhotin2012" />
* 2DFA: at least <math>n</math> and at most <math>2n+3</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: at least <math>n</math> and at most <math>O(n^8)</math> states. The upper bound is by implementing the method of the [[Immerman–Szelepcsényi theorem]], see Geffert, Mereghetti and Pighizzini.<ref name="GeffertMereghetti2007">{{cite journal|last1=Geffert|first1=Viliam|last2=Mereghetti|first2=Carlo|last3=Pighizzini|first3=Giovanni|title=Complementing two-way finite automata|journal=Information and Computation|volume=205|issue=8|year=2007|pages=1173–1187|issn=0890-5401|doi=10.1016/j.ic.2007.01.008}}</ref>
===Concatenation===
* DFA: <math>mn</math> states, see Yu, Zhuang and Salomaa.<ref name="YuZhuang1994" />
* NFA: between <math>m+n-1</math> and <math>m+n</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 2DFA: <math>e^{\Theta(\sqrt{(m+n)\log(m+n)})}</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
* 2NFA: <math>e^{\Theta(\sqrt{(m+n)\log(m+n)})}</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
===Kleene star===
* DFA: <math>(n-1)^2+1</math> states, see Yu, Zhuang and Salomaa. <ref name="YuZhuang1994" />
* NFA: <math>n+1</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />
* 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" />
* 2DFA: <math>\Theta(g(n))</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />
==Further reading==
| |||