Transition Constraints: A Study on the Computational Complexity of Qualitative Change

1 Introduction

Suppose you are watching a movie. On the screen, a woman is sitting at her desk talking to a man on the other side. The camera moves from the woman to the man and back to the woman. You detect that something is wrong with the displayed conversation. When you watch the movie again, you discover the following: in the scene the coffee mug is initially to the left of the woman, but when the camera moves back, the coffee mug is suddenly to her right. How can that be?

Qualitative Spatial and Temporal Reasoning (QSTR) is the research field studying representations of space and time that abstract from numeric quantities. The representation formalisms considered in QSTR are typically based on some finite vocabulary that allow for expressing spatial or temporal relationships and concepts, such as "to the left of", "to the north of", "contained in", etc. These terms can be given a precise meaning, e.g., by using a first-order logic (FOL) semantics that provides an interpretation of these terms on the domain of interest. In this setting a number of reasoning tasks are relevant. For example, one can ask whether some given qualitative information is consistent or what knowledge is entailed by it. At the heart of these questions is the satisfiability problem: given a qualitative description of spatial relations between objects, is there a model of the description? In some cases this problem is undecidable (e.g., [Kontchakov et al., 2011]), but in many cases it is decidable and even tractable.

In this work, we tackle the satisfiability problem of pointbased qualitative spatial formalisms in combination with constraints on the transition between static scene descriptions. More precisely, we discuss the reasoning task of finding a solution to a temporal sequence of static reasoning problems where this sequence is subject to additional transition constraints, such as continuity constraints.

The general setup of our work touches on many previous research efforts in QSTR. One line of research considers the conceptual proximity of relations expressed in socalled neighborhood graphs [Freksa, 1991] and their various extensions (e.g., [Galton, 2001]). Another research direction is to use these results in practice to empower artificial agents [Dylla and Wallgr¨un, 2007; Wolter et al., 2007], track moving objects [Bennett et al., 2008], or to determine distances between qualitative information in the context of belief merging [D'Almeida et al., 2012]. Further applications deal with qualitative models of physical events [Apt and Brand, 2006] or robot motion planning [Westphal et al., 2011].

However, for many of these applications the usual neighborhood graphs are not sufficient, thus leading to symbolic formalisms without proper semantics. We combine these lines of research by providing a unified foundation for relational spatio-temporal reasoning that can easily be used in applications. We give a precise definition of transition relations that capture continuous qualitative change. These relations can be considered as implicit global constraints between static spatial descriptions or in a more general setting as additional relations in the vocabulary that give the ability to explicitly pose transition constraints. The contribution of this work is that both problems are shown to be NP-complete even when one considers only small, yet interesting fragments of point-based qualitative formalisms.

Although related problem settings of spatio-temporal formalisms have been analyzed in the literature before, the authors are not aware of a relational approach to this problem or work that analyzes the computational complexity of fragments of such formalisms.

Related work. A link to other works is the principal idea of qualitative states and transitions [Galton, 2005]. A qualitative state is a description of the world at a specific time in a fixed qualitative vocabulary. Transitions govern the connection between states and among them continuous transitions, which describe smooth movements of objects, are of interest to us. Moreover, transitions could be further restricted, e.g., if an application requires some objects to be static.

All of the previously cited works base transitions on Conceptual Neighborhood Graphs (CNG) [Freksa, 1991]. These graphs have as nodes the qualitative vocabulary and an edge between two terms whenever they are considered conceptually close. However, this is inadequate for many forms of continuous motion as neighborhood graphs only consider the change of one term at a time independent of other simultaneous changes. As a result, extensions have been suggested such as the concept of dominance spaces [Galton, 2001] resulting in directed CNGs, and generalized CNGs [Ragni and W¨olfl, 2005]. Galton characterized continuity via dominance spaces, but did not suggest a relational definition in terms of the static vocabulary. Ragni and W¨olfl studied relational consistency of sequences of states for fixed numbers of static and moveable objects. Later, Ragni and W¨olfl suggested a constraint formalism [Ragni and W¨olfl, 2006] for Cardinal Directions that uses a directed CNG derived for solid objects from continuity assumptions. We here propose a novel relational approach to continuous transitions in order to unify these concepts. Our work reflects dominance spaces, but makes transition constraints explicit in a relational language.

Although many works follow the idea of qualitative states and transitions, they often differ in the proposed formalism, e.g., Gerevini and Nebel (2002) propose a new constraint formalism combining an interval-based representation of time with the spatial RCC8 formalism, Apt and Brand (2006) suggest the use of constraint programming to extend the usual qualitative constraint reasoning with common CNGs, and Bennett et al. (2002) propose embeddings into modal logics. This makes contributing hard without assuming a particular formalism. We position this work on common ground, that is, on continuous transitions combined with the qualitative vocabulary which could be used directly in applications with, e.g., the constraint programming approach of Apt and Brand.

Finally, the idea of establishing the computational complexity of spatio-temporal formalisms has been considered before, e.g., by Bennett et al. (2002). The authors proposed different combinations of the qualitative formalism RCC with temporal logics using modal logics and classified them according to their expressiveness and computational complexity. Gerevini and Nebel (2002) also provided complexity results for their formalism. Our work differs from these in both the considered formalism and further in the approach of analyzing fragments.

2 Theoretical Background

The qualitative formalisms we consider are usually defined in terms of relation algebras on binary relations [Renz and Nebel, 2007]. However, they can be naturally expressed in relational languages in FOL, which are more flexible, in particular, as they are not limited to binary relations. Such relational languages can be used for expressing and analyzing constraints and are thus often referred to as constraint languages in this context. Not only are these languages a wellstudied concept in the theory of constraint satisfaction, but they have also been successfully applied to qualitative reasoning [Bodirsky and Chen, 2009]. We here use the flexibility of constraint languages to express and analyze transition constraints. In the following we provide a formal introduction to constraint languages and widely adopt the notation by Bodirsky and Chen.

2.1 Constraint languages

Assume a finite signature τ = {R1, . . . , Rm} of distinct relation symbols Ri, each with a finite arity ki. A constraint language Γ is a relational structure over the signature τ defined on some non-empty domain D that assigns an interpretation to each relation symbol Ri, i.e., RΓ i is a ki-ary relation on D. In this work the interpretation of the signature is clear from the context and we simply write Γ = 〈D;R1, . . . ,Rm〉 to specify τ and Γ. A primitive positive τ-formula is any FOL formula of the form ϕ = ∃v1 . . . vn ∧lj=1 ψj , where each ψj has the form Rivj1 . . . vjki (with Ri some ki-ary relation in τ) or the form vj1 = vj2 . An instance of CSP(Γ) is a primitive positive τ -formula without free variables.

Note that each instance ϕ = ∃v1 . . . vn ∧lj=1 ψj of CSP(Γ) may be conceived of as a constraint network over the variables {v1, . . . , vn} with domain D, and each of the conjuncts ψj = Rivj1 . . . vjki as a constraint with scope {vj1 , . . . , vjki }. To shorten notation we often only write the set of constraints {ψ1, . . . , ψl} to specify ϕ.

A central notion in the theory of constraint languages is expressibility of relations. A relation R ⊆ Dk is said to be expressible in Γ if there exists a primitive positive τformula ϕ with free variables {v1, . . . , vk} such that R = {(a1, . . . , ak) ∈ Dk : Γ, a1, . . . , ak |= ϕ}.

We briefly define some standard concepts of constraint satisfaction problems. A partial solution α of an instance ϕ = ∃v1 . . . vn ∧j ψj of CSP(Γ) is a map α: V ′ → D with V ′ ⊆ {v1, . . . , vn} such that Γ, α |= ψj for each conjunct ψj = Rivj1 . . . vjki in ϕ with {vj1 , . . . , vjki } ⊆ V ′ . The size of α is |V ′ |. A partial solution α of size n is called a solution of ϕ. Furthermore, ϕ is said to be k-consistent if each partial solution of size k - 1 can be extended to any other variable such that it is a partial solution of size k. Instance ϕ is strongly k-consistent if it is l-consistent for each 1 ≤ l ≤ k.

Finally, CSP(Γ) denotes the problem of deciding the satisfiability of an arbitrary instance of CSP(Γ).

Example 1. The Point Algebra can be seen as the constraint language ΓPA = 〈Q; ∅,<,≤, ̸=〉 of binary relation symbols with the natural interpretation of the relation symbols over Q [Bodirsky and Chen, 2009]. CSP(ΓPA) is well-known to be tractable [van Beek and Cohen, 1990; Bodirsky and Chen, 2009]. Any strongly 3-consistent Point Algebra instance that does not contain the empty relation is satisfiable. Strong 3consistency can be established in polynomial time, e.g., by intersection and composition of binary relations. Observe that the relations ̸=, ≤ are unions (disjunctions) of other relations, they thus express imprecise information. Notice, that for the purposes of the paper there is no difference in interpreting the Point Algebra on the real numbers (even in the context of continuity considerations).

Although the Point Algebra is rather simple, it forms the basis of several important formalisms. Examples include Cardinal Directions [Frank, 1991] (with signature north, northeast, east, . . . ), Allen's Interval Algebra [Allen, 1983] (spatially interpreted in-front-of , overlaps, part-of , . . . ), and its multidimensional variants, e.g., the Rectangle Algebra [Guesgen, 1989; Mukerjee and Joe, 1990]. These formalisms can be built from Point Algebra relations, e.g., [Allen, 1983; Bodirsky and Chen, 2009], and moreover the Point Algebra is easily expressed by fragments of them. Unlike the Point Algebra these formalisms are in the general case intractable, but have large subsets of their signatures, for which the satisfiability problem is tractable.

We do not define Conceptual Neighborhood Graphs, but give the usual graph for the Point Algebra in Figure 1. Note that the graph only describes conceptual proximity between non-disjunctive binary relation symbols. Thus, when applying such graphs to constraint networks one has different options to extend them to multiple variables and disjunctive relations.

2.2 Reference NP-complete problems

We use the following NP-complete problems in this work.

The betweenness problem [Garey and Johnson, 1979] is here used in its constraint language form [Bodirsky and K´ara, 2010]. The betweenness relation Rbetw ⊆ Q3 is Rbetwxyz := (x < y < z)∨(x > y > z). The associated decision problem CSP(〈Q;Rbetw〉) is NP-complete. Thus, any constraint language Γ over Q in which Rbetw is expressible has an NP-hard decision problem CSP(Γ).

The Monotone 1-in-3 SAT problem [Schaefer, 1978] is the NP-complete decision problem whether there exists a satisfying assignment of a propositional SAT formula with 3 positive literals per clause in which no more than one literal is true per clause.

3 Change, Transitions, and Continuity

In a general setting, we would like to describe and reason with change of objects. As objects in our formalisms are represented by variables, change occurs on their values. In particular, a certain change might relate multiple variables and their values in multiple states. Possible change is however dependent on several factors, most noticeably the type of objects, their ability or inability to change in specific ways, and their interactions. It is perhaps impossible to devise a fine-grained theory of adequate changes without being more specific on the intended application setting. For this reason we state a general class of problems that can be used in combination with different types of transitions to capture the needs of specific applications. After this general statement, we consider the very basic type of change that should hold in virtually all cases: continuity of change. Here, we derive a relational representation of continuous change for the Point Algebra.

A recurring theme in applications of qualitative reasoning with change is the use of sequences of static qualitative snapshots that form an extended temporal problem. We begin with a basic definition of such instances based on constraint languages.

Definition 1. Let Γ be a constraint language on domain D. An instance of SeqCSP(Γ) is a tuple S = 〈V, (Q1 , . . . , Qd )〉, where V is a finite set of variables and Q1 , . . . ,Qd are instances of CSP(Γ) over subsets of V . We refer to a Qt (1 ≤ t ≤ d) as a state and write vt (or even V t ) to refer to the variable v (or V ) occurring in the state Qt . A base solution of S is a sequence α = α1 , . . . , αd where each αt is a solution of Qt .

We here mostly restrict ourselves to sequences as it is the simplest type. In general, one could clearly be less restrictive and allow for tree- or general graph-structures.

3.1 Transitions

So far, we only express sequences of qualitative states without giving conditions for transitions or even explicit cases of possible transitions. The latter would be akin to operators in planning formalisms, but without restricting ourselves to a particular application there is little to be written about specific operators. Thus, we consider the first option, that is, restricting possible transitions by formulating properties that must hold for all transitions. These properties can always be used as background knowledge for specific transitions.

Certainly, a fundamental and relevant requirement is that of continuous change. Informally, the transition between two states is continuous if it is possible to transition from one state to the other without any intermediary distinct third state.

In what follows we turn our attention to the Point Algebra and discuss continuous transitions.

3.2 The Point Algebra with continuity

We focus on the Point Algebra to make the concept of continuous transitions, in particular their realizations, explicit. As mentioned before the Point Algebra is important as these transitions naturally extend to the mentioned point-based formalisms (also see Galton's product theorems [Galton, 2001]).

The idea we follow is to converge to a concept of solution that shows a SeqCSP(ΓPA) instance meeting certain "continuity constraints" to have a realization. In other words, for each such solution we have continuous trajectories of the objects which are described by this sequence without any gap.

Definition 2. Let S be an instance of SeqCSP(ΓPA).

1) A base solution α of S is a T2-solution if it satisfies the following T2-condition: for all pairs of variables 1 ≤ i, j ≤ n and time points 1 ≤ t < d it holds

2) A T2-solution α of S is a T4-solution if it satisfies the following T4-condition: for every four variables 1 ≤ i, j, k, l ≤ n and time point 1 ≤ t < d it holds

The usual neighborhood graph of the Point Algebra can be understood as continuous transitions of two objects, which is reflected by the T2-condition (1). The additional condition (2) required by T4-satisfiability reflects Galton's directed neighborhood graphs. It ensures that all transitions of two objects can occur simultaneously without introducing discontinuity. Here, whenever two objects transition from ̸= to =, no objects may split at the same time. This follows from the assumption of observing one limiting process with continuous functions. We illustrate these conditions in the following example.

Example 2. Consider the following instance of SeqCSP(ΓPA) over variables {x, y, z} and four states: {x1 < y1 < z1 , y2 < z2 , y3 < z3 , y4 < z4 < x4 }.

An illustration of a T2-solution is given in Figure 2. Here, x can neither skip over y in Q2 nor over z in Q3 due to the T2condition. However, the transition Q2 → Q3 with x2 = y2 to x3 > y3 and x2 < z2 to x3 = z3 does not satisfy the T4-condition. Thus, the instance is T2-satisfiable, but not T4satisfiable. The notion of continuity due to T4-satisfiability would require an intermediary state between Q2 and Q3 in which it holds y < x < z.

It is important to note that with [Galton, 2001] it follows that T4-solutions are realizable as they can be embedded in Galton's "TM spaces". For any T4-solution α1 , . . . , αd there is a family of continuous functions describing smooth motion of each object that successively traverses α1 , . . . , αd and in between αt , αt+1 always satisfies Qt or always satisfies Qt+1 . Further, it follows that many continuous motions can be described with SeqCSP(ΓPA) if they are not "infinitely intermingled" [Galton, 2001].

Finally, SeqCSP(ΓPA; T2) denotes the decision problem whether an arbitrary instance of SeqCSP(ΓPA) is T2satisfiable. Analogously, SeqCSP(ΓPA; T4) refers to T4satisfiability.

3.3 Constraint languages with transition relations

Any instance S of SeqCSP(ΓPA) can be written in polynomial time as an instance ϕ of CSP(ΓPA) with a specific form. This embedding explicitly introduces one variable vt to ϕ for each time point t and variable v in S. Thus, the constraints of each Qt can be posed on variables V t in ϕ. While we have so-far understood the T2-, and T4-conditions as additional implicit constraints on each transition, we can cast them as relations and make their application explicit as constraints.

The relation T4 ⊆ Q4 × Q4 is defined by

Clearly, instances of SeqCSP(ΓPA), SeqCSP(ΓPA; T2), and SeqCSP(ΓPA; T4) can now be represented as a formula in the constraint language ΓPA , 〈Q; ∅,<,≤, ̸=, T2〉 or 〈Q; ∅,<,≤, ̸=, T4〉, respectively, by posing the appropriate T2 or T4 relations on permutations of neighboring variables. The latter two constraint languages are, however, more expressive than sequential instances because relations can freely be posed as constraints on arbitrary variables. In particular, in these languages we can further restrict transitions. For this consider the following example.

Example 3. Given the variables V = {v1 , v2 ,w1 ,w2}, we set as constraints {v1 < w1 , v1 < v2 ,w1 = w2 , v1w1 T2 v2w2 }. This instance of CSP(〈Q;<, T2〉) states that there is a continuous motion of v,w through two states, in which v is initially placed left of w and gets closer to w in the second state, while w remains in the same position.

The relative move of v towards w while w remains at its position, as seen in this example, cannot be expressed as an instance of SeqCSP(ΓPA), it can only be expressed in the extended constraint language. Thus, the extended constraint languages can be used to express the intended sequential instances whose T2-, and T4-solutions can be enforced by T2-, T4-constraints, but also more specific transitions.

In general, the constraint language approach is expressive and may serve well for extending results to other related formalisms. Further, it could be interesting for future work to consider the briefly mentioned explicit transitions as transition relations in a constraint language, in particular, as constraint languages are a well-studied area.

The remainder of this work considers the computational complexity of these extended Point Algebra languages and the sequentially structured instances of SeqCSP(ΓPA).

4 Complexity of Constraint Languages with Transition Relations

In this section we study the computational complexity of all the constraint languages 〈Q; S, T2〉 and 〈Q; S, T4〉 for arbitrary subsets S of the Point Algebra's signature {∅, <, ≤, ̸=}. We show that, with the exception of trivial cases, all these languages are NP-complete.

Proof. All constraint languages with relations FOL-definable using < over Q have been classified and shown to be in NP [Bodirsky and K´ara, 2010].

Proposition 2. For S ⊆ {∅,≤}, both CSP(〈Q; S, T2〉) and CSP(〈Q; S, T4〉) are tractable.

Proof. Instances containing ∅ are unsatisfiable, otherwise a solution is to assign the same value to all variables.

We classify all the remaining cases as NP-complete in the following proposition.

Proposition 3. For any S ⊆ ΓPA that contains ̸= or <, both CSP(〈Q; S, T2〉) and CSP(〈Q; S, T4〉) are NP-complete.

Proof. NP-membership is due to Prop. 1. NP-hardness follows from the expressibility of Rbetw. Assume first, the case of T2 and ̸= ∈ S. Consider the following equivalence:

In case we have < ∈ S, we show ̸= is expressible which already gives us Rbetw as seen above. The identity

can be proven by a case distinction (x < y, x = y, and x > y). Note that the linear ordering is serial. Finally, we observe T4 suffices to express T2:

These results establish that any non-trivial subset of the signature already has an NP-complete satisfiability problem. Certainly, this gives us an upper bound on the complexity of SeqCSP(ΓPA) due to the embedding in these languages. In the next section we show stronger results for instances of SeqCSP(ΓPA) with both T2- and T4-satisfiability.

5 Complexity of Sequential CSPs

In the following we consider satisfiability problems of instances reflecting the idea of states and transitions. Certainly, our previous results already show that they are in NP and that the trivial polynomial cases apply here as well.

At first it seems likely that instances of SeqCSP(ΓPA; T2) in which every state is strongly 3-consistent and further every partial solution of size 2 of one state has a partial solution of size 2 in each neighboring state satisfying the T2-condition, are T2-satisfiable, but this is not the case (cp. Prop. 5).

Example 4. Consider the following instance over variables {x, y, z, u, v, w} and four states (which can be made strongly 3- and 2-consistent in the above sense): {x1 ≤ z1 ≤ u1 ≤ y1 , x1 < y1 , x2 < z2 , x2 ≤ y2 , u2 < y2 , y3 < v3 , y3 ≤ x3 ,w3 < x3 , y4 ≤ v4 ≤ w4 ≤ x4 , y4 < x4 }. In this example the first two states have no solution with x2 = y2 , because from x2 = y2 we obtain u2 < x2 = y2 < z2 and thus x1 = z1 = u1 = y1 - contradicting x1 < y1 . Similarly, the last two states have no solution for y3 = x3 . Thus, it holds x2 < y2 , x3 > y3 , and the example is not T2-satisfiable. As both flaws are not detected by the above mentioned local consistency, it is not refutation complete.

Indeed we show that the T2- and T4-satisfiability problem of sequential CSPs is NP-complete for the same fragments.

Theorem 1. For S ⊆ ΓPA with ̸= ∈ S, SeqCSP(〈Q; S〉 ; T2) and SeqCSP(〈Q; S〉 ; T4) are NP-complete.

Proof sketch. Via reduction from the betweenness problem. First, to express Rbetwxyz, consider three states with {x1 = y1 , y1 ̸= z1 , x2 ̸= y2 , y2 ̸= z2 , x2 ̸= z2 , x3 ̸= y3 , y3 = z3 }. Note that all T2- (and T4-) solutions of this instance 〈{x, y, z}, (Q1 ,Q2 ,Q3 )〉 either satisfy x2 < y2 < z2 or x2 > y2 > z2 as both pairs x, y and y, z must meet in Q1 and Q3 , respectively.

Given the form of sequential instances we have to argue about how to combine multiple copies of such a Rbetwconstruction. Let m be the number of betweenness-triples in the input. Consider the above construction on a sequence 〈{x, y, z}, (Q1 , Q2 , Q2 , . . . , Q2 , Q3 )〉 of 4·(3·m)2 +1 many states. Now, Rbetwxyz holds in all but the leftmost and rightmost state. To encode a complete betweenness problem, we add for each betweenness triple three fresh variables along with the above constraints into the same long sequence of states. In the middle state we force all variables representing the same input variable to match via equality constraints. For each triple we now have a betweenness constraint and there are enough states to untangle all triples such that each pair x, y, and each pair y, z can move to the same position in the leftmost and rightmost state, respectively.

Proof sketch. Via reduction fromMonotone 1-in-3-SAT. We can only provide a rough sketch due to lack of space.

For every atom ai in the SAT formula we introduce one variable pi. In the following we construct a sequence Q1 , . . . ,Qd with d linear in the number of clauses. First, we will set up some states to force a true/false decision for every atom, then we will check clause by clause whether this interpretation satisfies the problem.

For each Qk , k ≥ 2 we maintain three variables Lk < Ok < Rk such that for each pi it must hold pki ≤ Lk or Rk ≤ pki and that these relations do not change. We interpret pki ≤ Lk as ai is false and Rk ≤ pki as ai is true. The first state will be used for setup, and the rest for successively evaluating each clause, i.e., asserting that for every clause, no three atoms are on the left-hand side and no two atoms on the right-hand side. A crucial construction is the ̸=-like statement used, e.g., to force variables to the outside of the interval Lk < Rk . For this, consider for each pi a new variable ti, {p1i < t1i , L1 = O1 = R1}, and {p2i = t2i , L2 < O2 < R2 } under the T2-condition. If we had L2 < p2i = t2i < R2 then pi, ti would have to be equal in the first state as they cannot skip over L or R. Thus p2i , t2i must be outside Lk ,Rk . This is considered for arbitrarily many variables and we also use similar constructs later on. We must ensure the variables pi remain outside the L, R interval. This can be done by using a linear number of variables {cj} with c2j = O2 for all j, where in each succeeding state we move one cj from O to L and one from O to R, thus preventing any variable to move from L towards O and from R to O, respectively.

Now we need to evaluate each clause. Here, we only give the description of the (simpler) right-hand side. We denote by s the index of the first state of the series used to evaluate clause number s. The following is a double ̸=-like construction on variables p, q in the same clause using new variables l, ll, r, rr for each clause variable.

The first three states force the variables p, q to be separated by at least one other point, and the last state requires them to be smaller or equal to R. If they are both to the right of R the series is too short to achieve the latter constraint. We successively repeat this series, separated by a state without any forced ordering of p, q, for every pair of variables in each clause. Checking the left-hand side follows the same idea with more separating points.

Theorem 3. For S ⊆ ΓPA with < ∈ S, SeqCSP(〈Q; S〉 ; T2) is NP-complete.

Proof sketch. The reduction is essentially identical to Th. 2 except for replacing R with R1 < · · · < Rm (the point L is also replaced in the same way). This change is made in order to allow the test ps+3 ≤ R to be written as ps+4 < Rj (q analogously). The test is on step s+4 because it requires one more step to go through Rj .

With the T4-condition it remains possible to recreate ≤ from < and the ̸=-like construct from {≤, <}, which allows us to consider similar proofs.

Proof sketch. For the ̸=-like construct, consider: {x1 < t1 , l1 = y1 = r1 , x2 < t2 , l2 < y2 < r2 , x3 = t3 , l3 < y3 < r3 } which implies x3 ̸= y3 . The remainder of the reduction given for the T2-condition can be translated to the T4-condition with minor changes.

Given our NP-completeness results, a direct consequences is that fragments of other point-based formalisms are NPcomplete as well.

Corollary 1. SeqCSP(Γ; T2) and SeqCSP(Γ; T4) are NPcomplete for those fragments Γ of Allen's Interval Calculus, Cardinal Directions, or the Rectangle Algebra, that suffice to express < or ̸=.

So far, we have considered the computational complexity of fragments of languages and seen that all interesting cases are already NP-complete. We now turn our attention to some simple tractable cases that arise from structural restrictions.

Proposition 4. SeqCSP(ΓPA ; T2) and SeqCSP(ΓPA ; T4) are fixed-parameter tractable in the number of variables |V |.

Proof. Translate every Qt into the set of possible orderings of V that satisfy Qt . Next, connect orderings at neighboring time points if they satisfy the T2- (or T4-) condition. Finally, use graph search to find a path.

Further, we can observe that SeqCSP(ΓPA) coincides with SeqCSP(ΓPA; T2) (and SeqCSP(ΓPA; T4)) if the T2-condition (and T4-condition, respectively) already holds.

Proposition 5. An instance of SeqCSP(ΓPA ) with states Q1 , . . . ,Qd is T2-satisfiable (or T4-satisfiable) if for each 1 ≤ t ≤ d, Qt is strongly 3-consistent and, for each 1 ≤ t < d it holds that any partial solution of size 2 (size 4) of Qt can be combined with any partial solution of size 2 (size 4) of Qt+1 such that the T2-condition (and T4-condition, respectively) is satisfied.

Note that this includes instances on complete constraint networks without disjunctive relations, but moreover also instances which may contain disjunctive relations.

Example 5. Consider two variables {x, y} with constraints {x1 ≤ y1 , x2 = y2 , x4 = y4}. This instance contains disjunctive relations, but every base solution already satisfies the T2-condition (and T4-condition).

This observation may yield interesting heuristics and domain splitting strategies in constraint programming approaches for arbitrary instances.

6 Conclusion and Perspectives

In this paper we presented a study on transition constraints in the context of QSTR which arise in a variety of applications. We have introduced a generic approach to map such spatio-temporal reasoning problems to constraint languages and, in particular, to instances describing sequences of qualitative states.

For the main part of our work, we have focused on pointbased formalisms, in particular the Point Algebra, and provided definitions of two qualitative relations T2 and T4 which describe continuous transitions. They naturally extend to other point-based formalisms such as, e.g., Cardinal Directions and the Rectangle Algebra and are thus important.

We have used these relations to analyze the computational complexity of associated satisfiability problems. Our study is complete considering all fragments of the constraint language. These results show that reasoning with continuity is NP-complete for the Point Algebra, even if we just consider sequences of states and tiny, yet useful fragments. It immediately follows from our results that the same satisfiability problems of many other point-based formalisms are intractable even when considering only small fragments.

Future work includes considering structural properties of problem instances to find more tractable cases, and investigating the same problem setting for non-point-based formalisms, e.g., RCC. Another interesting line of future work is to integrate our tractability results in algorithms, e.g., in the constraint programming approach by Apt and Brand. Another promising line of research is to consider SAT-encodings of such formalisms, as our definitions of the continuity relations provide straightforward encodings.

Acknowledgments

The authors thank the anonymous reviewers for their helpful feedback. This work was supported by Deutsche Forschungsgemeinschaft in the Transregional Collaborative Research Center SFB/TR 8 Spatial Cognition project R4-[LogoSpace].