Complexity of Clique-Guarded First-Order Logic with Counting
2026-06-23 • Logic in Computer Science
Logic in Computer Science
AI summaryⓘ
The authors introduce a new logical language called clique-guarded first-order logic with counting (cgFOC), which is a simpler part of a bigger logic system. They study how complex this logic is by measuring its Vapnik-Chervonenkis (VC) dimension and graph dimension on certain structured data. They also show that this logic can be used efficiently for tasks like answering questions, listing answers, and learning from examples on specific types of graph structures. However, they find that making even small extensions to this logic can make problems much harder, even on simple tree-like structures.
clique-guarded first-order logiccounting logicVapnik-Chervonenkis dimensiongraph dimensionnowhere dense classeslocally bounded expansionquery answeringenumerationPAC learningintractability
Authors
Steffen van Bergerem, Johannes Friedrich Lange, Nicole Schweikardt
Abstract
We introduce clique-guarded first-order logic with counting (cgFOC), a fragment of the first-order logic with counting FOC [Kuske and Schweikardt, LICS 2017], and we study the complexity of this fragment. In particular, we prove computable upper bounds on the Vapnik-Chervonenkis (VC) dimension of cgFOC formulas and on the graph dimension of cgFOC counting terms on nowhere dense classes of relational structures. Furthermore, we show algorithmic metatheorems for cgFOC for query answering, enumeration, and probably approximately correct (PAC) learning for Boolean and multiclass classification problems on classes of locally bounded expansion. On the other hand, we show that a slight extension of cgFOC is already intractable on trees.