Two-way finite automaton: Difference between revisions

Revision as of 13:27, 1 May 2020

Revision as of 19:44, 13 May 2020

Line 80:

proved that an <math>n</math>-state 2AFA can be converted to a DFA with <math>2^{n2^n}</math> states.

The 2AFA to NFA conversion requires <math>2^{\Theta(n \log n)}</math> states in the worst case,

see [[Viliam Geffert|Geffert]] and [[Alexander Okhotin|Okhotin]].<ref name="GeffertOkhotin2014">{{cite book|last1=Geffert|first1=Viliam|title=Mathematical Foundations of Computer Science 2014|last2=Okhotin|first2=Alexander|chapter=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|series=Lecture Notes in Computer Science|isbn=978-3-662-44521-1}}</ref>

{{unsolved|computer science|Does every <math>n</math>-state 2NFA have an equivalent <math>\operatorname{poly}(n)</math>-state 2DFA?}}

Line 111:

}}</ref> discovered a formal relation between this problem

and the [[L (complexity)|L]] vs. [[NL (complexity)|NL]] open problem,

see [[Kapoutsis, Christos Kapoutsis|Kapoutsis]]<ref>{{cite journal

| last = Kapoutsis

| first = Christos A.