State complexity: Difference between revisions

Revision as of 13:25, 29 May 2022

Revision as of 13:37, 29 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^{2-o(1)}</math> and at most <math>\sqrt{n+1} \cdot 2^{0.5n}</math> states, see OkhotinIndzhev and Kiefer.<ref name="Okhotin2012">{{cite journal |last1=OkhotinIndzhev |first1=AlexanderEmil |last2=Kiefer |first2=Stefan |title=UnambiguousOn finitecomplementing unambiguous automata overand agraphs unarywith many cliques and cocliques alphabet|journal=Information andProcessing Letters Computation|volumedate=2121 August 2022 |yearvolume=2012177 |pagespage=15–36|issn=0890-5401106270 |doi=10.1016/j.icipl.20122022.01106270 |url=https://www.003}}<sciencedirect.com/ref>science/article/pii/S0020019022000278 for|access-date=29 theMay lower2022 bound and Indzhev and Kiefer<|ref name="EmilKiefer2021">{{citeIndzhevKiefer22 arXiv|last1language=Indzhev|first1=Emil|last2=Kiefer|first2=Stefan|eprint=2105.07470|title=On Complementing Unambiguous Automata and Graphs With Many Cliques anden Cocliques|classissn=cs.FL|date=20210020-0190}}</ref> 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>