A Rank-Preserving Gaifman Normal Form

arXiv (Cornell University)

Abstract

We introduce a rank measure for first-order logic and prove a "rank-preserving'" version of Gaifman's theorem. Compared to earlier "rank-preserving locality theorems'" (in particular, [Grohe, Kreutzer, Siebertz, JACM 2017]), our theorem is not only much simpler, but also yields formulas in exactly the same normal form as Gaifman's original theorem. As an application of this theorem, we give a simplified proof of the main result of [Grohe, Kreutzer, Siebertz, JACM 2017] that first-order properties of nowhere-dense structures can be decided in almost linear time.

Authors 2

1. Martin Grohe Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

2. Nicole Schweikardt

   Humboldt-Universität zu Berlin

   Affiliation as printed

   Humboldt-Universität zu Berlin