Abstract
This paper discusses the complexity of constraint satisfaction, and the effect of information hiding. On the one hand, powerful constraint satisfaction is necessarily global, and tends to break information hiding. On the other hand, preserving strict information hiding increases the complexity of constraint satisfaction, or severely limits the power of the constraint solver. Ultimately, under strict information hiding, constraint satisfaction on complex objects cannot be guaranteed.
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
Sara Baase. Computer Algorithms: Introduction to Design and Analysis. Addison-Wesley, 1978.
Grady Booch. Object-Oriented Analysis and Design — with applications. The Benjamin/Cummings Publishing, 1994.
C. Choppy, S. Kaplan, and M. Soria. Complexity analysis of term-rewriting systems. Theoretical Computer Science, 67(2/3):261–282, 1989.
Eric Cournarie and Michel Beaudouin-Lafon. Alien: a prototype-based constraint system. In Laffra et al. [11], pages 92–110.
Jacques Davy. Go, a graphical and interactive C++ toolkit for application data presentation and editing. In Proceedings 5th Annual Technical Conference on the X Window System, 1991.
R. Dechter and J. Pearl. Network-based heuristics for constraint satisfaction problems. Al, 34:1–38, 1988.
Bjorn N. Freeman-Benson and Alan Borning. Integrating constraints with an object-oriented language. In O. Lehrmann Madsen, editor, Proceedings ECOOP’92,LNCS 615, pages 268–286. Springer-Verlag, 1992.
Eugene C. Freuder. A sufficient condition for backtrack-free search. Journal of the ACM, 29(1):24–32, January 1982.
Hans-Werner Güsgen and Joachim Hertzberg. Some fundamental properties of local constraint propagation. AI,36:237–247, 1988.
Quinton Hoole and Edwin Blake. OOCS - constraints in an object oriented environment. In [24], pages 215–230, 1994.
C. Laffra, E. H. Blake, V. de Mey, and X. Pintado, editors. Object Oriented Programming for Graphics, Focus on Computer Graphics. Springer, 1995.
Chris Laffra and Jan van den Bos. Propagators and concurrent constraints. OOPS Messenger, 2(2):68–72, April 1991.
Wm. Leler. Constraint Programming Languages. Addison-Wesley, 1988.
Richard J. Lipton. Dna solution of hard computational problems. Science, 268:542–545, April 1995.
A. K. Mackworth. Consistency in networks of relations. AI,8:99–118, 1977.
A. K. Mackworth and E. Freuder. The complexity of some polynomial network consistency algorithms for constraint satisfaction problems. AI, 25:65–74, 1985.
R. Mohr and T. C. Henderson. Arc and path consistency revisited. AI, 28:225–233, 1986.
John R. Rankin. A graphics object oriented constraint solver. In Laffra et al. [11], pages 71–91.
Michael Sannella. Constraint Satisfaction and Debugging for Interactive User Interfaces. PhD thesis, University of Washington, Seattle, Washington, 1994.
Ivan E. Sutherland. Sketchpad: A man-machine graphical communication system. In Proceedings of the Spring Joint Computer Conference, Detroit, Michigan, May 21–231963, pages 329–345. AFIPS Press, 1963.
Edward Tsang. Foundations of Constraint Satisfaction. Academic Press, 1993.
Remco C. Veltkamp and Edwin H. Blake. Event-based.constraints: coordinate.satisfaction -> object.solution. In [24], pages 251–262, 1994.
Michael Wilk. Equate: an object-oriented constraint solver. In Proceedings OOPSLA’91, pages 286–298, 1991.
P. Wisskirchen, editor. Proceedings 4th Eurographics Workshop on Object-Oriented Graphics, Sintra, Portugal, May 1994.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1995 Springer-Verlag/Wien
About this paper
Cite this paper
Veltkamp, R.C., Kelleners, R.H.M.C. (1995). Information Hiding and the Complexity of Constraint Satisfaction. In: Veltkamp, R.C., Blake, E.H. (eds) Programming Paradigms in Graphics. Eurographics. Springer, Vienna. https://doi.org/10.1007/978-3-7091-9457-7_5
Download citation
DOI: https://doi.org/10.1007/978-3-7091-9457-7_5
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-82788-8
Online ISBN: 978-3-7091-9457-7
eBook Packages: Springer Book Archive