Efficient Pushdown Cellular Automata: Universality, Time and Space Hierarchies
Martin Kutrib
Pushdown cellular automata are a stack augmented generalization of classical cellular automata. They are a massively parallel and universal model, where the number of processing elements is bounded by the length of input data. We investigate encodings of pushdown cellular automata which are efficiently verifiable in real time. These encodings allow the construction of efficient universal devices. They are applied to computational complexity in order to show tight and strict time and stack-space hierarchies.