DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2026.36

A Game for Counting Logic Formula Size and an Application to Linear Orders

Authors: Grégoire Fournier and György Turán

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract

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.

Cite as

Grégoire Fournier and György Turán. A Game for Counting Logic Formula Size and an Application to Linear Orders. In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 36:1-36:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{fournier_et_al:LIPIcs.CSL.2026.36,
  author =	{Fournier, Gr\'{e}goire and Tur\'{a}n, Gy\"{o}rgy},
  title =	{{A Game for Counting Logic Formula Size and an Application to Linear Orders}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{36:1--36:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.36},
  URN =		{urn:nbn:de:0030-drops-254612},
  doi =		{10.4230/LIPIcs.CSL.2026.36},
  annote =	{Keywords: Finite Model Theory, Logical Aspects of Computational Complexity}
}

Document

DOI: 10.4230/DagRep.4.5.1

Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201)

Authors: Kira V. Adaricheva, Giuseppe F. Italiano, Hans Kleine Büning, and György Turán

Published in: Dagstuhl Reports, Volume 4, Issue 5 (2014)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 14201 "Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications". The seminar brought together researchers working in various areas of mathematics and computer science, mostly in algebra, logic, date base theory, artificial intelligence and data mining. A key objective of the seminar has been to bring together a critical mass of researchers and to provide a platform for personal contacts and scientific interchange between the different disciplines in an atmosphere that will stimulate collaboration and lead to new partnerships. The goal was to crystallize the main research directions and to disseminate challenging open problems across the different research areas.

Cite as

Kira V. Adaricheva, Giuseppe F. Italiano, Hans Kleine Büning, and György Turán. Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201). In Dagstuhl Reports, Volume 4, Issue 5, pp. 1-26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{adaricheva_et_al:DagRep.4.5.1,
  author =	{Adaricheva, Kira V. and Italiano, Giuseppe F. and Kleine B\"{u}ning, Hans and Tur\'{a}n, Gy\"{o}rgy},
  title =	{{Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201)}},
  pages =	{1--26},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{5},
  editor =	{Adaricheva, Kira V. and Italiano, Giuseppe F. and Kleine B\"{u}ning, Hans and Tur\'{a}n, Gy\"{o}rgy},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.5.1},
  URN =		{urn:nbn:de:0030-drops-46193},
  doi =		{10.4230/DagRep.4.5.1},
  annote =	{Keywords: Horn formulas, directed hypergraphs, lattices, closure system, data bases, implicational systems and concept analysis}
}

Search Results

Documents authored by Turán, György

A Game for Counting Logic Formula Size and an Application to Linear Orders

Abstract

Cite as

Horn formulas, directed hypergraphs, lattices and closure systems: related formalisms and applications (Dagstuhl Seminar 14201)

Abstract

Cite as

Thanks for your feedback!

Could not send message