Pushdown store machines and real-time computation
- 1 January 1969
- proceedings article
- Published by Association for Computing Machinery (ACM)
- p. 233-245
- https://doi.org/10.1145/800169.805438
Abstract
A comparison is made of the computing capabilities of pushdown store machines and real-time iterative arrays of finite-state machines with the following results. Every pushdown store computation can be performed by some iterative array in real time. The latter are strictly more powerful, since they can recognize the set of palindromes in real time, which is impossible for pushdown-store machines even without a real-time constraint. Versions of pushdown store machines, the tabulator machines and the n-dimensional pushdown store machines, are introduced during the development. By imposing a real-time constraint and letting the number of tabs and the number of dimensions vary, these form infinite hierarchies whose unions are equivalent to the pushdown store machine.This publication has 0 references indexed in Scilit: