Complexity of Clique-Guarded First-Order Logic with Counting
Steffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt · 2026
Read Complexity of Clique-Guarded First-Order Logic with Counting by Steffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24848.txt.
Introduction
Steffen van Bergerem, Johannes Friedrich Lange, and Nicole Schweikardt present clique guarded first order logic with counting and map out its complexity. The logic is a fragment of first order logic with counting, designed so that quantification is guarded by cliques in the underlying structure. The authors prove computable upper bounds on the VC dimension of its formulas. They also bound the graph dimension of its counting terms on nowhere dense classes of relational structures.
Algorithmic metatheorems follow for the logic on classes of locally bounded expansion. Query answering and enumeration become tractable there. PAC learning for Boolean and multiclass classification problems is covered as well. A slight extension of the logic is already intractable, even on trees, the simplest sparse structures. Van Bergerem and colleagues thereby draw a precise boundary: the clique guard is close to the most that can be added before the tractability of counting logic collapses.
Catalog record
| CREATOR | Steffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 300 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.24848