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. 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(n2), which is a superset of the context-sensitive languages. The class of languages accepted by deterministic, nonerasing stack automata is DSPACE(n⋅log(n)). Alternating pushdown automata An alternating pushdown automaton (APDA) is a pushdown automaton with a state set where . States in and are called existential resp. universal. In an existential state an APDA nondeterministically chooses the next state and accepts if at least one of the resulting computations accepts. In a universal state APDA moves to all next states and accepts if all the resulting computations accept. The model was introduced by Chandra, Kozen and Stockmeyer. Ladner, Lipton and Stockmeyer proved that this model is equivalent to EXPTIME i.e. a language is accepted by some APDA if, and only if, it can be decided by an exponential-time algorithm. Aizikowitz and Kaminski introduced synchronized alternating pushdown automata (SAPDA) that are equivalent to conjunctive grammars in the same way as nondeterministic PDA are equivalent to context-free grammars. See also Stack machine Context-free grammar Finite automaton Counter automaton Queue automaton Notes References Section 2.2: Pushdown Automata, pp. 101–114. Jean-Michel Autebert, Jean Berstel, Luc Boasson, Context-Free Languages and Push-Down Automata, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111–174. External links JFLAP, simulator for several types of automata including nondeterministic pushdown automata CoAn, another simulator for several machine types including nondeterministic pushdown automata (C++, Windows, Linux, MacOS) Automata (computation) Models of computation