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

---

A note on the expressive power of linear orders

Thomas Schwentick ; Nicole Schweikardt.

This article shows that there exist two particular linear orders such that first-order logic with these two linear orders has the same expressive power as first-order logic with the Bit-predicate FO(Bit). As a corollary we obtain that there also exists a built-in permutation such that first-order&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;]

---

A Strategy for Dynamic Programs: Start over and Muddle through

Samir Datta ; Anish Mukherjee ; Thomas Schwentick ; Nils Vortmeier ; Thomas Zeume.

In the setting of DynFO, dynamic programs update the stored result of a query whenever the underlying data changes. This update is expressed in terms of first-order logic. We introduce a strategy for constructing dynamic programs that utilises periodic computation of auxiliary data from scratch and&nbsp;[&hellip;]

---

Rewriting with Acyclic Queries: Mind Your Head

Gaetano Geck ; Jens Keppeler ; Thomas Schwentick ; Christopher Spinrath.

The paper studies the rewriting problem, that is, the decision problem whether, for a given conjunctive query $Q$ and a set $\mathcal{V}$ of views, there is a conjunctive query $Q'$ over $\mathcal{V}$ that is equivalent to $Q$, for cases where the query, the views, and/or the desired rewriting are&nbsp;[&hellip;]

---