Temporal Sequences of Qualitative Information: Reasoning about the Topology of Constant-Size Moving Regions

1 Introduction

The ability to reason about temporal and spatial information together is essential for the resolution of complex tasks in a physical and dynamic environment. Several qualitative formalisms of different expressiveness have been proposed to describe the world and reason about it [see, e.g., Chen et al., 2015]. Temporal sequences of qualitative information, which are our focus in this paper, are sequences of descriptions, each one representing the state of the world at a specific time. Spatio-temporal reasoning tasks include the ordering of such temporal sequences [Sioutis et al., 2015] as well as the construction of interpolating temporal sequences, which are useful, for example, within spatial planning [Ragni &W¨olfl, 2005; Westphal et al., 2011]; but the main task consists in deciding the consistency of temporal sequences. This problem is complex because, in general, temporal consistency and spatial consistency cannot be decided independently. In addition, the consistency of a description depends on the properties of spatio-temporal entities. For example, enforcing the continuity of movements is essential to reason about a physical environment [Galton, 2000]. It can also be necessary to ensure that certain attributes of entities - such as size, position, orientation, or shape - are preserved over time, and to impose restrictions on movements that are allowed between instants of the sequence. These constraints create temporal interdependencies which impact the consistency of descriptions.

Example 1. Consider this temporal sequence: A blue box is in a red box during a first period. During a second period, the red box is in a green box, and either the blue box is in the red box or the red box is in the blue box. During a third period, the green box is in the blue box. This description is consistent with deformable boxes but inconsistent with rigid boxes.

Several approaches deal with temporal interdependencies by using (conceptual) neighborhood graphs [Freksa, 1992]. Note that the inconsistency of the description in Example 1 actually only depends on the size of objects being constant; the fact that the boxes are undeformable is not used directly. Size preservation is thus an important temporal interdependency, notably required when reasoning about rigid objects, but also useful when considering deformable regions having a constant size, such as articulated solid bodies, deformable bodies (for certain deformations), or liquids. Unfortunately, few formalisms deal with constant-size regions and, as we will show, they all have significant disadvantages.

In this paper, we propose a general framework to reason about temporal sequences of qualitative information, based on the recently introduced multi-algebras [Cohen-Solal et al., 2017]. Our approach can represent various kinds of interdependencies, notably those of neighborhood graphs, and it has computational advantages compared to known approaches. Moreover, we instantiate our framework in the specific case of sequences of topological information about constant-size regions moving continuously (such as rigid or articulated bodies). We show that the resulting formalism is complete for deciding consistency; in addition, leveraging general theorems from the multi-algebra framework, we identify its three maximal tractable subclasses containing all basic relations.

2 Background and RelatedWork

2.1 Qualitative Formalisms

We recall the main concepts relative to qualitative temporal and spatial reasoning; details and references can be found in Ligozat [2013]. In qualitative reasoning, information about spatial or temporal entities of the world is given using binary relations from a finite set B. For example, the relative size of two entities x and y is entirely characterized by an element of the set BPA = {<,=,>}. Relations from B are called basic: exactly one of them holds between any two entities. A composite relation (or simply a relation) is actually a set of basic relations, that is, a subset of B; it represents less precise information - e.g., "x {<,=} y" means that either x < y or x = y, while "x BPA y" gives no information. The set A = 2B of all relations built from B forms a non-associative relation algebra. The point algebra PA, whose basic relations are BPA, is one of the simplest examples. Another well-known algebra is RCC8, which describes topological relations between regions, i.e., in this paper, nonempty regular closed subsets of Rd . The basic relations of RCC8 are illustrated in Fig. 1.

Descriptions are often given as qualitative constraint networks. A network N over an algebra A is a finite set E of entity variables, together with one relation from A (a constraint) for each pair of distinct variables. We denote by N xy the relation between entities x and y (implicitly, N yx =N xy ) : e.g., the network such that N xy = {PO}, N yz = {TPP}, and N xz = {DC} describes the topology of three unknown entities x,y,z. Note that all relations are basic in this network: it is then called a scenario. A fundamental question about such a description is its consistency: can we find entities satisfying it? Algebras are in fact equipped with operators over relations, intersection ∩, converse ¯·, and (weak) composition ⋄, which enable a form of deductive reasoning: their application can remove some basic relations from a composite one, yielding more specific information. From the first two constraints in the scenario shown above, we can infer that the basic relation between x and z must be in {PO,NTPP,TPP}; since this is disjoint from N xz , we can conclude that the scenario is inconsistent.

2.2 Neighborhood Graphs

Neighborhood graphs have been proposed to reason about change [Freksa, 1992]. They encode the ways relations between entities can change over time: Two basic relations are connected in a neighborhood graph if by continuously deforming two entities satisfying the first relation, we can make them satisfy the second one without any other relation occurring during the deformation. The two graphs in Fig. 2 [Gerevini & Nebel, 2002] show the neighborhood of topological relations, for variable-size and constant-size regions. Suppose that TPP holds between two regions; deform them continously until the relation does not hold, then stop immediately. As Fig. 2.a shows, the new relation can only be NTPP, PO, or EQ in general, but if the regions have a constant size, then Fig. 2.b indicates that it can only be NTPP or PO.

One of the applications of neighborhood graphs is to ensure that a temporal sequence of scenarios N1, . . . ,Nm - each Ni describing the situation at some fixed instant ti - is compatible with the property of continuity without intermediary relations (or continuous qualitative change) [Westphal et al.,

2013], which is notably useful for qualitative planning [Ragni &W¨olfl, 2005; Westphal et al., 2011]. A temporal sequence of scenarios is considered consistent if there exist entities evolving continuously and satisfying Ni at each instant ti; continuity without intermediary relations is the additional requirement that at any time between two fixed instants ti and ti+1, each pair of entities x, y only satisfies either N xy i or N xy i+1 . For example, the sequence "x TPP y, then x DC y" has no continuous solution without intermediary relations; in fact, a temporal sequence (r1, . . . , rm) of basic RCC8 relations satisfies continuity without intermediary relations if and only if it respects the neighborhood graph of RCC8, that is, for 1 ≤ i <m, either ri+1 = ri, or (ri, ri+1) is an edge in the graph.

2.3 RelatedWork

There are many studies about qualitative change, notably based on neighborhood graphs [e.g., Wu et al., 2014; Santos &Moreira, 2009], and about its applications [e.g., Cui et al., 1992; Dylla &Moratz, 2004]. On the other hand, reasoning about the simple temporal sequences of descriptions presented in the previous section is not largely studied. The only work that we know of is the general approach of Westphal et al. [2013], which duplicates all variables for each instant to add transition contraints enforcing the interdependencies.

However, spatio-temporal formalisms of higher expressiveness have been studied, in which the ordering of temporal entities is uncertain. In the formalism of Gerevini & Nebel [2002], descriptions consist of RCC8 relations that hold during temporal intervals, together with relations between these intervals: e.g., an interval I is before or after another interval, and during I the relation {DC,PO} holds between two regions. Ragni &W¨olfl [2006] introduced a similar formalism about directional relations of spatial points. The approach of Sioutis et al. [2014] has a different expressiveness - time entities are points and not intervals.

We are not aware of other "algebraic" qualitative spatiotemporal formalisms; but note that spatio-temporal reasoning is also studied in the context of logics [Bennett et al., 2002]. Spatio-temporal logics are more expressive, but less efficient: while deciding consistency is typically NP-complete with algebraic approaches, it is generally PSPACE-hard for logics.

Only two approaches, to our knowledge, deal with the preservation of region sizes in the context of evolving topological relations. The first one is the logic of Galton [1993], based on Allen's temporal logic. It allows for reasoning about rigid bodies with topological relations, but requires the knowledge of the precise size relation for each pair of regions. The second one is the formalism of Gerevini & Nebel [2002] mentioned above. It enforces size preservation by using the size and topology combination, duplicating all variables for each time interval I. It also ensures an evolution without intermediary relations thanks to a neighborhood graph. Yet, it is not clear whether or not this formalism ensures continuous movement; and no algorithm has been proposed to reason about non-basic descriptions.

3 Multi-Algebras for Temporal Sequences

Multi-algebras have recently been introduced [Cohen-Solal et al., 2017] in order to encompass into a common algebraic framework several forms of algebra combinations, notably loose integrations [W¨olfl &Westphal, 2009] and multi-scale representations [Cohen-Solal et al., 2015], but also temporal sequences. The latter application was illustrated with the simple example of temporal sequences of directional information (i.e., relations from PA) that enforce continuity without intermediary relations. We show here how this approach generalizes to any qualitative formalism, and, focusing on RCC8, how it can be adapted to the size preservation constraint.

3.1 Temporal Sequences and Projections

The relation between two entities in a temporal sequence of qualitative information can be seen as a tuple of relations, the i th relation being the one that holds at the i th instant in the sequence. Thus, the sequence in which a region x is inside another region y, then they overlap, and finally x is outside y corresponds to the tuple ({TPP,NTPP},{PO},{EC,DC}). Such relations are exactly the kind that multi-algebras are well-suited to represent. A multi-algebra is indeed a Cartesian product of algebras A1 ×· · ·×Am, a multi-algebra relation R hence being a tuple R = (R1, . . . ,Rm) of classical relations Ri ∈Ai. The multi-algebra of m-instant temporal sequences of topological information is thus simply RCC8 m . Yet, algebras in the product can also be distinct, which allows for combining information of heterogeneous nature into a relation: multi-algebras actually generalize loose integrations. For example, the well-known combination of topology and relative size [Gerevini & Renz, 2002] corresponds to the multi-algebra RCC8×PA: its relation ({DC},{<,=}) describes the fact that the two regions considered are disconnected and that the size of the first one is smaller or equal.

In most aspects, a multi-algebra behaves like several algebras independently gathered together: several classical notions can be transparently generalized to this framework by being applied componentwise. Thus, for two relations R and R′ , we write R⊆R′ if Ri ⊆R′i holds for each i, and R is said to be basic when each Ri is basic. More importantly, multialgebras are equipped with composition, converse, and intersection operators, which are simply applied componentwise (e.g., R⋄R′ is defined by ∀i : (R⋄R′ )i = Ri ⋄R′i ). It makes sense for temporal sequences, since it corresponds to applying the classical operators at all instants independently.

Nevertheless, the elements of the tuple are not always independent. For example, in order to guarantee continuity without intermediary relations on temporal sequences, each pair of successive relations must satisfy the neighborhood graph. In multi-algebras, interdependencies of this kind between individual components are enforced by additional operators, called projections. There is one projection for each ordered pair of algebras in the Cartesian product, which represents the interdependencies between the relations of these algebras. Formally, a projection ↱ j i : Ai ↦→Aj is a function associating, to each relation r of the algebra Ai, the relation r′ of the algebra Aj corresponding to the following semantics: if r holds, then r′ must hold. For instance, Table 1 gives the projections for the basic relations in the size-topology combination: the projection of {TPP} into PA is ↱PA RCC8{TPP} = {<}, since a region strictly included in another can only have a smaller size. The projections of other relations can be deduced from the table using formulas ↱ r = ⋃b∈r ↱{b} and ↱ ¯ r = ⋃b∈↱ r{ ¯b}.

Projections can enforce any neighborhood graph G: since it puts restrictions on basic relations of successive instants, but does not impose anything in other cases, the projection of b ∈ B from an instant i to an instant j is defined by ↱ j i {b}={b′ : (b,b′ ) ∈G}∪{b} if |i- j| =1, and ↱ j i {b} = B if |i- j| > 1. Using this, given any qualitative algebra A with a neighborhood graph G, we can build a multi-algebra representing temporal sequences of information from A in the context of continuity without intermediary relations. In the case of topological information, we get:

Definition 2. Let m∈N∗ . The multi-algebra TTwir of temporalized topology without intermediary relations is the Cartesian product RCC8 m equipped with projections enforcing the neighborhood graph in Fig. 2.a.

However, if we want to reason about constant-size regions, neighborhood graphs are not sufficient. Consider the relation (TPP,PO,TPP): it respects the graph of Fig. 2.b, but no pair of constant-size regions can satisfy it. This problem can be solved by reasoning about region sizes explicitly, in addition to the spatial reasoning. In a multi-algebra, this can be done by adding the point algebra to the Cartesian product. For topological reasoning, this yields RCC8 m ×PA: each relation is a tuple consisting of m topological relations (one for each instant) plus an extra relation indicating the relative size of the two regions. Projections from and to the added algebra are exactly those of the size-topology combination - which is thus a special case (m= 1) of this multi-algebra.

Definition 3. Let m∈N∗ . The multi-algebra TTcs of temporalized topology of constant-size regions is the Cartesian product RCC8 m ×PA equipped with the following projections: for all b, ↱ j i b=BRCC8 (no interdependency) for 1≤ i, j ≤m, and ↱m+1 i b and ↱i m+1 b defined by Table 1 for 1 ≤ i ≤ m.

The multi-algebra TTwir,cs of temporalized topology of constant-size regions without intermediary relations is the Cartesian product RCC8 m ×PA equipped with projections ↱ j i enforcing the neighborhood graph in Fig. 2.b for 1 ≤ i, j ≤ m, and the projections ↱m+1 i and ↱i m+1 of TTcs for 1 ≤ i ≤m.

These multi-algebras only ensure relative size preservation, but for some formalisms this suffices to guarantee the existence of a solution with constant-size regions. This technique of adding an algebra to the Cartesian product is a priori applicable to the preservation of other region attributes, such as orientation or position - as long as the added algebra can be meaningfully combined with the temporalized algebra.

3.2 Semantics of Temporal Sequences

As we have seen, multi-algebras are equipped with operators (composition, converse, intersection, and several projections)

that can be used to reason about their relations. To prove that reasoning using a specific multi-algebra is correct and/or complete, we need to define the semantics of its relations, i.e., the way they are actually interpreted. This requires expliciting a domain - the set of entities considered - and an interpretation function associating to each relation all pairs of entities that are considered as correct realizations of this relation.

In our context, we reason about regions that move continuously; an entity is thus what we call a continuous evolution of a region, that is, a continuous function indicating at each instant the current "state" of the region. 1 We consider two domains: the set R I of all continuous evolutions during an interval I ⊆R, and its strict subset R I cs containing all continuous evolutions of a constant-size region. More formally, R I (resp. R I cs) is the set of continuous functions f from I to the set of regions of Rd (resp. to the set of measurable regions of Rd satisfying ∃s ∈ R∗+ : ∀t ∈ I : m( f (t)) = s, with m a measure of region sizes). We can now define the semantics of TTcs (for space reasons, we do not define those of TTwir and TTwir,cs):

Definition 4. Let m ∈ N∗ , and let (t1, . . . , tm) ∈ Rm be an ordered sequence of m distinct instants. The interpretation function of TTcs is the function jTTcs : RCC8 m ×PA→(R[t1,tm] cs )2 associating to each relation R the set of all pairs of region evolutions ( f , f ′ ) satisfying R, i.e., verifying the RCC8 constraints at the corresponding instant (∀i ∈{1, . . . ,m}: f (ti) Ri f ′ (ti)) and the size constraints (m( f (t1)) Rm+1 m( f ′ (t1))).

This semantics satisfies good properties: the triple (TTcs, R[t1,tm] cs ,jTTcs ) actually constitutes a loosely combined formalism [Cohen-Solal et al., 2017]. This guarantees that reasoning is sound: using the operators to eliminate basic relations from a relation does not change its interpretation.

3.3 Deciding Consistency for Temporal Sequences

We have used multi-algebra relations to represent temporal sequences between two entities; like in the classical case, more complex descriptions can be given as qualitative constraint networks, whose constraints are multi-algebra relations. The following is an example of a network N (in fact a scenario) over RCC8 m ×PA: N xy = (TPP,PO,PO,<), N yz = (PO,TPP,PO,<), and N xz = (PO,PO,TPP,>).

Using the previous section, we can formally define a solution of a network as an assignment, to each entity variable from E, of one entity from the domain U considered, such that all constraints are satisfied: i.e., a set {ux}x∈E ⊆U verifying ∀x,y ∈ E: (ux,uy) ∈ j(N xy ). Note that one solution of a network satisfies exactly one scenario. To decide the consistency of a network, an intuitive method is to apply reasoning rules: using multi-algebra operators, we repeatedly remove "impossible" basic relations from the constraints. When nothing can be further removed, the resulting network N is said to be algebraically closed - because it is both closed under composition (∀x, y, z ∈ E : N xz ⊆ N xy ⋄N yz ) and closed under projection (∀x, y ∈ E : N xy j ⊆↱ j i N xy i for all distinct i, j).

Computing the algebraic closure of a network can yield empty relations, i.e., unsatisfiable constraints. Since reasoning is sound, this means that the initial network was inconsistent. An algebraically closed network containing no empty relation is called algebraically consistent, in the sense that algebraic reasoning cannot prove its inconsistency. Yet, in the general case, we cannot conclude anything about the consistency of an algebraically consistent network - even if it is a scenario. Having no inconsistent closed scenario is a fundamental property of a formalism, which depends on its interpretation function. This property is important because it provides a complete procedure for deciding consistency - a simple search for a closed scenario, typically using a branch-andbound algorithm that applies the algebraic closure. A formalism or fragment satisfies the stronger property of algebraic tractability when algebraically closing a network, which can be done in polynomial time, suffices to decide its consistency.

1 We cannot detail this for space reasons, but formally the notion of continuity requires one to specify a topology for the set of regions.

3.4 Computational Advantages of Multi-Algebras

Multi-algebras are well-suited for reasoning about temporal sequences with a large number of interdependencies, because, unlike other approaches such as that of Westphal et al. [2013] or Gerevini & Nebel [2002], there is no need to duplicate the entities for each instant of the sequence so that interdependency constraints can be added between an entity and itself at a different time (e.g., for preserving region sizes). In particular, the algebraic closure can be enforced in time Q(m· n 3 +m 2 · n 2 ) with multi-algebras, whereas it is in time Q(m 3 · n 3 ) if variables are duplicated. Not duplicating variables has a second advantage: a branch-and-bound search for a closed scenario of a network (to decide its consistency in intractable cases) has a significantly smaller branching factor. However, contrary to that of Westphal et al. [2013], our approach cannot prevent qualitative changes on distinct pairs of entities to occur "in parallel" between instants.

4 Temporalized Topology with Constant Sizes

We now focus on TTcs, that is, on the case of size preservation for temporal sequences of topological information; solutions must be continuous, but intermediary relations may occur. We show that reasoning with TTcs is complete, and we identify its maximal tractable subclasses containing all basic relations.

4.1 Completeness of Reasoning for TTcs

This section shows a fundamental result: the algebraic closure suffices to decide the consistency of all scenarios over TTcs. Note that the proof is very specific to the RCC8 case - there is no guarantee that a similar result holds for any other spatial algebra A. In particular, a necessary condition is the consistency of all closed scenarios for the corresponding combination A×PA (i.e., the m= 1 case); this notably does not hold if A is the interval algebra [Ligozat, 2013, Ch. 8].

Proposition 5. Algebraically closed scenarios over TTcs are consistent (considering regions of Rd , d ≥ 2).

Proof. Let N be an algebraically closed scenario over TTcs, with n entity variables x1, . . . , xn and m instants t1, . . . , tm. We show that it is possible to assign to each xi an element fi of R[t1,tm] cs (a continuous evolution of a constant-size region) such that all constraints are satisfied. Since we only have to prove the existence of one solution, in order to make the proof as simple and clear as possible, we choose a specific form for our regions and their moves, and we make them satisfy relations in a very specific way. In particular, since intermediary relations are allowed, we can deal with each instant independently; in fact, we only have to show that for any closed RCC8 scenario, our regions can be moved one by one and continuously so that, starting from a fixed configuration where they are all disjoint, we get a configuration satisfying the scenario. Since this continuous evolution can be reversed, the initial configuration can be used as an intermediary configuration between all instants, ensuring that the evolution is continuous throughout the whole sequence.

Region size. Since N is closed by composition and closed scenarios are consistent for PA, we can associate to each entity an integer rank(xi) ∈ {1, . . . ,n} such that the ranks satisfy the size constraints. Without loss of generality, we assume that the xi are in ascending order with respect to their ranks, and that ranks are successive integers (∀i ∈ {2, . . . ,n}: rank(xi-1) ≤ rank(xi) ≤ rank(xi-1)+1). Entities of rank 1 are the smallest regions, entities of rank 2 are the second smallest, etc. Of course, the rank of an entity does not depend on the instant we consider: this will guarantee that the size of an entity does not change between instants.

Region definition. Let us consider a closed RCC8 scenario. We write R i j for the basic RCC8 relation that must hold between xi and xj at this instant. We build each region as a disjoint union of subregions, namely, closed balls of Rd : this allows us to make a region interact with each other region independently. For each i, subregions of xi all have the same radius 3 rank(xi) (for it to be more than two times the radius of lower-rank balls - the reason for this will be clear later); they remain disjoint at all times, even while they move (this is never a problem in Rd , d ≥ 2), so that the size of xi remains constant. There are n primary subregions in xi, denoted P j i (1 ≤ j ≤ n), which will be used to enforce "local" relations (notably EC and PO) with each other region xj. Since xi may have to include (because of TPP or NTPP relations) all regions of lower rank, which in the worst case could all be disconnected (DC), we add to xi as many secondary subregions as there are subregions of (strictly) lower rank. Thus, for each k such that rank(xk) < rank(xi), for each subregion P of xk, we add to xi a subregion Pi(P) reserved for covering P if needs be. Note that entities of the same rank have exactly the same number of subregions, and thus the same size.

Starting configuration. Initially, all balls are disjoint and their centers all lie on a single line, chosen arbitrarily and called the axis (we also choose "left" and "right" directions along the axis). Except during moves, the center of each ball is always on the axis. We call the interaction zone Z(P) of ball P, the fixed area centered around the initial position of P - note that interaction zones never move. We suppose that interaction zones are disjoint, and that each one is large enough to contain a ball of radius 3 n+1 (larger than any subregion). Initially each Z(P) only contains its P. We make sure at all times that there is at most one subregion of each entity in each zone: this is a simple way to ensure that subregions of an entity always remain disjoint. We write Zi = {Z(P i ) |

P i subregion of xi} for the set of interaction zones of entity xi. If R i j = EQ for some i, j, we can move each subregion of x j so that it becomes equal to a distinct subregion of xi. Since the network is closed, this is always possible (xi and xj have the same rank) and harmless (∀k : R ik = R jk ). We can then identify xi and xj, that is, we can lock their subregions so that they always move together. Thus, in the following, we can assume without loss of generality that i ̸= j ⇐⇒ R i j ̸=EQ.

Step 1: "local" relations. For each pair i, j such that i < j (the order is irrelevant here), we do the following: (i) if R i j = PO, move P i j to make its center coincide with that of P j i (see Fig. 3.a,b); (ii) if R i j =EC, move P i j tomake its leftmost point coincide with the rightmost point of P j i (see Fig. 3.c,d); (iii) if R i j = TPP, move P i j to make its rightmost point coincide with the rightmost point of P j i (see Fig. 3.e). It is not hard to see that, at the end of this pass, there is at most two subregions in each interaction zone (and they belong to distinct regions, so the size of each region has not changed), no P j i such that i < j has moved, and all relations PO and EC are verified.

Step 2: inclusions. We now "only" need to make our regions satisfy the TPP and NTPP relations. Note that in Step 1, we have guaranteed an interior connection for each TPP relation, so this is out of the way - we just have to enforce the inclusions. This is the hardest part: we must cover all subregions from the included entity while avoiding side effects on other entities, and we must also take care of not undoing previous moves. To achieve this, (i) we process entities in ascending size order, ensuring that when we process xi, no subregion of xk with k ≤ i can move again; and (ii) for each entity, we do not iterate on its relations but on its interaction zones, treating all balls that happen to be there. Subregions of xi that moved to another zone have already been processed (subregions can only move to zones of lower-index entities).

Concretely: For each i from 1 to n, consider each interaction zone Z(P i ) ∈Zi. If it is empty, P i moved to another zone: we do nothing. Otherwise, there can only be six configurations, shown in Fig. 3. For each k from i+1 to n, we examine whether we need to add a subregion of xk in this zone. It is never necessary if there is already one, but otherwise it must be done in two cases: (i) R ik ∈ {TPP,NTPP}, so P i must be covered by a subregion of xk; (ii) the zone contains a ball of some other entity x j, which was moved there in Step 1 or earlier in this iteration, and R jk ∈ {TPP,NTPP} (this case can concern several balls, each from a distinct entity). If there is at least one ball to cover and no subregion of xk is there, then we move subregion Pk(P i ) from its starting position (by construction, it has not moved) to Z(P i ), so that it covers all balls that need to be covered and does not overlap any ball that must not be overlapped. To achieve this, except in one special case, it is enough to simply make the center of Pk(P i ) coincide with the interaction point of Z(P i ) (see Fig. 3), which only depends on its configuration at the end of Step 1. The special case occurs when the zone has been used to enforce EC (Fig. 3.c,d) and we must cover the ball on the left (resp. right) without overlapping the ball on the right (resp. left). In this case, we make Pk(P i ) tangent to the interaction point, positioning its center on the left (resp. right) side of the axis (green dotted balls in Fig. 3.c,d). We can prove, using the composition table of RCC8, that no resulting inclusion or overlap can contradict any constraint in the scenario (in particular, if Pk(P i ) is larger than all balls present, it covers them all).

Hence, searching for an algebraically closed scenario is sufficient to decide the consistency of any network over TTcs: reasoning with TTcs is complete for deciding consistency.

4.2 Tractable Subclasses of TTcs

Prop. 5 entails that deciding consistency on TTcs is in NP (exhibiting a closed scenario proves the consistency of a network). Yet, since any RCC8 network has an equivalent polynomial-size TTcs network, deciding consistency on TTcs is actually NP-complete. Consequently, we now turn to the identification of tractable fragments, and notably subsets of TTcs that are closed under composition, intersection and converse - called subclasses [Ligozat, 2013]. Our results rely on the theorems of Cohen-Solal et al. [2017], which provide sufficient conditions for a multi-algebra subclass to be algebraically tractable. Space constraints prevent us from detailing these conditions, but our proofs contain all arguments necessary to check them using the original paper as reference.

Before identifying maximal tractable subclasses of TTcs, we prove the tractability of an intermediary subclass: the Cartesian product of m instances of the (non-convex) maximal distributive subalgebra of RCC8 [Long & Li, 2015], denoted RCC8max, and of PAmax = {<,=,>, ̸=,BPA}.

Proposition 6. The subclass RCC8max m ×PAmax of TTcs is algebraically tractable.

Proof. We weaken all the projections from PA (Am+1) to RCC8 (Ai with i <m+1): we consider that ↱RCC8 PA b=BRCC8 for all b ∈ BPA. We will prove that the subclass with weakened projections is algebraically tractable, which directly entails that the original subclass also is.

We apply the slicing theorem of Cohen-Solal et al. [2017, Th. 24] to the subclass with weakened projections, using identity functions as refinements: (I) Algebraically closed scenarios for the weakened projections are consistent, because they are closed for the original projections and by Prop. 5. (II) C1: networks over RCC8max and PAmax that are closed under composition are minimal [Long & Li, 2015].

(III) C2: the subclass is simple because (i) RCC8max×PAmax (m = 1) with weakened projections is simple [Cohen-Solal et al., 2017], (ii) between two relations Ri and Rj over RCC8, there is no direct interdependency (↱RCC8 RCC8 b = BRCC8 for all b), and (iii) being closed under projection is a local property. (IV) C3: ↱-consistent relations are consistent. Indeed, this is true for basic relations (Prop. 5); for non-basic ones, we can choose a basic PA relation, then independently pick a compatible RCC8 relation for each instant, since, once again, Ri and Rj are independent when i, j <m+1. (V) Finally, by similar arguments as for condition C2, the subclass is ↱-closed.

Now, we identify the three maximal tractable subclasses of TTcs containing all basic relations, based on the classical subclasses of RCC8, namely ̂H8, C8, and Q8 [Renz, 1999].

Theorem 7. The maximal tractable subclasses of TTcs that contain BRCC8 are ̂Hm 8 ×PA, C m 8 ×PA, and Qm 8 ×PA.

Proof. Let S be ̂H8, C8, or Q8. We use the refinement theorem of Cohen-Solal et al. [2017, Th. 26] to show that S×PA is algebraically tractable, by refining it to RCC8max m ×PAmax using H = (hS, . . . ,hS,hmax), with hS the usual refinement of S to basic relations [Gerevini & Renz, 2002, Fig. 2] and hmax the refinement of PA to the basic relations of maximal dimension [see Cohen-Solal et al., 2017]. (I) C1: S m ×PA is algebraically stable by H, because (i) it is the case for m= 1 [Cohen-Solal et al., 2017], (ii) there is no direct interdependency between the instants of the sequence, and (iii) being closed under projection/composition are local properties. (II) C2: RCC8max m ×PAmax is algebraically tractable (Prop. 6). (III) S m ×PA is ↱-closed using the same arguments as for C1. Hence, by the refinement theorem, S m ×PA is tractable. Now, since ̂H8, C8, and Q8 are the only three subclasses of RCC8 that contain all basic relations and that are maximal for tractability (assuming P ̸= NP) [Renz, 1999], ̂Hm 8 ×PA, C m 8 ×PA, and Qm 8 ×PA are thus also maximal.

5 Conclusion and Perspectives

We propose a general approach, based on multi-algebras, to reason about temporal sequences of qualitative information, which is more efficient than state-of-the-art approaches. We notably introduce the new formalism of temporalized topology of constant-size regions, whose reasoning is complete for deciding consistency. Moreover, we have identified its maximal tractable subclasses containing all basic relations.

This article is limited to temporal sequences, but its ideas can notably be applied to the more temporally expressive approach of Sioutis et al. [2014], providing it with a complete reasoning procedure dealing with topological relations between constant-size regions.

Future work will focus on the enforcement of continuity without intermediary relations, with and without size preservation; we conjecture that deciding consistency is also complete in these cases. We also plan to show that multi-algebras can enforce dominance diagrams [Galton, 2000], which generalize neighborhood graphs, and address continuity without intermediary states [Westphal et al., 2013].