Теоретические и экспериментальные оценки сложности методов локального распространения в задачах программирования в ограничениях
Аннотация
Список литературы
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.
Рецензия
Для цитирования:
Семенов В.А., Сидяка О.В. Теоретические и экспериментальные оценки сложности методов локального распространения в задачах программирования в ограничениях. Труды Института системного программирования РАН. 2010;19.
For citation:
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.)