Abstract
In this paper, we introduce a new form of consistency in general constraint satisfaction problems (CSPs), called ω-pairwise-consistency which can be applied to both binary and non-binary constraints. Enforcing ω-pairwise-consistency in a CSP simplifies the problem representation by removing those tuples from the given constraints that will not participate in any solution. Typical CSP solving algorithms can then solve the simplified CSP more efficiently. We show that ω-pairwise-consistency is stronger than some other forms of consistency reported in the literature. We also present an algorithm for achieving ω-pairwise-consistency.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. J. ACM, 30(3):497–513, 1983.
C. Bessiere and M. Cordier. Arc-consistency and arc-consistency again. In Proceedings of AAAI-93, pages 108–113, 1993.
M. Cooper. An optimal k-consistency algorithm. Artificial Intelligence, 41:89–95, 1989.
R. Dechter and J. Pearl. Tree clustering for constraint networks. Artificial Intelligence, 38:353–366, 1989.
R. Dechter and P. van Beek. Local and global relational consistency. In Proceedings of the 1st International Conference on Principles and Practices of Constraint Programming, pages 240–257, Cassis, France, September 1995.
E. Freuder. Synthesizing constraint expressions. Communications of the ACM, 21(11):958–966, 1978.
M. Gyssens. On the complexity of join dependencies. ACM Transactions on Database Systems, 11(1):81–108, 1986.
C. Han and C. Lee. Comments on Mohr and Henderson’s path consistency algorithm. Artificial Intelligence, 36:125–130, 1988.
P. Jegou. On the consistency of general constraint satisfaction problems. In Proceedings of AAAI-93, pages 114–119, 1993.
A. Mackworth. Consistency in networks of relations. Artificial Intelligence, 8(1):99–118, 1977.
A. Mackworth and E. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. Artificial Intelligence, 25(1):65–74, 1985.
D. Maier. The Theory of Relational Databases. Computer Science Press, 1983.
R. Mohr and T. Henderson. Arc and path consistency revisited. Artificial Intelligence, 28:225–233, 1986.
U. Montanari. Networks of constraints: Fundamental properties and applications to picture processing. Information Science, 2:95–123, 1974.
W. Pang. Constraint Structure in Constraint Satisfaction Problems. PhD thesis, University of Regina, Canada, 1998.
W. Pang and S. D. Goodwin. A new synthesis algorithm for solving CSPs. In Proceedings of the 2nd International Workshop on Constraint-Based Reasoning, pages 1–10, Key West, FL, May 1996.
W. Pang and S. D. Goodwin. Constraint-directed backtracking. In The 10th Australian Joint Conference on AI, pages 47–56, Perth, Western Australia, December 1997.
P. Van Hentenryck, Y. Deville, and C. Teng. A generic arc-consistency algorithm and its specialization. Artificial Intelligence, 57:291–321, 1992.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pang, W., Goodwin, S.D. (2000). Consistency in General CSPs. In: Mizoguchi, R., Slaney, J. (eds) PRICAI 2000 Topics in Artificial Intelligence. PRICAI 2000. Lecture Notes in Computer Science(), vol 1886. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44533-1_48
Download citation
DOI: https://doi.org/10.1007/3-540-44533-1_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67925-7
Online ISBN: 978-3-540-44533-3
eBook Packages: Springer Book Archive