2026-08-21T18:34:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27401 2026-08-21T14:42:38Z ddc:004 open_access

Complexity of Clique-Guarded First-Order Logic with Counting van Bergerem, Steffen Lange, Johannes Friedrich Schweikardt, Nicole First-order logic with counting VC dimension graph dimension algorithmic metatheorems enumeration nowhere dense locally bounded expansion PAC learning 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Steffen van Bergerem and Johannes Friedrich Lange and Nicole Schweikardt 2026 Is Part Of LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2026.20 urn:nbn:de:0030-drops-274012 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.20 eng https://creativecommons.org/licenses/by/4.0/legalcode