In this paper, we consider quantitative temporal or spatial constraint networks whose constraints evolve over time in an ultimately periodic fashion. These constraint networks are an extension of STPs (simple temporal problems). We study some properties of these new types of constraint networks. We also propose a constraint propagation algorithm. We show that this algorithm decides the consistency problem in some particular cases

Temporal and spatial reasoning is a central task for numerous applications in many areas of artificial intelligence. For this task, numerous formalisms using the qualitative approach have been proposed. Clearly, these formalisms share a common algebraic structure. In this paper we propose and study a general definition of such formalisms by considering calculi based on basic relations of an arbitrary arity. We also describe the QAT (the qualitative algebra toolkit), a JAVA constraint programming library allowing to handle constraint networks based on those qualitative calculi

We consider qualitative temporal or spatial constraint networks whose constraints evolve over time in an ultimately periodic fashion: after an initial stretch of time, a fixed pattern of constraints (over an interval) is reproduced indefinitely. We propose a local propagation algorithm which is polynomial, and we show that it decides the consistency problem in some particular cases. We also show that the general problem of consistency for such networks is in PSPACE

In this paper, we further investigate the consistency problem for the qualitative temporal calculus INDU introduced by A. K. Pujari et al. (1999). We prove the intractability of the consistency problem for the subset of preconvex relations. On the other hand, we show the tractability of strongly preconvex relations. Furthermore, we also define another interesting set of relations for which the consistency problem can be decided by a method similar to the usual path-consistency method.

A typical instance of a qualitative temporal reasoning calculus is Allen's temporal interval calculus. When using the calculus, a central problem is the problem of consistency: giv en a binary constraint network, which expresses qualitative constraints between a finite set of intervals in terms of disjunctions of the 13 possible basic relations, determine whether there exists an instantiation of the network in terms of intervals in the time line. The problem is NP-complete, and extensive work has been devoted to characterizing tractable subclasses of disjunctive relations resulting in a description of all the tractable subclasses. From a theoretical point of view, Allen's calculus has many good properties: the underlying constraint algebra is a relation algebra in Tarski's sense; testing path-consistency is a complete method for testing consistency for well-determined subclasses of relations; scenarios, i.e. atomic path-consistent networks are consistent and determine unique qualitative configurations; the first order theory associated to the calculus is aleph-zero categorical; tractable subclasses can be characterized either syntactically (ORD-Horn relations) or topologically (pre-convex relations). Many qualitative spatial and temporal calculi have been developed in the past years along lines which are prima facie quite similar to those at work in Allen's calculus. However, it is apparent that many of the properties mentioned above no longer hold. In this talk, we describe some of the main points where specific calculi differ from Allen's calculus, and discuss the new questions that arise. In the discussion, we make use of algebraic and topological concepts, such as weak representations and conceptual spaces. We describe some first results of the approach.