2026-09-15T15:44:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25433 2026-09-05T19:16:24Z ddc:004 open_access

Arity Hierarchies for Quantifiers Closed Under Partial Polymorphisms Dawar, Anuj Hella, Lauri Pago, Benedikt finite model theory constraint satisfaction problems generalized quantifiers We investigate the expressive power of generalized quantifiers closed under partial polymorphism conditions motivated by the study of constraint satisfaction problems. We answer a number of questions arising from the work of Dawar and Hella (CSL 2024) where such quantifiers were introduced. For quantifiers closed under partial near-unanimity polymorphisms, we establish hierarchy results clarifying the interplay between the arity of the polymorphisms and of the quantifiers: The expressive power of (𝓁+1)-ary quantifiers closed under 𝓁-ary partial near-unanimity polymorphisms is strictly between the class of all quantifiers of arity 𝓁-1 and 𝓁. We also establish an infinite hierarchy based on the arity of quantifiers with a fixed arity of partial near-unanimity polymorphisms. Finally, we prove inexpressiveness results for quantifiers with a partial Maltsev polymorphism. The separation results are proved using novel algebraic constructions in the style of Cai-Fürer-Immerman and the quantifier pebble games of Dawar and Hella (2024). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Lauri Hella and Benedikt Pago 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.9 urn:nbn:de:0030-drops-254330 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.9 eng https://creativecommons.org/licenses/by/4.0/legalcode