Two-way finite automaton: Difference between revisions

Revision as of 17:22, 29 January 2023

Latest revision as of 06:31, 14 April 2025

(One intermediate revision by one other user not shown)

Line 128:

| pages = 195–202

| doi = 10.1016/0022-0000(80)90034-3

| doi-access= free

}}</ref> constructed a sequence of languages, each accepted by an n-state NFA, yet which is not accepted by any sweeping automata with fewer than <math>2^n</math> states.

Line 142:

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| doi-access=free}}</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| doi-access=free}}</ref>

== References ==

{{reflist}}

[[Category:Finite-state automatamachines]]