Variations of a new machine model
Jan Van Leeuwen · 1976
Motivated by an elementary programming system for formal language generation, we propose a generalized a pushdown acceptor which uses both a checking stack and a pushdown store in original manner. In the analysis of the machine-model parallel rewriting appears to be a fundamental tool for breaking the implicit recursion-structure. Variations of the machine-model (in the sense of Cook) lead to a natural hierarchy of machines defining DLOG, NLOG, P, NP, and PSPACE, showing different ways in which one class may be considered a restriction of another (as anticipated also in Galil's work on hierarchies of complete problems). Various applications in language theory and in the study of complexity classes are discussed.