  We study deterministic tree-walking-storage automata, which are finite-state
devices equipped with a tree-like storage. These 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, with the possible
moves of the tree pointer corresponding 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. Here we are
particularly considering the capacities of deterministic tree-walking-storage
automata working in real time. It is shown that even the non-erasing variant
can accept rather complicated unary languages as, for example, the language of
words whose lengths are powers of two, or the language of words whose lengths
are Fibonacci numbers. Comparing the computational capacities with automata
from the classical automata hierarchy, we derive that the families of languages
accepted by real-time deterministic (non-erasing) tree-walking-storage automata
is located between the regular and the deterministic context-sensitive
languages. There is a context-free language that is not accepted by any
real-time deterministic tree-walking-storage automaton. On the other hand,
these devices accept a unary language in non-erasing mode that cannot be
accepted by any classical stack automaton, even in erasing mode and arbitrary
time. Basic closure properties of the induced families of languages are shown.
In particular, we consider Boolean operations (complementation, union,
intersection) and AFL operations (union, intersection with regular languages,
homomorphism, inverse homomorphism, concatenation, iteration). It turns out
that the two families in question have the same properties and, in particular,
share all but one of these closure properties with the important family of
deterministic context-free languages.
