Deterministic tree-walking-storage automata

Abstract We introduce and investigate tree-walking-storage automata, which are finite-state devices equipped with a tree-like storage. The automata are generalized stack automata, where the linear stack storage is replaced by a non-linear tree-like stack. Therefore, tree-walking-storage automata have the ability to explore the interior of the tree storage without altering the contents, where the possible moves of the tree pointer correspond to those of tree-walking automata. In addition, a tree-walking-storage automaton can append (push) non-existent descendants to a tree node and remove (pop) leaves from the tree. As for classical stack automata, we also consider non-erasing and checking variants. As a first step to investigate these models we consider the computational capacities of deterministic one-way variants. In particular, a primary focus lies on comparing the different variants of tree-walking-storage automata as well as with classical stack automata, enabling us to draw a complete picture. Basic closure properties of the induced families of languages are shown. In particular, we consider Boolean operations and several AFL operations.