The Expressive Power of CSP-Quantifiers

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review


A generalized quantifier QK is called a CSP-quantifier if its defining class K consists of all structures that can be homomorphically mapped to a fixed finite template structure. For all positive integers n ≥ 2 and k, we define a pebble game that characterizes equivalence of structures with respect to the logic Lk∞ω(CSP+n ), where CSP+n is the union of the class Q1 of all unary quantifiers and the class CSPn of all CSP-quantifiers with template structures that have at most n elements. Using these games we prove that for every n ≥ 2 there exists a CSP-quantifier with template of size n + 1 which is not definable in Lω∞ω(CSP+n ). The proof of this result is based on a new variation of the well-known Cai-Fürer-Immerman construction.

Original languageEnglish
Title of host publication31st EACSL Annual Conference on Computer Science Logic, CSL 2023
EditorsBartek Klin, Elaine Pimentel
ISBN (Electronic)9783959772648
Publication statusPublished - 1 Feb 2023
Publication typeA4 Article in conference proceedings
EventAnnual Conference on Computer Science Logic - Warsaw, Poland
Duration: 13 Feb 202316 Feb 2023

Publication series

NameLeibniz International Proceedings in Informatics
ISSN (Electronic)1868-8969


ConferenceAnnual Conference on Computer Science Logic


  • constraint satisfaction problems
  • descriptive complexity theory
  • finite variable logics
  • generalized quantifiers
  • pebble games

Publication forum classification

  • Publication forum level 1

ASJC Scopus subject areas

  • Software

Cite this