TY - GEN

T1 - The Expressive Power of CSP-Quantifiers

AU - Hella, Lauri

N1 - Publisher Copyright:
© Lauri Hella; licensed under Creative Commons License CC-BY 4.0.

PY - 2023/2/1

Y1 - 2023/2/1

N2 - 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.

AB - 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.

KW - constraint satisfaction problems

KW - descriptive complexity theory

KW - finite variable logics

KW - generalized quantifiers

KW - pebble games

U2 - 10.4230/LIPIcs.CSL.2023.25

DO - 10.4230/LIPIcs.CSL.2023.25

M3 - Conference contribution

AN - SCOPUS:85148334230

T3 - Leibniz International Proceedings in Informatics

BT - 31st EACSL Annual Conference on Computer Science Logic, CSL 2023

A2 - Klin, Bartek

A2 - Pimentel, Elaine

T2 - Annual Conference on Computer Science Logic

Y2 - 13 February 2023 through 16 February 2023

ER -