# 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

nonerasingif 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.