Martin Kutrib
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Martin Kutrib has a total of 89 co-authors. Here are the top co-authors by number of shared publications:
Andreas Malcher
59 shared publicationsMarkus Holzer
Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
46 shared publicationsMatthias Wendlandt
36 shared publications- Andreas Malcher
Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany
30 shared publications - Matthias Wendlandt
Institut für Informatik, Universität Gießen
23 shared publications Henning Bordihn
Institut für Informatik, Universität Potsdam, August-Bebel-Straße 89, 14482 Potsdam, Germany
15 shared publications
Latest Publications
- Open Access
- 8 September 2026
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 60, 35
Input-Driven Pushdown Automata with Translucent Input Letters
Input-driven pushdown automata with translucent input letters are investigated. Here, the use of translucent input letters means that the input is processed in several sweeps and that, depending on the current state of the automaton, some input symbols are visible and can be processed, whereas some other symbols are invisible, and may be processed in another sweep. Additionally, the returning mode as well as the non-returning mode are considered, where in the former mode a new sweep must start after processing a visible input symbol. Input-driven pushdown automata differ from traditional pushdown automata by the fact that the actions on the pushdown store (push, pop, nothing) are dictated by the input symbols. We obtain the result that the input-driven nondeterministic model is computationally stronger than the deterministic model both in the returning mode and in the non-returning mode, whereas it is known that the deterministic and the nondeterministic model are equivalent for input-driven pushdown automata without translucency. It also turns out that the non-returning model is computationally stronger than the returning model both in the deterministic and the nondeterministic case. Furthermore, we investigate the closure properties of the language families introduced under the Boolean operations. We obtain a complete picture in the deterministic case and an almost complete picture in the nondeterministic case. Finally, we look at decidability questions and obtain the non-semidecidability of the questions of universality, inclusion, equivalence, and regularity in the nondeterministic case.
- 8 September 2026
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 60, 35
Open AccessInput-Driven Pushdown Automata with Translucent Input Letters
Input-driven pushdown automata with translucent input letters are investigated. Here, the use of translucent input letters means that the input is processed in several sweeps and that, depending on the current state of the automaton, some input symbols are visible and can be processed, whereas some other symbols are invisible, and may be processed in another sweep. Additionally, the returning mode as well as the non-returning mode are considered, where in the former mode a new sweep must start after processing a visible input symbol. Input-driven pushdown automata differ from traditional pushdown automata by the fact that the actions on the pushdown store (push, pop, nothing) are dictated by the input symbols. We obtain the result that the input-driven nondeterministic model is computationally stronger than the deterministic model both in the returning mode and in the non-returning mode, whereas it is known that the deterministic and the nondeterministic model are equivalent for input-driven pushdown automata without translucency. It also turns out that the non-returning model is computationally stronger than the returning model both in the deterministic and the nondeterministic case. Furthermore, we investigate the closure properties of the language families introduced under the Boolean operations. We obtain a complete picture in the deterministic case and an almost complete picture in the nondeterministic case. Finally, we look at decidability questions and obtain the non-semidecidability of the questions of universality, inclusion, equivalence, and regularity in the nondeterministic case.
- 17 July 2026
- Published by Springer Nature
- p. 110-121
State-Limited Inductive Inference of Cellular Automata
- 17 July 2026
- Published by Springer Nature
- p. 110-121
State-Limited Inductive Inference of Cellular Automata
- Open Access
- 13 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1072
On properties of languages accepted by deterministic pushdown automata with translucent input letters
- 13 March 2026
- Published by Elsevier in Theoretical Computer Science
- Vol. 1072
Open AccessOn properties of languages accepted by deterministic pushdown automata with translucent input letters
- Open Access
- 24 February 2026
- Published by Springer Nature in Acta Informatica
- Vol. 63 (1) , 9
Deterministic tree-walking-storage automata
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.
- 24 February 2026
- Published by Springer Nature in Acta Informatica
- Vol. 63 (1) , 9
Open AccessDeterministic tree-walking-storage automata
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.
- 17 September 2025
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- p. 1-27
Reversible Two-Party Computations
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, which means that the automata are also backward deterministic and, thus, are able to uniquely step the computation back and forth. We study the computational capacity of such devices and obtain on the one hand that there are regular languages that cannot be accepted by such systems. On the other hand, such systems can accept even non-semilinear languages. Since the systems communicate by sending messages, we also consider systems where the number of messages sent during a computation is restricted. We obtain a finite hierarchy with respect to the allowed amount of communication inside the reversible classes and separations to general, not necessarily reversible, classes. Finally, we study closure properties and decidability questions and obtain that the questions of emptiness, finiteness, inclusion, and equivalence are not semidecidable if a superlogarithmic amount of communication is allowed.
- 17 September 2025
- Published by World Scientific Pub Co Pte Ltd in International Journal of Foundations of Computer Science
- p. 1-27
Reversible Two-Party Computations
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, which means that the automata are also backward deterministic and, thus, are able to uniquely step the computation back and forth. We study the computational capacity of such devices and obtain on the one hand that there are regular languages that cannot be accepted by such systems. On the other hand, such systems can accept even non-semilinear languages. Since the systems communicate by sending messages, we also consider systems where the number of messages sent during a computation is restricted. We obtain a finite hierarchy with respect to the allowed amount of communication inside the reversible classes and separations to general, not necessarily reversible, classes. Finally, we study closure properties and decidability questions and obtain that the questions of emptiness, finiteness, inclusion, and equivalence are not semidecidable if a superlogarithmic amount of communication is allowed.
- 23 August 2025
- Published by Springer Nature
- p. 252-266
State-Freezing Pushdown Automata
- Open Access
- 17 August 2025
- Published by Springer Nature
- p. 229-243
Subregular Expressions with Two Operations
- 17 August 2025
- Published by Springer Nature
- p. 229-243
Open AccessSubregular Expressions with Two Operations
- Open Access
- 13 August 2025
- Published by Elsevier in Information and Computation
- Vol. 306
Complexity of exclusive nondeterministic finite automata
- 13 August 2025
- Published by Elsevier in Information and Computation
- Vol. 306
Open AccessComplexity of exclusive nondeterministic finite automata
- 29 June 2025
- Published by Springer Nature
- p. 151-165
Two-Way Finite Automata with Translucent Input Letters
- 29 June 2025
- Published by Springer Nature
- p. 151-165
Two-Way Finite Automata with Translucent Input Letters