Metraipolis › archive › dc_960383f53b15
Deciding two-variable logic with global and local Presburger quantification — arXiv:2610.39108
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.39108
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-01T02:39:52.637Z
- SHA-256 of the archived text
6b008703b1d83f8170b800aa0c790a48e30eb4f340fa37b6dc643202b1ca67f4- Stable URL of this page
https://metraipolis.com/documento/dc_960383f53b15
How to cite
Deciding two-variable logic with global and local Presburger quantification — arXiv:2610.39108 — arXiv (en), https://arxiv.org/abs/2610.39108 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_960383f53b15 (Metraipolis archive dc_960383f53b15, sha256 6b008703b1d83f8170b800aa0c790a48e30eb4f340fa37b6dc643202b1ca67f4)
BibTeX
@misc{dc960383f53b15,
title = {Deciding two-variable logic with global and local Presburger quantification — arXiv:2610.39108},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.39108},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_960383f53b15; sha256 6b008703b1d83f8170b800aa0c790a48e30eb4f340fa37b6dc643202b1ca67f4},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.39108. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We look at a two-variable logic over finite graphs that allows Presburger quantifiers: linear arithmetic inequalities between the number of elements that satisfy subformulas. The prior literature shows that closing two-variable logic under Presburger quantification leads to undecidability, while closing under \emph{local quantification} -- the counts are always over neighbors of a given node -- preserves decidability. Here we show decidability of satisfiability for an intermediate logic that allows both local counts and global counts, but where the linear constraints do not mix the two. The proof requires a significant extension of the prior machinery developed for two-variable logic with counting. As a corollary we obtain decidability of satisfiability for an important family of Graph Neural Networks (GNNs). GNNs are a popular graph learning formalism. For example, in a variation of GNNs considered in the past literature, local aggregation is used in each layer to create modified values at each vertex of a graph, and then global aggregation is used in a final layer to obtain a single numerical value for the graph as a whole. Our logic is motivated by the fact that mixing of local counting and global aggregation in GNNs has been shown to lead to undecidability. Our results here show that if global and local aggregation are separated, one regains decidability. Decidability of other static analysis problems, like equivalence of GNNs, follows from the decidability of satisfiability.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.LO, nuovi lavori del giorno).
Categorie arXiv: Logic in Computer Science (cs.LO) ; Logic (math.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.39108 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-01T02:15:58.503Z dalla pagina https://arxiv.org/list/math.LO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).