Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems

DOI10.1007/978-3-642-04027-6_10zbMath1257.03052OpenAlexW1924671213MaRDI QIDQ3644743

Albert Atserias, Mark Weyer

Publication date: 12 November 2009

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04027-6_10

Mathematics Subject Classification ID

Logic in computer science (03B70) Decidability of theories and sets of sentences (03B25)

Related Items (1)

On Monotonic Determinacy and Rewritability for Recursive Queries and Views

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Homogenizable relational structures
• Definability with bounded number of bound variables
• Peek arc consistency
• Theoretical analysis of singleton arc consistency and its extensions
• Large finite structures with few \(L^k\)-types
• CSP dichotomy for special triads
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• A Sufficient Condition for Backtrack-Free Search
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Ramsey Classes and Homogeneous Structures
• On the Power of k-Consistency

This page was built for publication: Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems