4 results
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 […]
Published on December 14, 2011
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) […]
Published on December 29, 2015
Martin Grohe ; Nicole Schweikardt.
Succinctness is a natural measure for comparing the strength of different logics. Intuitively, a logic L_1 is more succinct than another logic L_2 if all properties that can be expressed in L_2 can be expressed in L_1 by formulas of (approximately) the same size, but some properties can be expressed […]
Published on June 29, 2005
Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin.
A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, where $n$ is the size of the database. Typical examples are databases of bounded degree or of degree bounded by $\log n$. It is known that over a […]
Published on May 10, 2022