Quantifiers closed under partial polymorphisms

DOI10.4230/LIPICS.CSL.2024.23MaRDI QIDQ6856032zbMATH OpenFDO

Authors Anuj Dawar, Lauri Hella

Publication date 19 February 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.CSL.2024.23

zbMATH Keywords

constraint satisfaction problemsdescriptive complexity theoryfinite variable logicsgeneralized quantifierspebble games

Mathematics Subject Classification ID

Logic in computer science (03B70) Computer science (68-XX)

Cites work

• A dichotomy theorem for nonuniform CSPs
• A proof of the CSP dichotomy conjecture
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Approximations of isomorphism and logics with linear-algebraic operators
• Closed systems of functions and predicates
• Enhancing fixed point logic with cardinality quantifiers
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 863501 (Why is no real title available?)
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Logical hierarchies in PTIME
• Partial Polymorphisms and Constraint Satisfaction Problems
• Pebble games with algebraic rules
• Rank logic is dead, long live rank logic!
• Strong partial clones and the time complexity of SAT problems
• The algebras of partial functions and their invariants
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• The expressive power of CSP-quantifiers

Cited in

(1)

• Linear algebraic quantifiers

This page was built for publication: Quantifiers closed under partial polymorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6856032)