Search

• < Previous
• 1
• Next >

---

Two-Variable Logic with Two Order Relations

Thomas Schwentick ; Thomas Zeume.

It is shown that the finite satisfiability problem for two-variable logic over structures with one total preorder relation, its induced successor relation, one linear order relation and some further unary relations is EXPSPACE-complete. Actually, EXPSPACE-completeness already holds for structures&nbsp;[&hellip;]

---

Dynamic Complexity of Parity Exists Queries

Nils Vortmeier ; Thomas Zeume.

Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynFO of Patnaik and Immerman. Can this be generalised to other or even all queries that are definable in first-order logic&nbsp;[&hellip;]

---