Skip to Main content Skip to Navigation
Conference papers

Minimal Consistency Problem of Temporal Qualitative Constraint Networks

Jean-François Condotta 1 Souhila Kaci 2
2 GRAPHIK - Graphs for Inferences on Knowledge
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier, CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : Various formalisms for representing and reasoning about temporal information with qualitative constraints have been studied in the past three decades. The most known are definitely the Point Algebra (PA) and the Interval Algebra (IA) proposed by Allen. In this paper, for both calculi, we study a particular problem that we call minimal consistency problem (MinCons). Given a temporal qualitative constraint network (TQCN) and a positive integer k, this problem consists in deciding whether or not this TQCN admits a solution using at most k distinct points on the line. On the one hand, we prove that this problem is NP-complete for both PA and IA, in the general case. On the other hand, we show that for TQCNs defined on the convex relations, MinCons is polynomial. For these TQCNs, we give a polynomial method allowing to obtain compact scenarios.
Document type :
Conference papers
Complete list of metadata
Contributor : Fabien Delorme Connect in order to contact the contributor
Submitted on : Tuesday, July 27, 2021 - 9:26:11 AM
Last modification on : Thursday, September 9, 2021 - 3:10:29 PM



Jean-François Condotta, Souhila Kaci. Minimal Consistency Problem of Temporal Qualitative Constraint Networks. 20th International Symposium on Temporal Representation an Reasoning (TIME 2013), Sep 2013, Pensacola, FL, United States. pp.11-18, ⟨10.1109/TIME.2013.11⟩. ⟨hal-03300299⟩



Record views