Abstract
Unit TVPI constraints are sufficiently expressive for many problems: for example in scheduling and temporal reasoning. We give an algorithm for incremental satisfiability of unit TVPI constraints. Not only is this algorithm efficiently implementable, it also supports efficient implementation of entailment detection, including constraints entailed by disjunctive constraints, and projection. Finally, for use in a CLP system, constraints more general than unit TVPI must be handled, though not necessarily in a complete way. Our algorithm naturally extends to (non-unit) TVPI constraints, and it can be augmented with a bounds-propagation technique for constraints more general than TVPI. An implementation of the solver is underway as part of the continuing development of CLP(R) [9].
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Apsvall, B., Shiloach, Y.: A polynomial time algorithm for solving systems of linear inequalities with two variables per inequality. SIAM J. of Computing. 9 (1980) 827–845.
Bledsoe, W.W.: A new method for proving certain Presburger formulas. Proc. of the 4th Joint Conf. on Artificial Intelligence. (1975) 15–21.
Cohen, E., Megiddo, N.: Improved Algorithms for Linear Inequalities with Two Variables per Inequality. Proc. of the 23rd Symp. on Theory of Computing. (1991) 145–155.
Dincbas, M., Van Hentenryck, P., Simonis, H., Aggoun, A.: The Constraint Logic Programming Language CHIP. Proc. of the 2nd Intl. Conf. on Fifth Generation Computer Systems. (1988) 249–264.
Harvey, W.: Personal communication. (1994).
Van Hentenryck, P., Deville, Y., Teng, C.: A generic arc-consistency algorithm and its specializations. Artificial Intelligence. 57 (1992) 291–321.
Van Hentenryck, P., Saraswat, V., Deville.Y.: Constraint Processing in cc(FD). Manuscript (1991).
Huynh, T., Lassez, J-L., McAloon,K.: Simplification and elimination of redundant linear arithmetic constraints. Proc. North American Conf. on Logic Programming. (1989) 37–51.
Jaffar, J., Michaylov, S., Stuckey, P.J., Yap, R.H.C.: The CLP(R) Language and System. ACM Trans. on Programming Languages. 14(3) (1992) 339–395.
Kapur, D., Nie, X.: Reasoning about Numbers in Tecton. Eighth Intl. Symp. on methodologies for intelligent systems. To appear (1994).
Lagarias, J.C.: The Computational Complexity of Simultaneous Diophantine Approximation Problems. SIAM J. of Computing. 14(1) (1985) 196–209.
Lassez, J-L., Maher, M.J.: On Fourier's Algorithm for Linear Arithmetic Constraints. J. of Automated Reasoning. 9 (1992) 373–379.
Le Pape, C.: Des Systèmes d'Ordonnancement Flexibles et Opportunistes. Thesis. Université de Paris-Sud. 1988.
Mackworth, A.K.: Constraint Satisfaction. Wiley. New York. 1987.
Pugh, W.: The Omega test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis. Comm. ACM. 8 (1992) 102–114.
Pugh, W., Wonnacott, D.: Experiences with Constraint-based Array Dependence Analysis. Proc. Principles and Practice of Constraint Programming. PCP'94. 1994.
Pratt, V.R.: Two easy theories whose combination is hard. Tech. Report. Massachusetts Institute of Technology. Cambridge. Mass. 1977.
Revesz, P.Z.: A Closed Form for Datalog Queries with Integer Order. Proc. Intl. Conf. on Database Theory. 1990.
Rosenkrantz, D.J., Hunt, H.B. III.: Processing Conjunctive Predicates and Queries. Proc. Conf. on Very Large Data Bases. (1980) 64–72.
Shostak, R.: Deciding Linear Inequalities by Computing Loop Residues. J. of the ACM. 28(4) (1981) 769–779.
Shostak, R.: On the SUP-INF Method for Proving Presburger Formulas. J. of the ACM. 24(4) (1977) 529–543.
Toman, D., Chomicki, J., Rogers, D.S.: Datalog with Periodicity Constraints. Proc. Intl. Logic Programming Symp. To appear (1994).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Jaffar, J., Maher, M.J., Stuckey, P.J., Yap, R.H.C. (1994). Beyond finite domains. In: Borning, A. (eds) Principles and Practice of Constraint Programming. PPCP 1994. Lecture Notes in Computer Science, vol 874. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58601-6_92
Download citation
DOI: https://doi.org/10.1007/3-540-58601-6_92
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58601-2
Online ISBN: 978-3-540-49032-6
eBook Packages: Springer Book Archive