State complexity: Difference between revisions

Revision as of 20:14, 23 March 2017

Revision as of 23:17, 23 March 2017

Line 154:

* UFA: between <math>mn+m+n</math> and <math>O(n 2^{0.79m})</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016">{{cite journal|last1=Jirásek|first1=Jozef|title=Operations on Unambiguous Finite Automata|last2=Jirásková|first2=Galina|last3=Šebej|first3=Juraj|volume=9840|year=2016|pages=243–255|issn=0302-9743|doi=10.1007/978-3-662-53132-7_20|series=Lecture Notes in Computer Science|isbn=978-3-662-53131-0}}</ref>

* SVFA: <math>mn</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015">{{cite journal|last1=Jirásek|first1=Jozef Štefan|last2=Jirásková|first2=Galina|last3=Szabari|first3=Alexander|title=Operations on Self-Verifying Finite Automata|volume=9139|year=2015|pages=231–261|issn=0302-9743|doi=10.1007/978-3-319-20297-6_16}}</ref>

* 2DFA: between <math>m+n</math> and <math>4m+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>

Line 168 ⟶ 170:

* UFA: <math>mn</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />

* SVFA: <math>mn</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />

* 2DFA: between <math>m+n</math> and <math>m+n+1</math> states, see Kunc and Okhotin.<ref name="KuncOkhotin2012" />

Line 183 ⟶ 187:

* UFA: at least <math>n^{2-o(1)}</math> and at most <math>O(2^{0.79n})</math> states, 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> for the lower bound and Jirásek, Jirásková and Šebej<ref name="JirásekJirásková2016" /> for the upper bound.

* SVFA: <math>n</math> states, by exchanging accepting and rejecting states.

* 2DFA: at least <math>n</math> and at most <math>4n</math> states, 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>

Line 195 ⟶ 201:

* UFA: <math>\frac{3}{4} 2^{m+n}-1</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />

* SVFA: <math>\Theta(3^{n/3}2^m)</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />

* 2DFA: at least <math>\frac{2^{\Omega(n)}}{\log m}</math> and at most <math>2m^{m+1}\cdot 2^{n^{n+1}}</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008">{{cite journal|last1=Jirásková|first1=Galina|title=On the State Complexity of Operations on Two-Way Finite Automata|last2=Okhotin|first2=Alexander|volume=5257|year=2008|pages=443–454|issn=0302-9743|doi=10.1007/978-3-540-85780-8_35|series=Lecture Notes in Computer Science|isbn=978-3-540-85779-2}}</ref>

Line 205 ⟶ 213:

* UFA: <math>\frac{3}{4} 2^n</math> states, see Jirásek, Jirásková and Šebej.<ref name="JirásekJirásková2016" />

* SVFA: <math>\frac{3}{4}2^n</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />

* 2DFA: at least <math>\frac{1}{n}2^{\frac{n}{2}-1}</math> and at most <math>2^{O(n^{n+1})}</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008" />

Line 215 ⟶ 225:

* UFA: <math>n</math> states.

* SVFA: <math>2n+1</math> states, see Jirásek, Jirásková and Szabari.<ref name="JirásekJirásková2015" />

* 2DFA: between <math>n+1</math> and <math>n+2</math> states, see Jirásková and Okhotin.<ref name="JiráskováOkhotin2008" />