Search

• < Previous
• 1
• Next >

---

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

---

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

---