NESA

Ginsburg, Greibach, and Harrison [1] have recently proposed a mathematical model for modern compilers which they claim abstracts the essential structure of the compilation process. Their basic model, called a stack automaton (SA) consists of an input tape with end markers, a finite state control, and a stack (Fig. 1). The input head maybe moved either right or left. The stack is similar to a push-down store, and may be modified by erasing symbols from the top or adding symbols at the top. Unlike a push-down store, however, the SA is also allowed to move its stack head into the stack in a read-only mode. In [1] it is shown that every context-sensitive language is accepted by a deterministic SA. Furthermore, it is shown every set accepted by some SA is recursive.

A stack automaton is called nonerasing if no symbol may be erased from the stack.

(1) The deterministic, nonerasing stack automaton is equivalent to the deterministic $n \log n$-bounded Turing machine.

(2) The nondeterministic, nonerasing stack automaton is equivalent to the nondeterministic $n^2$-bounded Turing machine.

— Nonerastng Stack Automata