UMUwe Meyer

Uwe Meyer

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Uwe Meyer has a total of 12 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Compiling Roopl++ to HSSA

    by Lukas Gail, Uwe Meyer, Tristan Schönhals

  • Open Access

    Deterministic tree-walking-storage automata

    by Martin Kutrib, Uwe Meyer

    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.

  • Open Access

    Deterministic real-time tree-walking-storage automata

    by Martin Kutrib, Uwe Meyer

    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 double Fibonacci numbers. Comparing the computational capacities with automata from the classical automata hierarchy, we derive that the family of languages accepted by real-time deterministic (non-erasing) tree-walking-storage automata is located between the regular and the deterministic context-sensitive languages. Moreover, the families are incomparable with the families of context-free and growing context-sensitive languages. It turns out that the devices under consideration accept unary languages 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 and AFL operations. 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. Then, we consider the computational capacity of the counterpart to counter- and stack-counter automata, where the set of stack symbols is a singleton. Finally, we explore several decidability problems and show, that even for devices with a single tree symbol, the problems are all non-semidecidable by reductions of non-semidecidable problems of Turing machines.

  • Open Access

    Context-Free Binding Grammars

    by Björn Lötters, Uwe Meyer

  • Open Access

    Deterministic Real-Time Tree-Walking-Storage Automata

    by Martin Kutrib, Uwe Meyer

    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.


  • Syntax checking either way

    by Martin Kutrib, Uwe Meyer

  • Optimizing Reversible Programs

    by Niklas Deworetzki, Martin Kutrib, Uwe Meyer, Pia-Doreen Ritzke