Two-way finite automaton: Difference between revisions

Revision as of 02:35, 6 December 2018

Revision as of 11:21, 6 February 2019

Line 145:

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=0-201-02988-X}} 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>

and Cook (1971)<ref>{{cite book| author=S.A. Cook| chapter=Linear Time Simulation of Deterministic Two-Way Pushdown Automata| title=Proc. IFIP Congress| year=1971| pages=75–80| publisher=North Holland}}</ref> characterized the class of languages recognizable by deterministic ('''2DPDA''') and non-deterministic ('''2NPDA''') two-way pushdown automata;