On stack-augmented polyautomata

Abstract

A stack augmented generalization of cellular automata, the pushdown cellular automata, are investigated. We are studying the language accepting capabilities of such devices. Closure properties of real­time, linear­time and unrestricted time language families are shown. The relationships of these families with each other and to languages of sequential automata are considered.