The Consistent Labeling Problem in Temporal Reasoning

Temporal reasoning can be perfn-med by maintaining a temporal relation n&work, a complete network in which the nodes are time intervals and each arc is the temporal relation between the two intervals which it connects. In this paper, we point out that the task of detecting inconsistency of the network and mapping the intervals onto a date line is a Consistent Labeling problem (CLPJ. The problem is formalized and analyzed. The signijicance of identifying and analyzing the CLP in temporal reasoning is that CLPs have certain features which allow us to apply certain techniques to our problem. We also point out that the CLP exists when we reason with disjunctive temporal relations. Therefore, the intractability of the constraint propagation mechunism in tempo& reasoning is inherent in the problem, not caused by the represent&n that we choose for time, as [Vi&n $ Kautz 861 claims.

Authors

• Edward P. K. Tsang

Keywords

No keywords are indexed for this paper.