Abstract
In constraint solving for finite domains, efficient set representation is an important issue. In this paper we propose an enhancement of Erwig’s diet representation called the enhanced diet, which represents a finite domain as an AVL tree of intervals. In addition to element insertion and deletion, we show that the domain splitting used for constraints such as X ≤ Y can be done in O(logm) steps by adopting Crane’s Algorithm, where m is the number of intervals, not the number of elements.
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
Puget, J.F., Leconte, M.: Beyond the glass box: Constraints as objects. In: Lloyd, J. (ed.) Logic Programming, pp. 513–527. MIT Press, Cambridge (1995)
Wai, A.: Constraint programming in Java with JSolver. In: The Proceedings of The Practical Application of Constraints Technologies and Logic Programming (PACLP 1999) (1999)
Zhou, N., Nagasawa, I.: An efficient finite-domain constraint solver in Beta-Prolog. Journal of Japanese Society for Artificial Intelligence 9, 275–282 (1994)
Codognet, P., Diaz, D.: Compiling constraints in clp(FD). Journal of Logic Programming 27, 185–226 (1996)
Erwig, M.: Diets for fat sets. Journal of Functional Programming 8, 627–632 (1998)
Knuth, D.E.: The Art of Computer Programming, Sorting and Searching, 2nd edn. vol. 3. Addison Wesley, Longman (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ohnishi, S., Tasaka, H., Tamura, N. (2003). Efficient Representation of Discrete Sets for Constraint Programming. In: Rossi, F. (eds) Principles and Practice of Constraint Programming – CP 2003. CP 2003. Lecture Notes in Computer Science, vol 2833. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-45193-8_79
Download citation
DOI: https://doi.org/10.1007/978-3-540-45193-8_79
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-20202-8
Online ISBN: 978-3-540-45193-8
eBook Packages: Springer Book Archive