Tractable disjunctions of linear constraints: Basic results and applications to temporal reasoning. (English) Zbl 0989.68134
We study the problems of deciding consistency and performing variable elimination for disjunctions of linear inequalities and disequations with at most one inequality per disjunction. This new class of constraints extends the class of generalized linear constraints originally studied by Lassez and McAloon. We show that deciding consistency of a set of constraints in this class can be done in polynomial time. We also present a variable elimination algorithm which is similar to Fourier’s algorithm for linear inequalities. Finally, we use these results to provide new temporal reasoning algorithms for the Ord-Horn subclass of Allen’s interval formalism. We also show that there is no low level of local consistency that can guarantee global consistency for the Ord-Horn subclass. This property distinguishes the Ord-Horn subclass from the pointizable subclass (for which strong 5-consistency is sufficient to guarantee global consistency), and the continuous endpoint subclass (for which strong 3-consistency is sufficient to guarantee global consistency).
MSC:
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 68T37 | Reasoning under uncertainty in the context of artificial intelligence |
Keywords:
linear constraints; variable elimination; interval algebra; ORD-Horn constraints; global consistencyReferences:
| [1] | Allen, J. F., Maintaining knowledge about temporal intervals, Comm. ACM, 26, 11, 832-843 (1983) · Zbl 0519.68079 |
| [2] | H. Beringer, B. de Backer, Satisfiability of Boolean formulas over linear constraints, in: Proc. IJCAI-93, Morgan Kaufmann, Los Altos, CA, 1993, pp. 296-301.; H. Beringer, B. de Backer, Satisfiability of Boolean formulas over linear constraints, in: Proc. IJCAI-93, Morgan Kaufmann, Los Altos, CA, 1993, pp. 296-301. |
| [3] | Cooper, M. C., An optimal \(k\)-consistency algorithm, Artificial Intelligence, 41, 1, 89-95 (1990) · Zbl 0678.68058 |
| [4] | Dechter, R., From local to global consistency, Artificial Intelligence, 55, 87-107 (1992) · Zbl 0762.68053 |
| [5] | Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artificial Intelligence (Special Volume on Knowledge Representation), 49, 1-3, 61-95 (1991) · Zbl 0737.68070 |
| [6] | Freuder, E., Synthesizing constraint expressions, Comm. ACM, 21, 11, 958-966 (1978) · Zbl 0386.68065 |
| [7] | Freuder, E., A sufficient condition for backtrack-free search, J. ACM, 29, 1, 24-32 (1982) · Zbl 0477.68063 |
| [8] | Grunbaum, B., Convex Polytopes (1967), Wiley: Wiley New York · Zbl 0163.16603 |
| [9] | Imbert, J.-L., Variable elimination for disequations in generalized linear constraint systems, Comput. J. (Special Issue on Variable Elimination), 36, 5, 473-484 (1993) · Zbl 0797.68142 |
| [10] | J.-L. Imbert, Variable elimination for generalized linear constraints: particular problems involving disequalities, Proc. 10th Internat. Conf. on Logic Programming, MIT Press, Cambridge, MA, 1993, pp. 499-516.; J.-L. Imbert, Variable elimination for generalized linear constraints: particular problems involving disequalities, Proc. 10th Internat. Conf. on Logic Programming, MIT Press, Cambridge, MA, 1993, pp. 499-516. |
| [11] | J.-L. Imbert, Redundancy, variable elimination and linear disequations, Proc. Internat. Symp. on Logic Programming, 1994 pp. 139-153.; J.-L. Imbert, Redundancy, variable elimination and linear disequations, Proc. Internat. Symp. on Logic Programming, 1994 pp. 139-153. |
| [12] | Imbert, J.-L.; van Hentenryck, P., On the handling of disequations in CLP over linear rational arithmetic, (Benhamou, F.; Colmerauer, A., Constraint Logic Programming: Selected Research, Logic Programming Series (1993), MIT Press: MIT Press Cambridge, MA), 49-71 |
| [13] | Jaffar, J.; Maher, M. J., Constraint logic programminga survey, J. Logic Programming, 19, 20, 503-581 (1994) |
| [14] | P. Jonsson, C. Bäckström, A linear programming approach to temporal reasoning, Proc. AAAI-96, AAAI Press/MIT Press, Cambridge, MA, 1996, pp. 1235-1240.; P. Jonsson, C. Bäckström, A linear programming approach to temporal reasoning, Proc. AAAI-96, AAAI Press/MIT Press, Cambridge, MA, 1996, pp. 1235-1240. |
| [15] | Jonsson, P.; Bäckström, C., A unifying approach to temporal constraint reasoning, Artificial Intelligence, 102, 143-155 (1998) · Zbl 0912.68160 |
| [16] | Kanellakis, P. C.; Kuper, G. M.; Revesz, P. Z., Constraint query languages, J. Comput. System Sci., 51, 26-52 (1995) |
| [17] | Khachiyan, L. G., A polynomial algorithm in linear programming, Sov. Math. Dokl., 20, 191-194 (1979) · Zbl 0414.90086 |
| [18] | M. Koubarakis, Dense time and temporal constraints with ≠, in: Principles of Knowledge Representation and Reasoning: Proc. 3rd Internat. Conf., KR’92, Morgan Kaufmann, San Mateo, CA, October 1992, pp. 24-35.; M. Koubarakis, Dense time and temporal constraints with ≠, in: Principles of Knowledge Representation and Reasoning: Proc. 3rd Internat. Conf., KR’92, Morgan Kaufmann, San Mateo, CA, October 1992, pp. 24-35. |
| [19] | M. Koubarakis, Complexity results for first-order theories of temporal constraints, in: Principles of Knowledge Representation and Reasoning: Proc. 4th Internat. Conf. (KR’94), Morgan Kaufmann, San Francisco, CA, May 1994, pp. 379-390.; M. Koubarakis, Complexity results for first-order theories of temporal constraints, in: Principles of Knowledge Representation and Reasoning: Proc. 4th Internat. Conf. (KR’94), Morgan Kaufmann, San Francisco, CA, May 1994, pp. 379-390. |
| [20] | Koubarakis, M., Database models for infinite and indefinite temporal information, Inform. Systems, 19, 2, 141-173 (1994) |
| [21] | Koubarakis, M., Foundations of indefinite constraint databases, (Borning, A., Proc. 2nd Internat. Workshop on the Principles and Practice of Constraint Programming (PPCP’94), Lecture Notes in Computer Science, vol. 874 (1994), Springer: Springer Berlin), 266-280 · Zbl 0802.00046 |
| [22] | M. Koubarakis, From local to global consistency in temporal constraint networks in: Proc. 1st Internat. Conf. on Principles and Practice of Constraint Programming (CP’95), Lecture Notes in Computer Science, vol. 976, Cassis, France, Springer, Berlin, September 1995, pp. 53-69.; M. Koubarakis, From local to global consistency in temporal constraint networks in: Proc. 1st Internat. Conf. on Principles and Practice of Constraint Programming (CP’95), Lecture Notes in Computer Science, vol. 976, Cassis, France, Springer, Berlin, September 1995, pp. 53-69. |
| [23] | M. Koubarakis, From local to global consistency in temporal constraint networks, Theoret. Comput. Sci. 173 (1997) 89-112. Invited submission to the special issue dedicated to the 1st Internat. Conf. on Principles and Practice of Constraint Programming (CP95), Editors: U. Montanari and F. Rossi.; M. Koubarakis, From local to global consistency in temporal constraint networks, Theoret. Comput. Sci. 173 (1997) 89-112. Invited submission to the special issue dedicated to the 1st Internat. Conf. on Principles and Practice of Constraint Programming (CP95), Editors: U. Montanari and F. Rossi. · Zbl 0902.68016 |
| [24] | M. Koubarakis, The complexity of query evaluation in indefinite temporal constraint databases, Theoret. Comput. Sci. 171 (1997) 25-60. Special Issue on Uncertainty in Databases and Deductive Systems, Editor: L.V.S. Lakshmanan.; M. Koubarakis, The complexity of query evaluation in indefinite temporal constraint databases, Theoret. Comput. Sci. 171 (1997) 25-60. Special Issue on Uncertainty in Databases and Deductive Systems, Editor: L.V.S. Lakshmanan. · Zbl 0887.68029 |
| [25] | Ladkin, P.; Maddux, R., On binary constraint problems, J. ACM, 41, 3, 435-469 (1994) · Zbl 0813.03045 |
| [26] | J.-L. Lassez, K. McAloon, A canonical form for generalized linear constraints, Technical Report RC15004 (#67009), IBM Research Division, T.J. Watson Research Center, 1989.; J.-L. Lassez, K. McAloon, A canonical form for generalized linear constraints, Technical Report RC15004 (#67009), IBM Research Division, T.J. Watson Research Center, 1989. · Zbl 0745.90046 |
| [27] | J.-L. Lassez, K. McAloon, A canonical form for generalized linear costraints, in: TAPSOFT ’89, Advanced Seminar on Foundations of Innovative Software Development, Lecture Notes in Computer Science, vol. 351, Springer, Berlin, 1989, pp. 19-27.; J.-L. Lassez, K. McAloon, A canonical form for generalized linear costraints, in: TAPSOFT ’89, Advanced Seminar on Foundations of Innovative Software Development, Lecture Notes in Computer Science, vol. 351, Springer, Berlin, 1989, pp. 19-27. |
| [28] | Lassez, J.-L.; McAloon, K., A canonical form for generalized linear constraints, J. Symbolic Comput., 13, 1, 1-24 (1992) · Zbl 0745.90046 |
| [29] | Nebel, B.; Bürckert, H.-J., Reasoning about temporal relations: a maximal tractable subclass of Allen’s interval algebra, J. ACM, 42, 1, 43-66 (1995) · Zbl 0886.68077 |
| [30] | B. Nebel, H.-J. Bürckert, C programs used for the analysis of the ORD-Horn class, available electronically from ftp://ftp. informatik.uni-freiburg.de/ ̃nebel/journals.html.; B. Nebel, H.-J. Bürckert, C programs used for the analysis of the ORD-Horn class, available electronically from ftp://ftp. informatik.uni-freiburg.de/ ̃nebel/journals.html. |
| [31] | (Schrijver, A., Theory of Integer and Linear Programming (1986), Wiley: Wiley New York) · Zbl 0665.90063 |
| [32] | S. Skiadopoulos, Tractable query answering in indefinite linear constraint databases, Master’s Thesis, Department of Computation, UMIST, 1998.; S. Skiadopoulos, Tractable query answering in indefinite linear constraint databases, Master’s Thesis, Department of Computation, UMIST, 1998. |
| [33] | Sontag, E., Real addition and the polynomial time hierarchy, Inform. Process. Lett., 20, 115-120 (1985) · Zbl 0575.03030 |
| [34] | van Beek, P., Reasoning about qualitative temporal information, Artificial Intelligence, 58, 297-326 (1992) · Zbl 0782.68106 |
| [35] | van Beek, P.; Cohen, R., Exact and approximate reasoning about temporal relations, Comput. Intelligence, 6, 132-144 (1990) |
| [36] | Vilain, M.; Kautz, H.; van Beek, P., Constraint propagation algorithms for temporal reasoning: a revised report, (Weld, D. S.; de Kleer, J., Readings in Qualitative Reasoning about Physical Systems (1989), Morgan Kaufmann: Morgan Kaufmann Los Altos, CA), 373-381 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
