On the Power of k-Consistency

DOI10.1007/978-3-540-73420-8_26zbMath1171.68720OpenAlexW1603707154MaRDI QIDQ5428816

Andrei A. Bulatov, Victor Dalmau, Albert Atserias

Publication date: 28 November 2007

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-73420-8_26

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (13)

On Monotonic Determinacy and Rewritability for Recursive Queries and Views ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ On the speed of constraint propagation and the time complexity of arc consistency testing ⋮ On Singleton Arc Consistency for CSPs Defined by Monotone Patterns ⋮ Tree projections and structural decomposition methods: minimality and game-theoretic characterization ⋮ On singleton arc consistency for CSPs defined by monotone patterns ⋮ Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems ⋮ How many variables are needed to express an existential positive query? ⋮ Tree Projections: Game Characterization and Computational Aspects ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ On the hardness of solving edge matching puzzles as SAT or CSP problems ⋮ Structural tractability of enumerating CSP solutions ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

This page was built for publication: On the Power of k-Consistency