Skip to content
DraconiticResearch
Search Sources API
197,768 studies31 sourcesUpdated 3 min ago
PreprintCC BY 4.0arXiv

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

  • Steffen van Bergerem
  • Martin Grohe
  • Charlotte Lenz
  • Nicole Schweikardt
Open at sourcePDFDOICite

Abstract

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 meta-theorem of [Grohe, Kreutzer, Siebertz, JACM 2017] stating that first-order properties of nowhere dense structures can be decided in almost-linear time. Our locality theorem for the weight logic ngFOW+ can be seen as an essential step toward such a meta-theorem for this logic.

Related

  1. A Rank-Preserving Gaifman Normal Form
    Martin Grohe, Nicole Schweikardt
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  2. Anisotropic-Length-Preserving Weighted Anisotropic Curvature Flows
    Zhishuai Liu, Guoxin Wei
    arXivPreprintarXiv licenceFull textGeometry & topologyarXiv
  3. Harmonicity of normal almost contact metric structures
    M. Benyounes, T. Levasseur, E. Loubeau +1
    Differential Geometry and its ApplicationsPeer-reviewedCC BY 4.0Full textGeneral mathematicsHAL
  4. Universal weighted sampling of positive and normal operator orbits
    Jian Wu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv
  5. Optimal weighted sampling of positive and normal operator orbits
    Jian Wu
    arXivPreprintarXiv licenceFull textAnalysis & PDEsarXiv

Cite

BibTeXRIS
BibTeX
@misc{bergerem2026rankpreserving,
  title = {{A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures}},
  author = {Steffen van Bergerem and Martin Grohe and Charlotte Lenz and Nicole Schweikardt},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2609.37337},
  eprint = {2609.37337},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2609.37337},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures
AU  - Steffen van Bergerem
AU  - Martin Grohe
AU  - Charlotte Lenz
AU  - Nicole Schweikardt
PY  - 2026
DA  - 2026/09/29
PB  - arXiv
DO  - 10.48550/arxiv.2609.37337
UR  - https://arxiv.org/abs/2609.37337
AB  - 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 meta-theorem of [Grohe, Kreutzer, Siebertz, JACM 2017] stating that first-order properties of nowhere dense structures can be decided in almost-linear time. Our locality theorem for the weight logic ngFOW+ can be seen as an essential step toward such a meta-theorem for this logic.
ER  -