24 citations · 33 across the 12 of their papers we have counts for
5 papers · 1 filter
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…
The First-Order Theory of Ground Tree Rewrite Graphs
Stefan Göller, Markus Lohrey
We prove that the complexity of the uniform first-order theory of ground tree rewrite graphs is in ATIME(2^{2^{poly(n)}},O(n)). Providing a matching lower bound, we show that there…
Branching-time model checking of one-counter processes
Stefan Göller, Markus Lohrey
One-counter processes (OCPs) are pushdown processes which operate only on a unary stack alphabet. We study the computational complexity of model checking computation tree logic (CT…
Branching-time model checking of one-counter processes
Stefan Göller, Markus Lohrey
One-counter processes (OCPs) are pushdown processes which operate only on a unary stack alphabet. We study the computational complexity of model checking computation tree logic (CT…
On a Non-Context-Free Extension of PDL
Stefan Göller, Dirk Nowotka
Over the last 25 years, a lot of work has been done on seeking for decidable non-regular extensions of Propositional Dynamic Logic (PDL). Only recently, an expressive extension of…