23 citations · 52 across the 13 of their papers we have counts for
13 papers
Deterministic Real-Time Tree-Walking-Storage Automata
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 lin…
Reversible Two-Party Computations
Martin Kutrib, Andreas Malcher
Deterministic synchronous systems consisting of two finite automata running in opposite directions on a shared read-only input are studied with respect to their ability to perform…
Reversible Computations of One-Way Counter Automata
Martin Kutrib, Andreas Malcher
Deterministic one-way time-bounded multi-counter automata are studied with respect to their ability to perform reversible computations, which means that the automata are also backw…
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers
Martin Kutrib, Andreas Malcher, Carlo Mereghetti +1
An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the out…
Input-Driven Double-Head Pushdown Automata
Markus Holzer, Martin Kutrib, Andreas Malcher +1
We introduce and study input-driven deterministic and nondeterministic double-head pushdown automata. A double-head pushdown automaton is a slight generalization of an ordinary pus…
On the Descriptional Complexity of Operations on Semilinear Sets
Simon Beier, Markus Holzer, Martin Kutrib
We investigate the descriptional complexity of operations on semilinear sets. Roughly speaking, a semilinear set is the finite union of linear sets, which are built by constant and…