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

---

Preservation and decomposition theorems for bounded degree structures

Frederik Harwath ; Lucas Heimberg ; Nicole Schweikardt.

We provide elementary algorithms for two preservation theorems for first-order sentences (FO) on the class \^ad of all finite structures of degree at most d: For each FO-sentence that is preserved under extensions (homomorphisms) on \^ad, a \^ad-equivalent existential (existential-positive)&nbsp;[&hellip;]

---