Two-way finite automaton: Difference between revisions

Revision as of 11:21, 6 February 2019

Revision as of 14:58, 20 February 2019

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 journalbook|last1=Geffert|first1=Viliam|title=Mathematical Foundations of Computer Science 2014|last2=Okhotin|first2=Alexander|titlechapter=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 144:

==Two-way pushdown automaton==

A [[pushdown automaton]] that is allowed to move either way on its input tape is called '''two-way pushdown automaton''' ('''2PDA''');<ref>{{cite book|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=978-0-201-02988-X8}} Here: p.124; this paragraph is omitted in the 2003 edition.</ref>

it has been studied by Hartmanis, Lewis, and Stearns (1965).<ref>{{cite book|author1=J. Hartmanis |author2=P.M. Lewis II, R.E. Stearns| chapter=Hierarchies of Memory Limited Computations| title=Proc. 6th Ann. IEEE Symp. on Switching Circuit Theory and Logical Design| year=1965| pages=179–190}}</ref>

Aho, Hopcroft, Ullman (1968)<ref>{{cite journal|author1=Alfred V. Aho |author2=John E. Hopcroft |author3=Jeffrey D. Ullman | title=Time and Tape Complexity of Pushdown Automaton Languages| journal=Information and Control| year=1968| volume=13| number=3| pages=186–206| doi=10.1016/s0019-9958(68)91087-5}}</ref>