Abstract
We propose a variant of the Hierarchical Constraint Logic Programming (HCLP) scheme of Borning, Wilson, and others. We consider compositionality and incrementality in Constraint Logic Programming, introduce HCLP, and present Wilson's proof that it is non-compositional. We define a scheme which uses bags (multisets) called BCH (Bags for the Composition of Hierarchies) for composing together solutions to individual hierarchies; it calculates a superset of the solutions expected from HCLP. We prove that BCH is compositional. We then define FGH (Filters, Guards, Hierarchies), a non-compositional scheme which removes precisely those BCH solutions which are unacceptable to HCLP. Thus we separate HCLP into two parts, one compositional and one non-compositional.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Alan Borning, Bjorn Freeman-Benson, and Molly Wilson. Constraint Hierarchies. Lisp and Symbolic Computation, 5:223–270, 1992.
Alan Borning, Michael Maher, Amy Martindale, and Molly Wilson. Constraint Hierarchies and Logic Programming. In ICLP'89, Lisbon, 1989.
Michel Gangnet and Burton Rosenberg. Constraint Programming and Graph Algorithms. In 2nd International Symposium on Artificial Intelligence and Mathematics, January 1992.
David Gries and Fred Schneider. A Logical Approach to Discrete Math. Springer-Verlag, 1994.
Joxan Jaffar and Jean-Louis Lassez. Constraint Logic Programming. In POPL'87, Munich, 1987.
Michael Jampel. A Compositional Theory of Constraint Hierarchies. Technical Report TCU/CS/1995/5, Department of Computer Science, City University, London, March 1995.
Michael Jampel and Sebastian Hunt. Composition in Hierarchical CLP. In IJCAI'95, Montreal, August 1995.
Michael Jampel. Over-Constrained Systems. PhD thesis, Department of Computer Science, City University, 1996. (Draft, January 1996. Final version to be submitted in June 1996.).
Francisco Menezes, Pedro Barahona, and Philippe Codognet. An Incremental Hierarchical Constraint Solver. In PPCP'93, 1993.
Ken Satoh. Formalizing Soft Constraints by Interpretation Ordering. In ECAI'90, 1990.
Molly Wilson. Hierarchical Constraint Logic Programming. Technical Report 93-05-01, University of Washington, Seattle, May 1993. (PhD Dissertation).
Molly Wilson and Alan Borning. Extending Hierarchical Constraint Logic Programming: Nonmonotonicity and Inter-Hierarchy Comparison. In NACLP'89, 1989.
Molly Wilson and Alan Borning. Hierarchical Constraint Logic Programming. Journal of Logic Programming, 16(3):277–318, July 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jampel, M. (1996). A compositional theory of constraint hierarchies (Operational semantics). 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_22
Download citation
DOI: https://doi.org/10.1007/3-540-61479-6_22
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