2026-07-21T12:35:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19666 2024-03-06T11:04:35Z ddc:004 open_access

Quantifiers Closed Under Partial Polymorphisms Dawar, Anuj Hella, Lauri generalized quantifiers constraint satisfaction problems pebble games finite variable logics descriptive complexity theory We study Lindström quantifiers that satisfy certain closure properties which are motivated by the study of polymorphisms in the context of constraint satisfaction problems (CSP). When the algebra of polymorphisms of a finite structure 𝔅 satisfies certain equations, this gives rise to a natural closure condition on the class of structures that map homomorphically to 𝔅. The collection of quantifiers that satisfy closure conditions arising from a fixed set of equations are rather more general than those arising as CSP. For any such conditions 𝒫, we define a pebble game that delimits the distinguishing power of the infinitary logic with all quantifiers that are 𝒫-closed. We use the pebble game to show that the problem of deciding whether a system of linear equations is solvable in ℤ / 2ℤ is not expressible in the infinitary logic with all quantifiers closed under a near-unanimity condition. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Lauri Hella 2024 Is Part Of LIPIcs, Volume 288, 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2024.23 urn:nbn:de:0030-drops-196662 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.23 eng https://creativecommons.org/licenses/by/4.0/legalcode