Deterministic tree-walking-storage automata
Open Access
- 24 February 2026
- journal article
- research article
- Published by Springer Nature in Acta Informatica
- Vol. 63 (1) , 9
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.Keywords
Funding Information
- Justus-Liebig-Universität Gießen
This publication has 31 references indexed in Scilit:
- Tree-Walking-Storage Automata2023
- An Automata Characterisation for Multiple Context-Free Languages2016
- Reversible Limited Automata2015
- On Simulation Cost of Unary Limited Automata2015
- Tree-walking automata cannot be determinizedTheoretical Computer Science, 2006
- Tree-stack automataTheory of Computing Systems, 1996
- Pushdown tree automataTheory of Computing Systems, 1983
- (Semi)alternating stack automataTheory of Computing Systems, 1981
- One way finite visit automataTheoretical Computer Science, 1978
- Checking stacks and context-free programmed grammars accept p-complete languages1974