Deterministic Pushdown Store Machines and Real-Time Computation
Stephen N. Cole · Journal of the ACM · 1971
A comparison is made of the computing capabilities of deterministic pushdown store machines and real-time iterative arrays of finite-state machines.The main result is that every deterministic pushdown store computation can be performed by some (multidimensional) iterative array in real-time.The latter are strictly more powerful since they can recognize the set of palindromes in real-time, which deterministic pushdown store machines cannot do even if permitted unlimited computing time.During the development of the main result, variants of pushdown store machines, the tabulator machines and the n-dimensional pushdown store machines, are introduced.By imposing a real-time constraint and letting the number of tabs and the number of dimensions vary, an infinite hierarchy of pushdown store (deterministic context-free) languages is obtained.