A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures

Steffen van Bergerem, Martin Grohe, Charlotte Lenz +1

We 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…