Theoretical and Experimental Studies of Temporal Constraint Satisfaction Problem

Debasis Mitra

Reasoning with time is embedded in many application domains than we are often aware of. For example, understanding a parallel program involves how each unit of the program is temporally related to the other unit through dependency. There is a growing awareness about the importance of understanding time in any dynamic or evolving situation. Within last twenty years different dimensions of reasoning have been identified, such as, qualitative reasoning versus quantitative reasoning, point-based representation versus interval-based representation, propositional expression versus first order expression. My work concentrates on interval-based qualitative propositional reasoning. The representation scheme and a polynomial approximate algorithm were proposed by James Allen. The problem of detecting global consistency has been subsequently proved to be NP-complete. Practical reasoning systems have been developed based on Allen’s S-consistency algorithm. This algorithm checks for consistency over constraints between each subset of 3 temporal entities of the full set of temporal assertions in the system (rather than checking for complete consistency between all constraints, which is called global-consistency). There has been very little systematic study on either the S-consistency problem, or the global-consistency problem.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.