State complexity: Difference between revisions

Revision as of 09:07, 18 May 2021

Revision as of 20:44, 30 June 2021

Line 49:

* SVFA to DFA: <math>\Theta(3^{n/3})</math> states, see Jirásková and [[Giovanni Pighizzini|Pighizzini]]<ref name="JiráskováPighizzini2011">{{cite journal|last1=Jirásková|first1=Galina|last2=Pighizzini|first2=Giovanni|title=Optimal simulation of self-verifying automata by deterministic automata|journal=Information and Computation|volume=209|issue=3|year=2011|pages=528–535|issn=0890-5401|doi=10.1016/j.ic.2010.11.017}}</ref>

* 2DFA to DFA: <math>n(n^n-(n-1)^n)</math> states, see [[Christos Kapoutsis|Kapoutsis]].<ref name="Kapoutsis2005">{{Cite book|last1=Kapoutsis|first1=Christos|title=Mathematical Foundations of Computer Science 2005|series=Lecture Notes in Computer Science|volume=3618|year=2005|pages=544–555|issn=0302-9743|doi=10.1007/11549345_47|isbn=978-3-540-28702-5|chapter=Removing Bidirectionality from Nondeterministic Finite Automata}}</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="Birget1993a">{{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" />

** 2NFA to NFA accepting the complement: <math>O(4^n)</math> states, see [[Moshe Vardi|Vardi]].<ref name="Vardi1989">{{cite journal|last1=Vardi|first1=Moshe Y.|title=A note on the reduction of two-way automata to one-way automata|journal=Information Processing Letters|volume=30|issue=5|year=1989|pages=261–264|issn=0020-0190|doi=10.1016/0020-0190(89)90205-6|citeseerx=10.1.1.60.464}}</ref>