{"id":"arxiv/2606.11993","url":"https://arxiv.org/abs/2606.11993","tags":["cs.LO","math.LO"],"score":0,"title":"A Rank-Preserving Gaifman Normal Form","domain":"cs.LO","source":"arxiv","authors":["Martin Grohe","Nicole Schweikardt"],"reviews":0,"subject":"cs.LO","summary":"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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-10","reactions":{}}