Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems

DOI10.1007/978-3-642-04027-6_10MaRDI QIDQ3644743zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Computer Science Logic
• Computer Science Logic
• Lower bounds for existential pebble games and k-consistency tests
• Lower bounds for existential pebble games and \(k\)-consistency tests
• Arc consistency and friends

Cites work

• scientific article; zbMATH DE number 1007358 (Why is no real title available?)
• scientific article; zbMATH DE number 1775416 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• scientific article; zbMATH DE number 932194 (Why is no real title available?)
• scientific article; zbMATH DE number 1392292 (Why is no real title available?)
• A Sufficient Condition for Backtrack-Free Search
• CSP dichotomy for special triads
• Definability with bounded number of bound variables
• Homogenizable relational structures
• Large finite structures with few \(L^k\)-types
• On the Power of k-Consistency
• Peek arc consistency
• Planar Graphs: Logical Complexity and Parallel Isomorphism Tests
• Ramsey Classes and Homogeneous Structures
• 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
• Theoretical analysis of singleton arc consistency and its extensions

Cited in

(7)

• Lower bounds for existential pebble games and k-consistency tests
• Some new decidability results on positive and negative set constraints
• scientific article; zbMATH DE number 5547861 (Why is no real title available?)
• Computer Science Logic
• On Monotonic Determinacy and Rewritability for Recursive Queries and Views
• Lower bounds for existential pebble games and \(k\)-consistency tests
• Computer Science Logic

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

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