Skip to content
DraconiticResearch
Search Sources API
201,683 studies31 sourcesUpdated 56 min ago
PreprintarXiv licencearXiv

A Rank-Preserving Gaifman Normal Form

  • Martin Grohe
  • Nicole Schweikardt
Open at sourcePDFDOICite

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.

Related

  1. A Rank-Preserving Gaifman Normal Form for First-Order Logic on Weighted Structures
    Steffen van Bergerem, Martin Grohe, Charlotte Lenz +1
    arXivPreprintCC BY 4.0Full textLogic & foundationsarXiv
  2. Plane Cremona maps preserving a Euclidean volume form
    Marc Abboud, Jérémy Blanc, Stéphane Lamy
    arXivPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryarXiv
  3. On the Rank of Normal Functions on Pointed Curves
    Lorenzo Fassina
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv
  4. Simultaneous Williamson's normal form for positive operators
    Rudra Kamat, Anmary Tonny
    arXivPreprintCC BY 4.0Full textAnalysis & PDEsarXiv
  5. Matrix equivalence to Smith normal form: new theoretical results for multivariate polynomial matrices
    Dong Lu, Yuanyuan Ruan, Dingkang Wang +1
    arXivPreprintarXiv licenceFull textAlgebra & number theoryarXiv

Cite

BibTeXRIS
BibTeX
@misc{grohe2026rankpreserving,
  title = {{A Rank-Preserving Gaifman Normal Form}},
  author = {Martin Grohe and Nicole Schweikardt},
  howpublished = {arXiv},
  year = {2026},
  month = jun,
  doi = {10.48550/arxiv.2606.11993},
  eprint = {2606.11993},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2606.11993},
}
RIS
TY  - UNPB
TI  - A Rank-Preserving Gaifman Normal Form
AU  - Martin Grohe
AU  - Nicole Schweikardt
PY  - 2026
DA  - 2026/06/10
PB  - arXiv
DO  - 10.48550/arxiv.2606.11993
UR  - https://arxiv.org/abs/2606.11993
AB  - 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.
ER  -