Search

• < Previous
• 1
• Next >

---

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 is some fixed ground tree rewrite graph whose first-order theory is hard for ATIME(2^{2^{poly(n)}},poly(n)) with&nbsp;[&hellip;]

---

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 problem is complete for logarithmic space or NC$^1$, respectively. This solves an open problem from Balc\'azar,&nbsp;[&hellip;]

---