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;]

---

Tree-Automatic Well-Founded Trees

Martin Huschenbett ; Alexander Kartzow ; Jiamou Liu ; Markus Lohrey.

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-founded tree is strictly below omega^omega. Moreover, we make a step towards proving that the ranks of tree-automatic&nbsp;[&hellip;]

---

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 verification of real-timed systems. It was recently shown that the path checking problem for MTL, when evaluated over finite&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;]

---