2026-10-06T10:54:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25461 2026-03-19T12:28:54Z ddc:004 open_access

A Game for Counting Logic Formula Size and an Application to Linear Orders Fournier, Grégoire Turán, György Finite Model Theory Logical Aspects of Computational Complexity Ehrenfeucht-Fraïssé (EF) games are a basic tool in finite model theory for proving definability lower bounds, with many applications in complexity theory and related areas. They have been applied to study various logics, giving insights on quantifier rank and other logical complexity measures. In this paper, we present an EF game to capture formula size in counting logic with a bounded number of variables. The game combines games introduced previously for counting logic quantifier rank due to Immerman and Lander, and for first-order formula size due to Adler and Immerman, and Hella and Väänänen. The game is used to prove an extension of a formula size lower bound of Grohe and Schweikardt for distinguishing linear orders, from 3-variable first-order logic to 3-variable counting logic. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Grégoire Fournier and György Turán 2026 Is Part Of LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2026.36 urn:nbn:de:0030-drops-254612 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.36 eng https://creativecommons.org/licenses/by/4.0/legalcode