Abstract
In the previous studies, it has been shown that the classical constraint satisfaction problem (CSP) is deductive in nature, and can be formulated as a classical theorem proving problem [1, 10]. Constraint satisfaction problems for which an assignment of values to all variables which satisfy all available constraints is not possible are referred to as over-constrained problems. This paper shows how computing partial solutions to over-constrained problems can be viewed as a default reasoning problem. We propose two methods for translating over-constrained problem specifications with finite domains to two different variants of default logic. We argue that default logic provides the appropriate level of abstraction for representing and analyzing over-constrained problem even if other methods are used for actually computing solutions.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
W. Bibel. Constraint satisfaction from a deductive viewpoint. Artificial Intelligence, 35(3):401–413, July 1988.
J. P. Delgrande and W. K. Jackson. Default logic revisited. In Proc. of the Second International Conference on the Principles of Knowledge Representation and Reasoning, pages 118–127, 1991.
J. P. Delgrande, Torsten Schaub, and W. K. Jackson. An approach to default reasoning based on a first-order conditional logic: Revised report. Artificial Intelligence, 36:63–90, 1988.
Fox, M.: Constraint Directed Search: A Case Study of Job-Shop Scheduling. Morgan Kaufman, 1987.
E. C. Freuder and Richard J. Wallace. Partial constraint satisfaction. Artificial Intelligence, 58:21–70, 1992.
A.K. Ghose, P. Hadjinian, A. Sattar, J. You, and R. Goebel. Iterated belief change: A preliminary report. In Proceedings of Australian Joint Conference on Artificial Intelligence, pages 39–44, Melbourne, Victoria, November 1993. World Scientific Publishing Co.
A.K. Ghose, A. Sattar, and R. Goebel. Default reasoning as partial constraint satisfaction. In Proceedings of Australian Joint Conference on Artificial Intelligence, Armidale, NSW, November 1994. World Scientific Publishing Co.
S. Goodwin and A. Sattar. On computing preferred explanation. In Proceedings of Australian Joint Conference on Artificial Intelligence, pages 45–52, Melbourne, Victoria, November 1993. World Scientific Publishing Co.
H.A. Kautz and B. Selman. Hard problems for simple default logics. In Proc. of the First International Conference on the Principles of Knowledge Representation and Reasoning, pages 189–197, 1989.
A. K. Mackworth. The logic of constraint satisfaction. Artificial Intelligence, 58 (1–3):3–20, December 1992.
R. Reiter. A logic for default reasoning. Artificial Intelligence, 13(1&2):81–132, 1980.
Satoh K.: Formalizing soft constraints by interpretation ordering. In Proc. of the 9th European Conf. on AI, pages 585–590, 1990.
Sattar A. and Goebel R.G.: Constraint Satisfaction as Hypothetical Reasoning. In Proceedings of the Vth International Symposium on Artificial Intelligence Cancun, Mexico, December 1992. AAAI-Press.
Molly Wilson and Alan Borning. Hierarchical constraint logic programming. Journal of Logic Programming, 16:277–318, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sattar, A., Ghose, A.K., Goebel, R. (1996). Specifying over-constrained problems in default logic. In: Jampel, M., Freuder, E., Maher, M. (eds) Over-Constrained Systems. OCS 1995. Lecture Notes in Computer Science, vol 1106. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-61479-6_27
Download citation
DOI: https://doi.org/10.1007/3-540-61479-6_27
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-61479-1
Online ISBN: 978-3-540-68601-9
eBook Packages: Springer Book Archive