State complexity: Difference between revisions

Revision as of 10:24, 14 October 2018

Revision as of 10:34, 14 October 2018

Line 163:

* 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>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. Raskin<ref name="Raskin2018">{{citeCitation misc|last1=Raskin|first1=Michael|titlecontribution=A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton|series=Proc. ICALP|year=2018|doi=10.4230/LIPIcs.ICALP.2018.138}}</ref> recently proved a superpolynomial 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>