Constraint Satisfaction with Counting Quantifiers

DOI10.1137/140981332zbMath1392.68206OpenAlexW4244440046MaRDI QIDQ5256528

Juraj Stacho, Barnaby Martin, Florent R. Madelaine

Publication date: 18 June 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://eprints.mdx.ac.uk/16767/1/WebCSR2014.pdf

zbMATH Keywords

computational complexityretractioncounting quantifiersquantified constraint satisfaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

The Complexity of Counting Quantifiers on Equality Languages ⋮ Unnamed Item ⋮ Quantified Constraints in Twenty Seventeen ⋮ Quantitative Logic Reasoning ⋮ The complexity of counting quantifiers on equality languages

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of surjective homomorphism problems-a survey
• The edge intersection graphs of paths in a tree
• The complexity of constraint satisfaction games and QCSP
• On the complexity of H-coloring
• List homomorphisms to reflexive graphs
• A note on the metric properties of trees
• List homomorphisms and circular arc graphs
• Constraint Satisfaction with Counting Quantifiers
• QCSP on Partially Reflexive Forests
• First-Order Model Checking Problems Parameterized by the Model
• The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• Undirected connectivity in log-space
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• QCSP on Partially Reflexive Cycles – The Wavy Line of Tractability
• Constraint Satisfaction with Counting Quantifiers 2
• Computer Science Logic
• Classifying the Complexity of Constraints Using Finite Algebras
• Space complexity of list H-colouring: a dichotomy
• The complexity of satisfiability problems
• Logical Approaches to Computational Barriers

This page was built for publication: Constraint Satisfaction with Counting Quantifiers