State complexity: Difference between revisions

Revision as of 08:58, 21 February 2019

Revision as of 17:54, 6 January 2021

Line 55:

* AFA to NFA: <math>2^n</math> states, see Fellah, Jürgensen and Yu.<ref name="FellahJürgensen1990">{{cite journal|last1=Fellah|first1=A.|last2=Jürgensen|first2=H.|last3=Yu|first3=S.|title=Constructions for alternating finite automata∗|journal=International Journal of Computer Mathematics|volume=35|issue=1–4|year=1990|pages=117–132|issn=0020-7160|doi=10.1080/00207169008803893}}</ref>

* 2AFA to DFA: <math>2^{n2^n}</math>, see [[Richard E. Ladner|Ladner]], [[Richard J. Lipton|Lipton]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="LadnerLipton1984">{{cite journal|last1=Ladner|first1=Richard E.|last2=Lipton|first2=Richard J.|last3=Stockmeyer|first3=Larry J.|title=Alternating Pushdown and Stack Automata|journal=SIAM Journal on Computing|volume=13|issue=1|year=1984|pages=135–155|issn=0097-5397|doi=10.1137/0213010}}</ref>

* 2AFA to NFA: <math>2^{\Theta(n \log n)}</math>, see [[Viliam Geffert|Geffert]] and [[Alexander Okhotin|Okhotin]].<ref name="GeffertOkhotin2014">{{Cite book|last1=Geffert|first1=Viliam|title=Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata|last2=Okhotin|first2=Alexander|volume=8634|year=2014|pages=291–302|issn=0302-9743|doi=10.1007/978-3-662-44522-8_25|series=Lecture Notes in Computer Science|isbn=978-3-662-44521-1}}</ref>

===The 2DFA vs. 2NFA problem and logarithmic space===