On (Maximal, Tractable) Fragments of the Branching Algebra ?

Abstract

Branching Algebra is the natural branching-time generalization of Allen's Interval Algebra. Its potential applications range from planning with alternatives, to automatic story-telling with alternative timelines, to checking version systems with several branches. As in the linear case, the consistency problem of Branching Algebra is computationally hard, and, in particular, NP-complete. Recently, tractable fragments of it have been studied, but the landscape of tractability of fragments is far from being complete. In this paper, we identify three interesting fragments of the Branching Algebra: the Horn fragment, which was already known, the Pointsable fragment, and the Linear fragment. We study their tractability as well as their tractability via Path-Consistency, and we discuss their maximality.

Keywords

• Constraint programming • Consistency • Branching time •
• Tractability of fragments

-

When dealing with automated temporal reasoning, one of the most prominent formalisms is certainly Allen's Interval Algebra [ 1 ] (IA). Applications of the IA encompass a large number of elds, including scheduling, planning, database theory, natural language processing, among others. Events in the IA are represented as intervals on a linearly ordered set, and can be related to each other through one of the thirteen basic relations (IAbasic). A relation is a constraint that speci es which basic relations may hold between a pair of intervals, so the IA has a total of 213 relations. A constraint network is a pair formed by a set of interval variables and a set of constraints between them; the fundamental reasoning task that arises when dealing with constraint networks is the consistency problem, that is, the problem of establishing whether it is possible to satisfy all given constraints, asserting the existence of a realization of the network. This problem, which is archetypical for the class of Constraint Satisfaction Problems (CSP), is NP-complete for generic IA networks, as shown by Vilain and Kautz [ 17 ], and therefore, in general, solutions can only be found by exploring the tree of all possible assignments. For this reason, in the nineties and early two thousands the research has focused towards nding the tractable fragments of the IA, that is, subsets of relations for which the consistency problem is tractable. The tractability landscape of the IA is completed by listing all maximal tractable sub-algebras of it, that is, all tractable fragments that cannot be further extended without losing the tractability. After [ 9 ], such a landscape is fully known, and it encompasses 18 incomparable, maximal, tractable fragments of the IA. Some tractable fragments, even non-maximal, are noteworthy because of the technique used to show their tractability, the naturalness of their relations, and their applications: the convex fragment [ 16 ] (IAconvex, 82 relations), the pointisable fragment [ 17 ] (IApoint, a superset of IAconvex with 182 relations), and the ORD-Horn fragment [ 13 ] (IAHorn, also known as IApreconvex [ 10 ], with 868 relations, which extends IApoint and is maximal).

The Branching Algebra (BA) [ 14 ] is the natural generalization of the IA to tree-shaped orderings. Its potential applications, additional to the classical ones, range from planning with alternatives, to automatic story-telling with alternative timelines, to checking version systems with several branches. The set of basic branching relations (BAbasic) contains all of the 13 IAbasic relations, plus six new `branching' basic relations, which take into account the possible incomparability of interval endpoints, for a total of 19 basic pairwise-disjoint and jointly-exhaustive relations. Quite obviously, the consistency problem for the BA is still NP-complete [ 14 ] and therefore, just like in the linear case, we are interested in nding tractable fragments, in particular the maximally tractable ones. Unlike the linear case, however, the landscape of tractability in BA is still far from being complete. Only two tractable fragments are known: the convex (BAconvex) fragment [ 8 ], which resembles its linear counterpart, and the TORD-Horn fragment (BAHorn) [ 3 ], inspired by the ORD-Horn fragment of the IA.

In this paper we focus on the tractability of fragments of the BA, and we study both tractable fragments and PC-tractable ones, that is, tractable by Path-Consistency (PC-tractability is a desirable property which is not guaranteed by tractability). In particular, we show that BAHorn is maximally tractable (its PC-tractability was already known from [ 3 ]), we introduce two new tractable fragments, called BAlin (the linear fragment of the BA) and BApoint (the pointisable fragment of the BA), and we discuss both their PC-tractability as well as their maximality. b a c d Notation. Let (T ; <), often denoted by T , a right-branching tree-order, i.e. a partial order where:

8x; y; z 2 T : (x < z) ^ (y < z) ) (x R y): When variables are interpreted as time points, (T ; <) is called a future branching model of time (or, simply, a branching model ). Elements of T are denoted by a; b; : : :, and a k b (resp., a R b) denotes that a and b are incomparable (resp., comparable) with respect to the ordering relation <. We use x; y; : : : to denote variables in the domain of points, and x y to denote x < y _ x = y. There are four basic relations that may hold between two points on a branching model: equals (=), incomparable (k), less than (<), and greater than (>); the rst two are symmetric, while the last two are the converse of each other. These relations are depicted in Figure 1 (left-hand side), and are called basic branching point relations. The set of basic branching point relations is denoted by BP Abasic. In the linear setting, the set of basic relations has only three elements, <; = and >, and it is called P Abasic (basic point relations ).

An interval in T is a pair [a; b] where a < b, and [a; b] = fx 2 T : a x bg. Intervals are generically denoted by I; J; : : : For an interval I, we use I ; I+ to denote its endpoints. Following [ 7 ], one can describe 24 basic branching relations based on the possible relative position of two pairs of ordered points on a branching model, that is, by directly generalizing the universally known set of 13 basic interval relations [ 1 ] (IAbasic). Some of these relations require rstorder quanti cation to be de ned: for example, in Figure 1 (right-hand side) we see that, in order to distinguish the two situations, we need to quantify over the existence, or non-existence, of a point between a and c. This problem becomes relevant when we study the behaviour of branching relations in association with the behaviour of branching point relations (that is, by studying the properties of their point-based translations); to overcome it, Ragni and Wol [ 14 ] introduce a set of coarser relations, characterized by being translatable to point-based relations using only the language of endpoints, without quanti cation. These 19

b (bi)

I before J m (mi)

I meets J

I+ < J

I+ = J

I overlaps J

I during J

I starts J

I nishes J

I equals J

I J I J I < J < I = J < I = J < J = J < I+ < J + I J

J + I I

I < I+ < J + J < I+ < J + J

I < I+ = J + J < I+ = J +

k I+ < I+ k J + < I+ k J + I

J

I+ J I+ I+ I+ I I I J I+ I I+ J + o (oi) d (di) s (si) f ( ) e ie u ib (ibi) I init. before J I < J im (imi) I init. meets J I

I init. equals J I

I unrelated J

I k J

J J + I+ J + I+ J + I+ J + J J I J

J + J + J + I+ J + I+ J + relations are depicted in Figure 2, and form the set of basic branching interval relations (BAbasic); for each relation, the symbol in parentheses corresponds to its converse, if the relation is not symmetric. A relation in the set BAbasic is either a linear relation, or the relation u (unrelated ), or it corresponds to the disjunction between a pair of ner relations from the set of 24 [ 7 ]. For example, the relation ib is the disjunction of the two relations in Figure 1. Operations and algebras. Given the basic relations r1; : : : ; rl, we denote by R = fr1; : : : ; rlg the disjunctive relation r1 _ : : : _ rl; thus, a relation is seen as a set, and a basic relation as a singleton. As the set IAbasic contains 13 elements, the set IA of all interval relations in the linear setting encompasses 213 elements, including the empty relation; similarly, the set BAbasic of 19 basic relations entails 219 interval relations in the branching setting. A constraint is an object of the type x R y, where x; y are interval variables and R is a relation.

There are three basic operations with relations: (Boolean) intersection, converse, and weak composition (often called simply composition). The converse of a basic relation is de ned as:

8x; y; r : x r^ y , y r x; and the converse of a relation is simply the union of the element-wise converse of its basic relations. In our notation, for example, bi (after ) denotes the converse of the basic relation b (before), and fimi; u; og is the converse of the relation fim; u; oig. The weak composition of two basic relations is de ned as follows: 8x; y; r; s : x (r s) y , 9z j x r z ^ z s y: Again, the composition of relations is de ned by the union of element-wise composition of its basic relation. Intuitively, weak composition is the application of transitivity of relations, and it is usually computed via a composition table. For example, given three intervals I; J; K for which I fsg J and J fog K, then we know that I (fsg fog) K = I fb; m; og K. The composition table for the IA is shown in [ 2 ], and for the BA in [ 15 ]. Converse, intersection, and weak composition are classical operations in the literature; however, we can de ne a new operation that is interesting for us, called strong composition, by combining weak composition and intersection. For basic relations we have that: 8x; y; r; s; t : x ( (r; s; t)) y , t 2 (r s); and for relations, that: 8x; y; R; S; T : x ( (R; S; T )) y , x (R S) y ^ x T y (recall from the preliminaries that basic relations are represented with lower-case letters, while relations are represented with upper-case letters).

Back to the previous example, suppose we also knew that I fm; sg K; the relation I fb; m; og K could still be re ned without using any new variable: indeed, by strong composition, we have that I ( (fsg; fog; fm; sg)) K = I fmg K, which is in fact a stronger result. Strong composition associates three relations, and its x-point application provides Path-Consistency.

Given a relation algebra A, if a set of relations S A is closed under converse, intersection, and weak composition, we say that it is a strong subalgebra of A, while if it is closed only under converse and strong composition, then it is a weak subalgebra. Obviously, every strong algebra is also a weak algebra, but the converse is not true in general; a special case occurs when the unknown relation > (i.e. the relation formed by the union of all basic relations, sometimes denoted by \?") is an element of S: then, if S is a weak algebra it must also be a strong one. Following [ 13 ], we can de ne a closure operator 1; 2;:::() that maps any given set (fragment) S to its algebraic closure, by repeatedly applying the operations 1; 2; : : : until a xed point is reached. In particular, ^;\; (S) (or simply ), computes the generated (strong) subalgebra of S.

Decision problems. Given a fragment S of a relation algebra A, an instance of S is a pair hV; Ri where V is a set of variables (e.g., points or intervals) and R

R 7! Abasic such that: is a set of relations between the variables. Instances are usually represented by labelled direct digraphs, where the vertices represent the variables and the labels on the edges represent the relations. An interpretation I of is an assignment 8r 2 R : r ! r0 j r0 r ^ r0 2 Abasic: A non-contradictory interpretation, that is an interpretation whose constraint can all be satis ed by at least one set of concrete elements in the underlying order, is called a model. Finally, if an instance has at least one model is said to be consistent. The problem of determining whether an instance of S has a model or not is the consistency problem A-SAT(S), and the problem of determining whether all of the basic relations in each relation of an instance can appear in at least one model is the minimal labels problem A-MIN(S); since the tractability of A-MIN depends on the tractability of A-SAT (see [ 17 ]), we can focus solely on the latter. In particular, we say that a fragment S is tractable if and only if A-SAT(S) is tractable; a tractable fragment S A which cannot be extended without losing its tractability, is said to be maximally tractable, or, simply, a maximal fragment.

Assuming that A is NP-complete, as it is the case for both the IA ([ 17 ]) and the BA ([ 14 ]), and that P 6= NP, we are interested in nding all the maximal tractable subalgebras of A, because the tractability of any fragment depends on the tractability of its generated subalgebra [ 13 ]. Finally, a fragment is said to be PC-tractable if its consistency problem is decided by the so called path-consistency algorithm (which is a special case of the local consistency algorithm [ 11 ]). PC-tractability of a fragment is a desirable property, as a PCtractable fragment S can be used as an heuristics to speed up a consistency checking brute force algorithm for a non-polynomial algebra A (see, e.g. [ 5 ]). The path-consistency algorithm has also a xed complexity: O(n3), where n is the number of distinct variables of an instance, and being a very well-known algorithm, optimized implementations abound. Studying the PC-tractability of tractable fragments is therefore an interesting problem. 3

Some Tractable Fragments of the Branching Algebra Tractable fragments of the IA. In the linear case there are 18 tractable fragments of the IA [ 9 ]. Three of them are noteworthy: IAconvex, IApoint, and IAHorn. In particular, IApoint is characterized by the fact that every instance of IApoint can be polynomially translated to an instance of the P A, e ectively reducing the interval-based problem to a point-based one. In general, for any intervals-based relation algebra A, there always exists a pointisable fragment Apoint whose relations can all be exhaustively expressed only by conjunctive constraints between intervals endpoints: this allows us to create a point mapping operator which translates any interval algebra instance into an equisatis able point algebra instance 0 in polynomial time. IApoint is obtained by applying the operator on IA. IAconvex [ 16 ] is a fragment of IApoint that uses only convex point-based relations; while in both cases, Path-Consistency decides the consistency of an instance, in IAconvex it also decides its minimal labels problem, unlike IApoint [ 17 ]. IAHorn [ 13 ] includes IApoint as a fragment, and is PCtractable as well. The common characteristics to these three fragments, besides the fact that they all are strong algebras, is that they have been studied via their point-based translation. In the case of IAHorn, unlike IApoint and IAconvex, an interval-based instance cannot be simply translated to a point-based one; yet, its PC-tractability is a consequence of developing a Horn point-based logical theory (known as the ORD-Horn theory [ 13 ]). The remaining 15 other tractable fragments have been studied mostly in [ 6 ] and [ 9 ], in a rather systematic way, and the problem of their PC-tractability has not been posed; their importance relies in the fact that they complete the tractability landscape of the fragments of the IA, more than the naturalness of their de nition or their actual practical implications.

The Convex and the Horn Fragment of the BA. In the branching case, only two tractable fragments are known so far. The BAconvex fragment [ 8 ] is the natural branching counterpart of IAconvex. Unlike the latter, however, it is only a weak algebra; yet it is PC-tractable and, as it is for IAconvex, PathConsistency decides the minimal label problems as well. The BAHorn fragment, which extends BAconvex, and that has been introduced in [ 3 ], has been proven to be PC-tractable by developing a tree-order point Horn theory (TORD-Horn), in a way similar to the linear counterpart. The question we pose now is: which additional fragments of the BA can be discovered by a systematic analysis of their translations to the branching point-based framework? The Point and the Linear Fragment of the BA. In [ 4 ], Broxvall introduces the branching disjunctive point algebra, which extends the standard (conjunctive) branching point algebra by allowing disjunctive constraints in its instances; for example, in a disjunctive algebra, a constraint such as: (x < y _ y

z) _ (x k y _ z = t); inadmissible in a classical algebra, is allowed. Formally, given a conjunctive point algebra A and two fragments S1; S2 A, we can build the derived disjunctive fragment S1 _S2 which contains the relations given by binary disjunctions over S1 and S2. Furthermore, we have that S1 = S and Si = Si 1 _ S, so Sk means that relations are k-disjunctions of the relations in S. Finally, S = Si1=0 Si, indicates that we can use an arbitrary amount of disjunctions for our relations. Besides their naturalness, disjunctive fragments in the point-based case are interesting because they allow to de ne non-pointisable fragments in the interval case. In the linear setting, for example, IAHorn can be translated to a certain disjunctive fragment of P A (although the disjunctive point-based fragments have not been explicitly studied in the linear case). An analysis of the disjunctive fragments of the BP A led Broxvall to determine that there are exactly ve maximal tractable The de nition of the and `base fragments' is provided in Tab. 1. The tractability of these fragments if proven by devising a speci c algorithm; it does not imply their PC-tractability, and, as a side note, the complexity of their consistency algorithm is slightly worse than O(n3).

Given any two fragments S1 and S2 of BP A, we can compute ( 1(S1_S2 )), where 1 is the inverse of the point mapping operator extended to disjunctive point algebras. Note that there is only a nite number of disjunctions which can be allowed in BA; also, from an implementation perspective, instead of systematically trying all possible combinations, 1(S1 _ S2 ) can be e ciently computed by a slightly modi ed version of [( 1(S1) [ 1(S2)), which assures that the relations of S1 (or their derived) are not combined between themselves (by de nition, we allow arbitrary disjunctions only of S2). By looking at Tab. 1, we see that TC and TD can be immediately excluded from our analysis since they do not contain the relation <, which is needed to state the natural constraint 8I : I < I+ (it is interesting to note that their mappings degenerate into the whole BA). Also, it is the case that BAHorn = ( 1(TE )): this equivalence, which is also an alternative way to show the tractability of BAHorn (but not to show its PC-tractability), becomes clear when comparing the de nitions of TE in Tab. 1 and those of TORD clauses given in [ 3 ]. By applying the mapping on TA which, after closure by converse, is equal to BP A, we obtain the branching equivalent of IApoint, that is, BApoint, which is a rst new tractable fragment of the BA. If, instead, we apply this mapping to TB, we get another previously unknown fragment, which we called BAlin because all the relations contained in TB are linear except one: the relation 6=. As the 6= relation is interpreted as < _ > _ jj, it is not linear, so BAlin is not a subset of IA, as its name may suggest.

Theorem 1. The fragments BAHorn, BAlin and BApoint are tractable strong subalgebras of the BA.

The fact that they are strong subalgebras can be proved by a systematic computer-assisted check; we provide the proof of tractability.

Proof. It is easy to see that BAHorn = ( 1(TE )), BApoint = ( 1(TA)), and BAlin = ( 1(TB)), therefore it is possible to convert any instance of BAHorn, BAlin and BApoint to an instance of (respectively) TE , TB and TA via , which operates in polynomial time. tu Tractability and PC-tractability. BAHorn, BApoint, and BAlin are tractable; their tractability, however, does not imply their PC-tractability. As a matter of fact, BAHorn is PC-tractable, as shown in [ 3 ]. For the other two fragments, unfortunately, we only have partial results; in particular, the following holds: Theorem 2. The Path-Consistency algorithm is complete for checking the consistency of instances of BAHorn. On the contrary, it is not complete for checking the consistency of instances of BApoint.

The fact that the consistency of instances of BAHorn can be checked by Path-Consistency has been shown in [ 3 ].

Proof. The fact that Path-Consistency is incomplete for checking the consistency of instances of BApoint can be shown by proving the existence of at least one inconsistent, but PC-consistent, instance. One such example is given in Fig. 3. tu Whether BAlin instances can be checked by Path-Consistency or not is an open problem; extensive search for counterexamples gave negative results.

The known fragments of BA are reported in Fig. 4. As we can see, IAconvex and BAconvex are the smallest tractable fragments di erent from the set of basic relations only; as we have already observed, however, IAconvex is a strong algebra, while BAconvex is a weak algebra. Its strong closure, (BAconvex), is slightly bigger. The importance of BAconvex lies in the fact that, besides being PC-tractable, the Path-Consistency is also complete for minimal labels. The PC-tractability of its strong closure, instead, is a mere consequence of the PCtractability of BAHorn. IAHorn and its strong closure in BA are also, obviously, PC-tractable, as they are both subsets of BAHorn. Finally, observe that BApoint is not included in BAHorn, unlike its linear counterpart, and that BAlin does not even have a linear counterpart, although it is a proper superset of IAHorn (and its closure). While it cannot be seen in the gure, it is interesting to point out that BAlin is the only set which does not contain any basic branching relation (like u or ibi), and if we try to extend it by adding any one of them, we always end up with a non tractable fragment of BA.

bi;d f

;oi g M

fbi; d; mi; oi; s; sig fibi;imi;fdu; ib; ibi; im; imi; bi; di; oi g g ig s ; i o ; i d ; i m i ; m i ; i b i ; e i f

L fe ; d ; d i ; f ; f i ;m i ; o ; o i ; s ; s i g I fb; d; di; mi; o; oig fie;im

i;e;d;f;sg f ib; ibi; im; imi; b; d; og

J ?

K The landscape of tractable and PC-tractable fragments of the BA is still incomplete. Towards its completion, it is important to establish which tractable (resp., PC-tractable) fragment is also maximally so. In [ 6 ], and earlier in [ 13 ], the fundamental tool to check the (non) maximality of a certain tractable fragment in the linear case is the introduction of the so-called corner sets, i.e. small sets of relations which allow the construction of polynomial reduction of some NP-complete problem (usually 3-SAT and 3-COLOR). The list of corner sets emerge as a consequence of the systematic analysis of the fragments of the IA. So, in the linear case, it holds that, given a certain tractable fragment S, it the case that S is maximal w.r.t. tractability if and only if every possible extension, that is, every set of the type (S [ fRg) with R 2= S, contains at least one of the corner sets. The complete list of corner sets [ 6 ] is:

N1 = ffb; di; f i; m; og; fb; d; m; o; sg; fd; di; f i; oi; sigg N2 = ffb; di; f i; m; og; fb; d; m; o; sg; fdi; f i; o; oi; sigg N3 = ffb; big; fo; oigg N4 = ffb; big; fm; mi; o; oigg N5 = ffm; mig; fb; bi; f; f i; s; sigg N6 = ffb; bi; m; mig; fo; oigg

To study the maximality of tractable fragments in the branching algebra, the linear corner sets are a possible starting point. Indeed, if a fragment of the BA contains a linear corner set and the relation fe; b; bi; d; di; f; f i; m; mi; o; oi; s; sig (which we denote as l), that is, a relation that constrains two intervals to be in some linear relation, then it is certainly not tractable: the reduction that proves NP-completeness is precisely the same as in the linear case, with the addition of the constraint I l J for each pair I; J of intervals that are not explicitly constrained. Since BAHorn, BApoint and BAlin all contain l, this argument can be applied in all three subalgebras. On the other hand, the opposite does not necessarily hold: if a certain fragment of BA does not contain any corner set, then it is not necessarily tractable. Therefore, by applying the same strategy as in the linear case, two outcomes are possible: (i) if all the possible extensions of a tractable fragment S contain a linear corner set, then S is maximal w.r.t. tractability, and (ii) if there exists an extension SR (= (S [ fRg)), for some relation R that does not contain any corner set, then SR is a new candidate for being tractable | in that case, it would also be a candidate to be maximally tractable. In the latter case, the process can be recursively applied, resulting

P3 P1

P2

P4

P5 in new, bigger subalgerbas, all potentially interesting, whose tractability is an open issue. We call extension graph of a certain fragment S a directed graph G = hV; Ei that represents the set of algebras that one obtains by such a systematic search: vertexes represent algebras, and edges indicate that one set can be extended into another, and may be optionally labelled by a relation which brings such extension.

Theorem 3. The following results hold: { BAHorn is maximally ( PC-)tractable; { BApoint has the extension graph shown in Fig. 5; { BAlin has the extension graph shown in Fig. 6.

The result was obtained through computer-assisted enumeration. By computerassisted enumeration, one can see that BAHorn cannot be extended in any fragment that is not a superset of some corner set. Also one can see that the every extension of BApoint and BAlin that is not the superset of any corner set is depicted in Fig. 5 and in Fig. 6. There are precisely ve supersets of BApoint whose tractability is unknown, and nine supersets of BAlin. While in the case of BApoint such supersets form a chain w.r.t. set containment, in the case of BAlin the situation is more complex, with six supersets that form three chains, and three supersets formed by combinations of other supersets.

The maximality of both BApoint and BAlin is therefore an open issue, as so are the PC-tractability of BAlin and the (non) existence of some other tractable fragment of the BA.

One way in which the tractable fragments are exploited in the literature is to speedup the task of checking the consistency of a network (see, e.g., [ 12 ] for IA or [ 8 ] for BA). Instead of having a backtracking algorithm that assigns a basic relation to each edge in the network, the search can stop as soon as all the edges are assigned relations (possibly, non basic) that are in a fragment tractable with PC. For this task, BAlin is very promising as it is the largest tractable known fragment; if it was PC-tractable, then it could be exploited to possibly obtain L3 L2;3

L4 L2;4

L5 L4;5 L1

L2 L6 a higher speedup than that obtained using BAHorn in [ 3 ]. However, as already said, the PC-tractability of BAlin is an open issue. 5

Conclusions The branching interval algebra (BA) is the tree order generalization of Allen's (linear) interval algebra (IA). Its potential applications include planning with alternatives, automatic story-telling with alternative timelines, and checking version systems with several branches. As in the linear case, the consistency problem of Branching Algebra is NP-complete, and studying its tractable fragments is a interesting problem. In the linear case, we know every tractable fragment of the full algebra, while in the branching case the entire landscape of tractable fragments is still unknown. In this paper we considered some of the results that are known in the linear case and the branching case in the point-based setting; by combining them we were able to add two new tractable fragments (BApoint and BAlin) of the branching interval algebra to the one that was already known (BAHorn). Also, we studied their maximality; we were able to prove BAHorn is maximal w.r.t. tractability; as much as the maximality of BApoint and BAlin is concerned, however, the problem is still open, although we proved some possibly useful partial results in this sense. Finally, we considered the problem of the tractability via Path-Consistency of these fragments, and proved that BApoint, while tractable, is not PC-tractable; the PC-tractability of BAHorn was already known, and the PC-tractability of BAlin is an open issue.

This paper is a stepping stone towards the complete classi cation of the fragments of the BA, which is, obviously, the main open problem at the moment. The techniques, and the algorithms, needed to perform this classi cation for an algebra with 19 relations (much bigger than the IA, with 13 relations only) can be certainly re-used for similar studies in other algebras, such as the rectangle algebra, and similar formalism for spatial-temporal reasoning.

References

1. Allen , J.: Maintaining knowledge about temporal intervals . Communications of the ACM 26 ( 11 ), 832 { 843 ( 1983 )

2. Allen , J. , Hayes , P.J.: Short time periods . In: Proc. of IJCAI 1987: 10th International Joint Conference on Arti cial Intelligence . pp. 981 { 983 ( 1987 )

3. Bertagnon , A. , Gavanelli , M. , Passantino , A. , Sciavicco , G. , Trevisani , S.: The Horn Fragment of Branching Algebra . In: Mun~ oz- Velasco , E. , Ozaki , A. , Theobald , M. (eds.) 27th International Symposium on Temporal Representation and Reasoning , TIME 2020, September 23-25 , 2020 , Bozen-Bolzano, Italy. LIPIcs , vol. 178 , pp. 5 : 1 {5: 16 . Schloss Dagstuhl - Leibniz-Zentrum fur Informatik ( 2020 ). https://doi.org/10.4230/LIPIcs.TIME. 2020 .5

4. Broxvall , M.: The point algebra for branching time revisited . In: Proc. of KI2001: Advances in Arti cial Intelligence. Lecture Notes in Arti cial Intelligence , vol. 2174 , pp. 106 { 121 . Springer ( 2001 )

5. Condotta , J., D'Almeida , D. , Lecoutre , C. , Sa s, L.: From qualitative to discrete constraint networks . In: Proc. of KI 2006: Workshop on Qualitative Constraint Calculi . pp. 54 { 64 ( 2006 )

6. Drakengren , T. , Jonsson , P.: A complete classi cation of tractability in Allen's algebra relative to subsets of basic relations . In: Arti cial Intelligence . pp. 205 { 219 . Elsevier ( 1997 )

7. Durhan , S. , Sciavicco , G.: Allen-like theory of time for tree-like structures . Information and Computation 259 ( 3 ), 375 { 389 ( 2018 )

8. Gavanelli , M. , Passantino , A. , Sciavicco , G.: Deciding the consistency of branching time interval networks . In: Proc. of TIME 2018: 25th International Symposium on Temporal Representation and Reasoning. LIPIcs , vol. 120 , pp. 12 : 1 { 12 : 15 ( 2018 )

9. Krokhin , A. , Jeavons , P. , Jonsson , P. : Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra . Journal of the ACM 50 ( 5 ), 591 { 640 ( 2003 )

10. Ligozat , G.: A new proof of tractability for ORD-Horn relations . In: AAAI-96 Proceedings . pp. 395 { 401 ( 1996 )

11. Mackworth , A. : Consistency in networks of relations . Arti cial Intelligence 8 ( 1 ), 99 { 118 ( 1977 )

12. Nebel , B.: Solving hard qualitative temporal reasoning problems: Evaluating the e ciency of using the ORD-Horn class . Constraints 1 ( 3 ), 175 { 190 ( 1997 )

13. Nebel , B. , Burckert, H.: Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra . Journal of the ACM 42 ( 1 ), 43 { 66 ( 1995 )

14. Ragni , M. , Wol , S.: Branching Allen . In: Proc. of ISCS 2004: 4th International Conference on Spatial Cognition. Lecture Notes in Computer Science , vol. 3343 , pp. 323 { 343 . Springer ( 2004 )

15. Reich, A.: Intervals, points, and branching time . In: Proc. of TIME 1994: 9th International Symposium on Temporal Representation and Reasoning . pp. 121 { 133 . IEEE ( 1994 )

16. van Beek, P. , Cohen , R. : Exact and approximate reasoning about temporal relations . Computational Intelligence 6 , 132 { 144 ( 1990 )

17. Vilain , M.B. , Kautz , H.: Constraint propagation algorithms for temporal reasoning . In: Proc. of AAAI 1986: 5th National Conference on Arti cial Intelligence . pp. 377 { 382 ( 1986 )