Two-way finite automaton: Difference between revisions

Revision as of 13:01, 9 May 2018

Revision as of 13:02, 9 May 2018

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>

it has been studied by Hartmanis, Lewis, and Stearns (1965).

Aho, Hopcroft, Ullman (1968)<ref>{{cite bookjournal|author1=JAlfred V. HartmanisAho |author2=P.M. {Lewis II },John R.E. StearnsHopcroft | chapterauthor3=HierarchiesJeffrey of MemoryD. LimitedUllman Computations| title=Proc.Time 6thand Ann.Tape IEEEComplexity Symp.of onPushdown SwitchingAutomaton CircuitLanguages| Theoryjournal=Information and Logical DesignControl| year=19651968| volume=13| number=3| pages=179–190186–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;

Aho, Hopcroft, Ullman (1968)

Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages. <ref>{{cite journal|author1=AlfredJim V. AhoGray |author2=JohnMichael EA. HopcroftHarrison |author3=JeffreyOscar DH. UllmanIbarra | title=Time and Tape Complexity ofTwo-Way Pushdown Automaton LanguagesAutomata| journal=Information and Control| year=19681967| volume=1311| number=31–2| pages=186–20630–70| doi=10.1016/s0019-9958(6867)9108790369-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;

Gray, Harrison, and Ibarra (1967) investigated the closure properties of these languages.

<ref>{{cite journal|author1=Jim Gray |author2=Michael A. Harrison |author3=Oscar H. Ibarra | title=Two-Way Pushdown Automata| journal=Information and Control| year=1967| volume=11| number=1–2| pages=30–70| doi=10.1016/s0019-9958(67)90369-5}}</ref>

== References ==