Search Results

Documents authored by Lange, Johannes Friedrich

Document
DOI: 10.4230/LIPIcs.MFCS.2026.20
Complexity of Clique-Guarded First-Order Logic with Counting

Authors: Steffen van Bergerem, Johannes Friedrich Lange, and Nicole Schweikardt

Published in: LIPIcs, Volume 386, 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)

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.
Cite as

Steffen van Bergerem, Johannes Friedrich Lange, and Nicole Schweikardt. Complexity of Clique-Guarded First-Order Logic with Counting. In 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 386, pp. 20:1-20:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{vanbergerem_et_al:LIPIcs.MFCS.2026.20,
  author =	{van Bergerem, Steffen and Lange, Johannes Friedrich and Schweikardt, Nicole},
  title =	{{Complexity of Clique-Guarded First-Order Logic with Counting}},
  booktitle =	{51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026)},
  pages =	{20:1--20:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-442-0},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{386},
  editor =	{Kouck\'{y}, Michal and Petrișan, Daniela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2026.20},
  URN =		{urn:nbn:de:0030-drops-274012},
  doi =		{10.4230/LIPIcs.MFCS.2026.20},
  annote =	{Keywords: First-order logic with counting, VC dimension, graph dimension, algorithmic metatheorems, enumeration, nowhere dense, locally bounded expansion, PAC learning}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact