14 citations · 74 across the 41 of their papers we have counts for
11 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…
Path Checking for MTL and TPTL over Data Words
Shiguang Feng, Markus Lohrey, Karin Quaas
Metric temporal logic (MTL) and timed propositional temporal logic (TPTL) are quantitative extensions of linear temporal logic, which are prominent and widely used in the verificat…
Satisfiability of ECTL* with tree constraints
Claudia Carapelle, Shiguang Feng, Alexander Kartzow +1
Recently, we have shown that satisfiability for with constraints over is decidable using a new technique. This approach reduces the satisfiability pr…
Satisfiability of CTL* with constraints
Claudia Carapelle, Alexander Kartzow, Markus Lohrey
We show that satisfiability for CTL* with equality-, order-, and modulo-constraints over Z is decidable. Previously, decidability was only known for certain fragments of CTL*, e.g.…
Tree-Automatic Well-Founded Trees
Martin Huschenbett, Alexander Kartzow, Jiamou Liu +1
We investigate tree-automatic well-founded trees. Using Delhomme's decomposition technique for tree-automatic structures, we show that the (ordinal) rank of a tree-automatic well-f…
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…