On the consistency problem for the INDU calculus

Philippe Balbiani (1, 2) , Jean-François Condotta (3) , Gérard Ligozat (4)

1 IRIT-LILaC - Logique, Interaction, Langue et Calcul
2 CNRS - Centre National de la Recherche Scientifique
3 CRIL - Centre de Recherche en Informatique de Lens
4 LIMSI - Laboratoire d'Informatique pour la Mécanique et les Sciences de l'Ingénieur

In this paper, we further investigate the consistency problem for the qualitative temporal calculus introduced by Pujari et al. [A.K. Pujari, G.V. Kumari, A. Sattar, INDU: An interval and duration network, in: Australian Joint Conference on Artificial Intelligence, 1999, pp. 291–303]. We prove the intractability of the consistency problem for the subset of pre-convex relations, and the tractability of strongly pre-convex relations. Furthermore, we also define another interesting set of relations for which the consistency problem can be decided by the , a method similar to the usual path-consistency method. Finally, we prove that the is also complete for the set of atomic relations of implying that the intervals have the same duration.

Keywords: Qualitative temporal reasoning; Interval algebra; Qualitative constraint networks; Tractability

Domains: Computer Science [cs]; Artificial Intelligence [cs.AI]

Philippe Balbiani, Jean-François Condotta, Gérard Ligozat. On the consistency problem for the INDU calculus. Journal of Applied Logic, 2006, Special issue: TIME-ICTL 2003, 4 (2), pp.119-140. ⟨10.1016/j.jal.2005.06.002⟩. ⟨hal-03300285⟩