{"id":"arxiv/2609.37337","url":"https://arxiv.org/abs/2609.37337","tags":["cs.LO","math.LO"],"score":0,"title":"A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures","domain":"cs.LO","source":"arxiv","authors":["Steffen van Bergerem","Martin Grohe","Charlotte Lenz","Nicole Schweikardt"],"reviews":0,"subject":"cs.LO","summary":"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 is much simpler and yields formulas in exactly the same normal form as Gaifman's original theorem. Furthermore, it holds not only for first-order logic, but also for first-order logic with modulo-counting quantifiers and, more generally, for the first-order logic on weighted structures ngFOW+ that is introduced in this article. As an application of our theorem, we give a simplified proof of the algorithmic…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}