×

zbMATH — the first resource for mathematics

From local to global consistency in temporal constraint networks. (English) Zbl 0902.68016
Summary: We study the problem of global consistency for several classes of quantitative temporal constraints which include inequalities, inequations and disjunctions of inequations. In all cases that we consider we identify the level of local consistency that is necessary and sufficient for achieving global consistency and present an algorithm which achieves this level. As a byproduct of our analysis, we also develop an interesting minimal network algorithm.

MSC:
68M99 Computer system organization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Cooper, M.C., An optimal k-consistency algorithm, Artif. intell., 41, 89-95, (1990) · Zbl 0678.68058
[2] Dechter, R., From local to global consistency, Artif. intell., 55, 87-107, (1992) · Zbl 0762.68053
[3] Dechter, R.; Meiri, I.; Pearl, J., Temporal constraint networks, Artif. intell., 49, 61-95, (1991), (special volume on Knowledge Representation) · Zbl 0737.68070
[4] Dechter, R.; Pearl, J., Network-based heuristics for constraint satisfaction problems, Artif. intell., 34, 1-38, (1988) · Zbl 0643.68156
[5] Freuder, E., Synthesizing constraint expressions, Comm. ACM, 21, 958-966, (1978) · Zbl 0386.68065
[6] Freuder, E., A sufficient condition for backtrack-free search, J. ACM, 29, 24-32, (1982) · Zbl 0477.68063
[7] Gerevini, A.; Cristani, M., Reasoning with inequations in temporal constraint networks, ()
[8] a shorter version appears in the Proc. Workshop on Spatial and Temporal Reasoning, IJCAI-95.
[9] Gerevini, A.; Schubert, L., Efficient temporal reasoning through timegraphs, (), 648-654
[10] Gerevini, A.; Schubert, L.; Schaeffer, S., Temporal reasoning in timegraph I-II, SIGART bull., 4, 21-25, (1993)
[11] Imbert, J.-L., Variable elimination for generalized linear constraints, ()
[12] Imbert, J.-L., Redundancy, variable elimination and linear disequations, (), 139-153
[13] Imbert, J.-L.; van Hentenryck, P., On the handling of disequations in CLP over linear rational arithmetic, (), 49-71
[14] Isli, A., Constraint-based temporal reasoning: a tractable point algebra combining qualitative, metric and holed constraints, ()
[15] Koubarakis, M., Dense time and temporal constraints with ≠, (), 24-35
[16] Koubarakis, M., Complexity results for first-order theories of temporal constraints, (), 379-390
[17] Koubarakis, M., Foundations of indefinite constraint databases, (), 266-280
[18] Koubarakis, M., Foundations of temporal constraint databases, (), Available electronic-mail from Computer Science Division, Dept. Electrical and Computer Engineering, National Technical University of Athens · Zbl 0989.68134
[19] Lassez, J.-L.; McAloon, K., A canonical form for generalized linear constraints, () · Zbl 0745.90046
[20] Meiri, I., Combining qualitative and quantitative constraints in temporal reasoning, ()
[21] Meiri, I., Combining qualitative and quantitative constraints in temporal reasoning, (), 260-267
[22] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inform. sci., 7, 95-132, (1974) · Zbl 0284.68074
[23] ()
[24] van Beek, P., Exact and approximate reasoning about qualitative temporal relations, ()
[25] van Beek, P., Reasoning about qualitative temporal information, (), 728-734
[26] van Beek, P., Temporal query processing with indefinite information, Artif. intell. med., 3, 325-339, (1991)
[27] van Beek, P., Reasoning about qualitative temporal information, Artif. intell., 58, 297-326, (1992) · Zbl 0782.68106
[28] van Beek, P.; Cohen, R., Exact and approximate reasoning about temporal relations, Comput. intell., 6, 132-144, (1990)
[29] Vilain, M.; Kautz, H., Constraint propagation algorithms for temporal reasoning, (), 377-382
[30] Vilain, M.; Kautz, H.; van Beek, P., Constraint propagation algorithms for temporal reasoning: a revised report, (), 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.