Nothing Special   »   [go: up one dir, main page]

Skip to main content

Beyond finite domains

  • Conference paper
  • First Online:
Principles and Practice of Constraint Programming (PPCP 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 874))

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].

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. 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.

    Google Scholar 

  2. Bledsoe, W.W.: A new method for proving certain Presburger formulas. Proc. of the 4th Joint Conf. on Artificial Intelligence. (1975) 15–21.

    Google Scholar 

  3. 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.

    Google Scholar 

  4. 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.

    Google Scholar 

  5. Harvey, W.: Personal communication. (1994).

    Google Scholar 

  6. Van Hentenryck, P., Deville, Y., Teng, C.: A generic arc-consistency algorithm and its specializations. Artificial Intelligence. 57 (1992) 291–321.

    Google Scholar 

  7. Van Hentenryck, P., Saraswat, V., Deville.Y.: Constraint Processing in cc(FD). Manuscript (1991).

    Google Scholar 

  8. 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.

    Google Scholar 

  9. 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.

    Google Scholar 

  10. Kapur, D., Nie, X.: Reasoning about Numbers in Tecton. Eighth Intl. Symp. on methodologies for intelligent systems. To appear (1994).

    Google Scholar 

  11. Lagarias, J.C.: The Computational Complexity of Simultaneous Diophantine Approximation Problems. SIAM J. of Computing. 14(1) (1985) 196–209.

    Google Scholar 

  12. Lassez, J-L., Maher, M.J.: On Fourier's Algorithm for Linear Arithmetic Constraints. J. of Automated Reasoning. 9 (1992) 373–379.

    Google Scholar 

  13. Le Pape, C.: Des Systèmes d'Ordonnancement Flexibles et Opportunistes. Thesis. Université de Paris-Sud. 1988.

    Google Scholar 

  14. Mackworth, A.K.: Constraint Satisfaction. Wiley. New York. 1987.

    Google Scholar 

  15. Pugh, W.: The Omega test: A Fast and Practical Integer Programming Algorithm for Dependence Analysis. Comm. ACM. 8 (1992) 102–114.

    Google Scholar 

  16. Pugh, W., Wonnacott, D.: Experiences with Constraint-based Array Dependence Analysis. Proc. Principles and Practice of Constraint Programming. PCP'94. 1994.

    Google Scholar 

  17. Pratt, V.R.: Two easy theories whose combination is hard. Tech. Report. Massachusetts Institute of Technology. Cambridge. Mass. 1977.

    Google Scholar 

  18. Revesz, P.Z.: A Closed Form for Datalog Queries with Integer Order. Proc. Intl. Conf. on Database Theory. 1990.

    Google Scholar 

  19. Rosenkrantz, D.J., Hunt, H.B. III.: Processing Conjunctive Predicates and Queries. Proc. Conf. on Very Large Data Bases. (1980) 64–72.

    Google Scholar 

  20. Shostak, R.: Deciding Linear Inequalities by Computing Loop Residues. J. of the ACM. 28(4) (1981) 769–779.

    Google Scholar 

  21. Shostak, R.: On the SUP-INF Method for Proving Presburger Formulas. J. of the ACM. 24(4) (1977) 529–543.

    Google Scholar 

  22. Toman, D., Chomicki, J., Rogers, D.S.: Datalog with Periodicity Constraints. Proc. Intl. Logic Programming Symp. To appear (1994).

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Alan Borning

Rights and permissions

Reprints 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

Publish with us

Policies and ethics