Ultimately periodic qualitative constraint networks for spatial and temporal reasoning

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