State complexity: Difference between revisions

Revision as of 07:14, 24 March 2017

Revision as of 13:39, 24 March 2017

Line 215:

* 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=0304-3975|doi=10.1016/j.tcs.2012.04.010}}</ref>

* 2NFA: <math>m+n</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2011" />

Line 231:

* 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===