23 citations · 59 across the 13 of their papers we have counts for
9 papers · 1 filter
On the Accepting State Complexity of Operations on Permutation Automata
Christian Rauch, Markus Holzer
We investigate the accepting state complexity of deterministic finite automata for regular languages obtained by applying one of the following operations to languages accepted by p…
On the Complexity of Intersection Non-emptiness for Star-Free Language Classes
Emmanuel Arrighi, Henning Fernau, Stefan Hoffmann +4
In the Intersection Non-Emptiness problem, we are given a list of finite automata over a common alphabet as input, and the goal is to determine whether some…
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…
More Structural Characterizations of Some Subregular Language Families by Biautomata
Markus Holzer, Sebastian Jakobi
We study structural restrictions on biautomata such as, e.g., acyclicity, permutation-freeness, strongly permutation-freeness, and orderability, to mention a few. We compare the ob…
Cooperating Distributed Grammar Systems of Finite Index Working in Hybrid Modes
Henning Fernau, Rudolf Freund, Markus Holzer
We study cooperating distributed grammar systems working in hybrid modes in connection with the finite index restriction in two different ways: firstly, we investigate cooperating…