Theoretical and practical complexity estimates for local propagation methods in constraint-based programming applications
Abstract
The issues of efficiency and robustness of local propagation methods in conformity to constraint-based programming applications are discussed. Comparative analysis of known algorithms is given and new combined method is proposed. The method allows solving of wider classes of constraint problems for polynomial time. The results of computational experiments are presented to illustrate the method advantages over traditional algorithms.
About the Authors
V. A. Semenov
ISP RAS, Moscow
Russian Federation
Russian Federation
O. V. Sidyaka
ISP RAS, Moscow
Russian Federation
Russian Federation
References
1. Dechter R. Constraint processing. Morgan Kaufmann, San Francisco, 2003.
2. E. Tsang. Foundations of constraint satisfaction. Academic Press Limited, London & San-Diego, 1993.
3. K. Bharat. Supporting the Construction of Distributed, Interoperative, User Interface Applications. Ph.D. Dissertation, Georgia Institute of Technology, 1996.
4. R.D. Hill. The Abstraction-Link-View Paradigm: Using Constraints to Connect User Interfaces to Applications. Proceedings of SIGCHI '92. 1992, pp. 335-342.
5. Joao Pascoal Faria, Raul Moreira Vidal. 1999. Data-driven Active Rules for the Maintenance of Derived Data and Integrity Constraints in User Interfaces to Databases
6. C. M. Hoffman, A. Lomonosov. Decomposition plans for geometric constraint systems. // J. Symbolic Computation. Volume 31. 2001. pp. 367-408.
7. W. Bouma, I. Fudos, C. Hoffmann, J. Cai, R. Paige. A Geometric Constraint Solver. 1995.
8. A. Borning, K. Marriott, P. Stuckey, Y. Xiao. Solving Linear Arithmetic Constraints for User Interface Applications: Algorithm Details. Technical Report 97-06-01, Department of Computer Science and Engineering University of Washington, 1997
9. M. Chetty, K.P. Dabke. Symbolic computations: an overview and application to controller design. // Proceedings of IEEE sponsored international conference on Information, Decision and Control, Adelaide, 8th-10th February, 1999, pp.451–456.
10. I. Fudos. Editable Representations For 2D Geometric Design. 1993
11. B. V. Zanden, An incremental algorithm for satisfying hierarchies of multiway dataflow constraints. // ACM Transactions on Programming Languages and Systems. Volume 18, Issue 1. 1996. 30-72.
12. A. Borning, R. Anderson, B. Freeman-Benson. Indigo: A Local Propagation Algorithm for Inequality Constraints. // In Proceedings of the 1996 ACM Symposium on User Interface Software and Technology, 1996, pp. 129-136.
13. M. Sannella. Skyblue: a multi-way local propagation constraint solver for user interface construction. // Proceedings of the 7th annual ACM symposium on User interface software and technology, 1994, pp. 137-146.
14. J. H. Maloney. Using Constraints for User Interface Construction. Doctoral Thesis. University of Washington. 1992
15. D. Frigioni, A. Marchetti-Spaccamela, U. Nanni. Dynamic algorithms for classes of constraint satisfaction problems. Theor. Comput. Sci. 259, 1-2 (May. 2001), 2001. pp. 287-305.
Review
For citations:
Semenov V.A., Sidyaka O.V. Theoretical and practical complexity estimates for local propagation methods in constraint-based programming applications. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2010;19. (In Russ.)
Email this article 