State complexity: Difference between revisions

Content deleted Content added
Page created
 
Line 36:
The following results are known.
 
* NFA to DFA: <math>2^n</math> states. This is the [[subset construction]] by [[Michael Rabin|Rabin]] and [[Dana Scott|Scott]], <ref name="RabinScott1959">{{cite journal|last1=Rabin|first1=M. O.|last2=Scott|first2=D.|title=Finite Automata and Their Decision Problems|journal=IBM Journal of Research and Development|volume=3|issue=2|year=1959|pages=114–125|issn=0018-8646|doi=10.1147/rd.32.0114}}</ref> proved optimal by [[Oleg Lupanov|Lupanov]].<ref>{{cite journal
| last = Lupanov
| first = Oleg B.
Line 57:
* 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}}</ref>,
 
* AFA to DFA: <math>2^{2^n}</math> states, see [[Ashok K. Chandra|Chandra]], [[Dexter Kozen|Kozen]] and [[Larry Stockmeyer|Stockmeyer]].<ref name="ChandraKozen1981">{{cite journal|last1=Chandra|first1=Ashok K.|last2=Kozen|first2=Dexter C.|last3=Stockmeyer|first3=Larry J.|title=Alternation|journal=Journal of the ACM|volume=28|issue=1|year=1981|pages=114–133|issn=00045411|doi=10.1145/322234.322243}}</ref>
 
* 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 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 journal|last1=Geffert|first1=Viliam|last2=Okhotin|first2=Alexander|title=Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata|volume=8634|year=2014|pages=291–302|issn=0302-9743|doi=10.1007/978-3-662-44522-8_25}}</ref>
 
 
 
==The 2DFA vs. 2NFA problem and logarithmic space==