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

CREATORSteffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE300 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24848

Browse the full library · About the Tower of Babel