24 citations · 33 across the 12 of their papers we have counts for
13 papers
Weak Bisimulation Finiteness of Pushdown Systems With Deterministic -Transitions Is 2-ExpTime-Complete
Stefan Göller, Paweł Parys
We consider the problem of deciding whether a given pushdown system all of whose -transitions are deterministic is weakly bisimulation finite, that is, whether it is w…
The -Complexity Of Visibly Pushdown Languages
Stefan Göller, Nathan Grosshans
We study the question of which visibly pushdown languages (VPLs) are in the complexity class and how to effectively decide this question. Our contribution is to int…
On long words avoiding Zimin patterns
Arnaud Carayol, Stefan Göller
A pattern is encountered in a word if some infix of the word is the image of the pattern under some non-erasing morphism. A pattern is unavoidable if, over every finite alphabe…
The Complexity of Bisimulation and Simulation on Finite Systems
Moses Ganardi, Stefan Göller, Markus Lohrey
In this paper the computational complexity of the (bi)simulation problem over restricted graph classes is studied. For trees given as pointer structures or terms the (bi)simulation…
A Polynomial-Time Algorithm for Reachability in Branching VASS in Dimension One
Stefan Göller, Christoph Haase, Ranko Lazić +1
Branching VASS (BVASS) generalise vector addition systems with states by allowing for special branching transitions that can non-deterministically distribute a counter value betwee…
Reachability in Two-Dimensional Vector Addition Systems with States is PSPACE-complete
Michael Blondin, Alain Finkel, Stefan Göller +2
Determining the complexity of the reachability problem for vector addition systems with states (VASS) is a long-standing open problem in computer science. Long known to be decidabl…