State complexity: Difference between revisions

Revision as of 19:53, 22 March 2017

Revision as of 20:00, 22 March 2017

Line 54:

* 2DFA to DFA: <math>n(n^n-(n-1)^n)</math> states, see [[Christos Kapoutsis|Kapoutsis]].<ref name="Kapoutsis2005">{{cite journal|last1=Kapoutsis|first1=Christos|title=Removing Bidirectionality from Nondeterministic Finite Automata|volume=3618|year=2005|pages=544–555|issn=0302-9743|doi=10.1007/11549345_47}}</ref> Earlier construction by [[John Cedric Shepherdson|Shepherdson]]<ref name="Shepherdson1959">{{cite journal|last1=Shepherdson|first1=J. C.|title=The Reduction of Two-Way Automata to One-Way Automata|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=198–200|issn=0018-8646|doi=10.1147/rd.32.0198}}</ref> used more states, and an earlier lower bound by Moore<ref name="Moore1971">{{cite journal|last1=Moore|first1=F.R.|title=On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata|journal=IEEE Transactions on Computers|volume=C-20|issue=10|year=1971|pages=1211–1214|issn=0018-9340|doi=10.1109/T-C.1971.223108}}</ref> was smaller.

* 2DFA to NFA: <math>\binom{2n}{n+1} = O(\frac{4^n}{\sqrt{n}})</math>, see Kapoutsis.<ref name="Kapoutsis2005" /> Earlier construction by [[Jean-Camille Birget|Birget]] <ref name="Birget1993Birget1993a">{{cite journal|last1=Birget|first1=Jean-Camille|title=State-complexity of finite-state devices, state compressibility and incompressibility|journal=Mathematical Systems Theory|volume=26|issue=3|year=1993|pages=237–269|issn=0025-5661|doi=10.1007/BF01371727}}</ref> used more states.

* 2NFA to NFA: <math>\binom{2n}{n+1}</math>, see Kapoutsis.<ref name="Kapoutsis2005" />

Line 180:

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

* NFA: <math>2^n</math> states, see Birget.<ref name="Birget1993Birget1993b">{{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.