research-article

Arc consistency and friends

Authors:

Hubie Chen,

Victor Dalmau,

Berit GrußienAuthors Info & Claims

Journal of Logic and Computation, Volume 23, Issue 1

Pages 87 - 108

https://doi.org/10.1093/logcom/exr039

Published: 01 February 2013 Publication History

Abstract

A natural and established way to restrict the constraint satisfaction problem is to fix the relations that can be used to pose constraints; such a family of relations is called a constraint language. In this article, we study arc consistency, a heavily investigated inference method, and three extensions thereof from the perspective of constraint languages. We conduct a comparison of the studied methods on the basis of which constraint languages they solve, and we present new polynomial-time tractability results for singleton arc consistency, the most powerful method studied.

Cited By

View all

Ciardo LSobocinski PLago UEsparza J(2024)Quantum advantage and CSP complexityProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662118(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662118
Carbonnel CCohen DCooper MŽivný S(2019)On Singleton Arc Consistency for CSPs Defined by Monotone PatternsAlgorithmica10.1007/s00453-018-0498-281:4(1699-1727)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0498-2
Jguirim WNaanaa WCooper M(2018)A polynomial relational class of binary CSPAnnals of Mathematics and Artificial Intelligence10.1007/s10472-017-9566-683:1(1-20)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10472-017-9566-6
Show More Cited By

Recommendations

Arc consistency for soft constraints

The notion of arc consistency plays a central role in constraint satisfaction [R. Dechter, Constraint Processing, Morgan Kaufmann, San Mateo, CA, 2003]. It is known since the introduction of valued and semi-ring constraint networks in 1995 that the ...
Maintaining Arc-Consistency within Dynamic Backtracking
CP '02: Proceedings of the 6th International Conference on Principles and Practice of Constraint Programming

Most of complete search algorithms over Constraint Satisfaction Problems (csp) are based on Standard Backtracking. Two main enhancements of this basic scheme have been studied: first, to integrate constraint propagation as mac which maintains arc ...
Arc-Consistency in Constraint Satisfaction Problems: A Survey
CIMSIM '10: Proceedings of the 2010 Second International Conference on Computational Intelligence, Modelling and Simulation

Arc consistency (AC) is very important in Constraint Satisfaction Problems (CSPs). Several algorithms have been made to deal with arc consistency, the most known is the Maintaining arc consistency algorithm (MAC). The usefulness of AC processing was ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of Logic and Computation

Journal of Logic and Computation Volume 23, Issue 1

February 2013

303 pages

ISSN:0955-792X

EISSN:1465-363X

Issue’s Table of Contents

Publisher

Oxford University Press, Inc.

United States

Publication History

Published: 01 February 2013

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Ciardo LSobocinski PLago UEsparza J(2024)Quantum advantage and CSP complexityProceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/3661814.3662118(1-15)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3661814.3662118
Carbonnel CCohen DCooper MŽivný S(2019)On Singleton Arc Consistency for CSPs Defined by Monotone PatternsAlgorithmica10.1007/s00453-018-0498-281:4(1699-1727)Online publication date: 1-Apr-2019
https://dl.acm.org/doi/10.1007/s00453-018-0498-2
Jguirim WNaanaa WCooper M(2018)A polynomial relational class of binary CSPAnnals of Mathematics and Artificial Intelligence10.1007/s10472-017-9566-683:1(1-20)Online publication date: 1-May-2018
https://dl.acm.org/doi/10.1007/s10472-017-9566-6
Chen HMüller M(2017)One Hierarchy Spawns AnotherACM Transactions on Computational Logic10.1145/314380518:4(1-37)Online publication date: 3-Nov-2017
https://dl.acm.org/doi/10.1145/3143805
Chen HLarose B(2017)Asking the Metaquestions in Constraint TractabilityACM Transactions on Computation Theory10.1145/31347579:3(1-27)Online publication date: 4-Oct-2017
https://dl.acm.org/doi/10.1145/3134757
Kong SLi SLi YLong Z(2017)On tree-preserving constraintsAnnals of Mathematics and Artificial Intelligence10.1007/s10472-017-9552-z81:3-4(241-271)Online publication date: 1-Dec-2017
https://dl.acm.org/doi/10.1007/s10472-017-9552-z
Carbonnel C(2016)The meta-problem for conservative Mal'tsev constraintsProceedings of the Thirtieth AAAI Conference on Artificial Intelligence10.5555/3016100.3016377(3376-3382)Online publication date: 12-Feb-2016
https://dl.acm.org/doi/10.5555/3016100.3016377
Kozik MKoskinen EGrohe MShankar N(2016)Weak consistency notions for all the CSPs of bounded widthProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2934510(633-641)Online publication date: 5-Jul-2016
https://dl.acm.org/doi/10.1145/2933575.2934510
Carbonnel CCooper M(2016)Tractability in constraint satisfaction problemsConstraints10.1007/s10601-015-9198-621:2(115-144)Online publication date: 1-Apr-2016
https://dl.acm.org/doi/10.1007/s10601-015-9198-6
Bessiere CCarbonnel CHebrard EKatsirelos GWalsh T(2013)Detecting and exploiting subproblem tractabilityProceedings of the Twenty-Third international joint conference on Artificial Intelligence10.5555/2540128.2540197(468-474)Online publication date: 3-Aug-2013
https://dl.acm.org/doi/10.5555/2540128.2540197

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

Cited By

Recommendations

Arc consistency for soft constraints

Maintaining Arc-Consistency within Dynamic Backtracking

Arc-Consistency in Constraint Satisfaction Problems: A Survey

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations