.png){kind=icon}
.png){kind=icon}
Return
Deterministic tree-walking-storage automata
.png){kind=icon}
OA
AI
DOI：10.1007/s00236-026-00522-5.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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:
STACK AUTOMATA
LIMITED AUTOMATA
PUSHDOWN
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.