Editing Pushdown automaton (section)

==Stack automata==
As a generalization of pushdown automata, Ginsburg, Greibach, and Harrison (1967) investigated '''stack automata''', which may additionally step left or right in the input string (surrounded by special endmarker symbols to prevent slipping out), and step up or down in the stack in read-only mode.<ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=Stack Automata and Compiling| journal=J. ACM| year=1967| volume=14| number=1| pages=172–201| doi=10.1145/321371.321385| doi-access=free}}</ref><ref>{{cite journal| author=Seymour Ginsburg, Sheila A. Greibach and Michael A. Harrison| title=One-Way Stack Automata| journal=J. ACM| year=1967| volume=14| number=2| pages=389–418| doi=10.1145/321386.321403| doi-access=free}}</ref> 
A stack automaton is called ''nonerasing'' if it never pops from the stack. The class of languages accepted by nondeterministic, nonerasing stack automata is ''[[NSPACE]]''(''n''<sup>2</sup>), which is a superset of the [[context-sensitive languages#Computational properties|context-sensitive languages]].<ref name="Hopcroft.Ullman.1967">{{cite journal|author1=John E. Hopcroft |author2=Jeffrey D. Ullman | title=Nonerasing Stack Automata| journal=Journal of Computer and System Sciences| year=1967| volume=1| number=2| pages=166–186| doi=10.1016/s0022-0000(67)80013-8| doi-access=free}}</ref> The class of languages accepted by deterministic, nonerasing stack automata is ''[[DSPACE]]''(''n''⋅log(''n'')).<ref name="Hopcroft.Ullman.1967"/>