State complexity: Difference between revisions

Revision as of 14:07, 29 May 2022

Revision as of 17:07, 31 May 2022

Line 164:

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

* NFA: <math>2^n</math> states, see Birget.<ref name="Birget1993b">{{cite journal|last1=Birget|first1=Jean-Camille|title=Partial orders on words, minimal elements of regular languages, and state complexity|journal=Theoretical Computer Science|volume=119|issue=2|year=1993|pages=267–291|issn=0304-3975|doi=10.1016/0304-3975(93)90160-U}}</ref>

* UFA: at least <math>n^{\tilde{\Omega}(\log n)}</math> states, see Göös, Kiefer and Yuan,<ref name="GoosKieferYuan2022">{{cite journalarxiv |last1=Göös |first1=Mika |last2=Kiefer |first2=Stefan |last3=Yuan |first3=Weiqiang |title=Lower Bounds for Unambiguous Automata via Communication Complexity |journal=arXiv:2109.09155 [cs] |date=12 February 2022 |urlarxiv=https://arxiv.org/abs/2109.09155}}</ref>, and at most <math>\sqrt{n+1} \cdot 2^{0.5n}</math> states, see Indzhev and Kiefer.<ref>{{cite journal |last1=Indzhev |first1=Emil |last2=Kiefer |first2=Stefan |title=On complementing unambiguous automata and graphs with many cliques and cocliques |journal=Information Processing Letters |date=1 August 2022 |volume=177 |page=106270 |doi=10.1016/j.ipl.2022.106270 |url=https://www.sciencedirect.com/science/article/pii/S0020019022000278 |access-date=29 May 2022 |ref=IndzhevKiefer22 |language=en |issn=0020-0190}}</ref>

* 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 230:

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

* NFA: <math>g(n)+O(n^2)</math> states, see Holzer and Kutrib.<ref name="HolzerKutrib2003" />

* UFA: at least <math>n^{(\log \log \log n)^{\Theta(1)}}</math> states, see Raskin,<ref name="Raskin2018">{{cite conference |last1=Raskin|first1=Michael|title=A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton|pages=138:1–138:11|book-title=Proc. ICALP 2018|year=2018|doi=10.4230/LIPIcs.ICALP.2018.138}}</ref>, 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"/>