Search

• < Previous
• 1
• Next >

---

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

---

Existential Definability over the Subword Ordering

Pascal Baumann ; Moses Ganardi ; Ramanathan S. Thinniyam ; Georg Zetzsche.

We study first-order logic (FO) over the structure consisting of finite words over some alphabet $A$, together with the (non-contiguous) subword ordering. In terms of decidability of quantifier alternation fragments, this logic is well-understood: If every word is available as a constant, then even&nbsp;[&hellip;]

---