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

---

On the complexity of XPath containment in the presence of disjunction, DTDs, and variables

Frank Neven ; Thomas Schwentick.

XPath is a simple language for navigating an XML-tree and returning a set of answer nodes. The focus in this paper is on the complexity of the containment problem for various fragments of XPath. We restrict attention to the most common XPath expressions which navigate along the child and/or&nbsp;[&hellip;]

---