> rtqxܥhc e|8MxY::FFGGG$4G4G4G4G4G4GG@4GKGRNKNKNKNKKKKKKKKKKKLXLaKGK}
NKrKKKKKFFNKGKKKKF,NKGNKKmH="4G4GFFFFKKKKProbabilistic Temporal Interval Networks: Extended Version
Vladimir RyabovAndr TrudelUniversity of Jyvskyl
P.O. Box 35
Jyvskyl, FIN-40351, Finland
vlad@it.jyu.fiJodrey School of Computer Science
Acadia University
Wolfville, Nova Scotia, B4P 2R6, Canada
Andre.Trudel@AcadiaU.ca
Track 1: Temporal representation and reasoning in AI
Topics: temporal constraint reasoning, uncertainty in temporal knowledge
Abstract
A Probabilistic Temporal Interval Network is a constraint satisfaction problem where the nodes are temporal intervals and the edges are uncertain interval relations. We attach a probability to each of Allens basic interval relations. An uncertain relation between two temporal intervals is represented as a disjunction of Allens probabilistic basic relations. Using the operations of inversion, composition, and addition, defined for this probabilistic representation, we propose a path consistency algorithm and an approach to finding consistent scenarios using a backtracking algorithm. We also discuss heuristic methods for optimizing the performance of the backtracking algorithm. Finally, we show how to estimate the probability of a consistent scenario.
1. Introduction
A Constraint Satisfaction Problem (CSP) [11] can be represented by a finite set of variables (or nodes), their associated domains, and a set of constraints on these variables. The domain of a variable is the set over which the variable takes its values. Each element of the domain is called a label. Solving a CSP consists of finding assignments of labels to variables that satisfy the given constraints.
A Probabilistic Temporal Interval (PTI) network is a special type of CSP. A PTI network consists of a set of nodes (temporal intervals) and the edges represent the uncertain relations between them. An uncertain relation between two intervals is a set of Allens [1] basic relations, where a probability is attached to each basic relation. We re-define three reasoning operations: inversion, composition, and addition. A standard path-consistency algorithm is modified to deal with uncertain interval relations. We also propose an approach to finding consistent scenarios in PTI networks using a backtracking algorithm and we present heuristic methods for optimizing the algorithms performance. We show how to compute the probability of a consistent scenario using the probabilities associated with Allens basic relations on each edge.
Our path-consistency algorithm, backtracking algorithm, and ordering heuristics are partially based on van Beek and Manchaks work [3]. Our probabilistic representation is more general than their standard temporal representation. Our paper can be viewed as an extension of the work presented in [3].
Other formalisms for handling uncertainty, such as possibility theory, have been applied to temporal representation and reasoning. A fuzzy extension of Allens Interval Algebra was proposed in [2]. In that paper, a possibility theory was utilized to model uncertain temporal relations by assigning a preference degree to every basic Allens relation within an uncertain interval relation. Three reasoning operations, namely, inverse, conjunctive combination (analogous to our operation of addition), and composition were defined for that representation. A path-consistency algorithm for interval-based networks with fuzzy temporal constraints has been proposed, and a tractable sub-algebra has been identified.
In addition to the above, other related work is: the paper of Ladkin and Reinefeld [7] describes algebraic methods for interval constraint problems; a theoretical evaluation of selected backtracking algorithm was presented in [5]; a description of backtracking algorithms for disjunctions of temporal constraints in [12], and analysis of symbolic and numeric constraint satisfaction techniques for temporal reasoning [8].
In Section 2 we define uncertain interval relations and present reasoning operations. In Section 3 we define PTI networks, give an example of such a network, and describe the types of input that are accepted by the algorithms presented in this paper. In Section 4 we define a path consistency algorithm. Further, in Section 5 we show how to find consistent scenarios within a network using a backtracking algorithm. Heuristic methods for speeding up the backtracking performance are discussed in Section 6. Later, in Section 7 we estimate the probabilities of consistent scenarios. Finally, in Section 8 we present our conclusions and point out directions for further research.
2. Uncertain Interval Relations
In this section, we define uncertain interval relations and the reasoning operations inversion, composition, and addition.
We denote temporal intervals with capital non-bold letters, i.e. A, B. The relation between two intervals is denoted with a subscripted capital letter R. For example, the relation between intervals A and B is written as RA,B. There are thirteen basic mutually exclusive relations [1] that can hold between two temporal intervals. The set of these relations is denoted as X={eq,b,bi,d,di,o,oi,m,mi,s,si,f,fi}. We refer to an element of this set as ((X. An uncertain relation between two temporal intervals is represented as a set of probabilities of all the basic relations that can hold between them. The probability of a basic temporal relation between two intervals is further denoted using the letter e with a superscript indicating the basic relation and possibly a subscript indicating the intervals, e.g., EMBED Equation.3. The uncertain relation between intervals A and B is written as RA,B={e((((X}. The set RA,B has a cardinality of 13, one entry for each of Allens basic temporal relations. The probabilities in RA,B sum to 1. For example, RA,B={eeq=0.5, eb=0.2,ebi=0.3} means that the relationship between intervals A and B is eq ( b ( bi and, eq is the sole relationship between intervals A and B with probability 0.5. Similarly for b with probability 0.2 and bi with 0.3. Note that in this and all subsequent examples, zero entries are omitted. For example, m has a probability of 0 of being the relationship between A and B.
The operation of inversion (~) derives the relation RB,A when the relation RA,B is defined, and RB,A =EMBED Equation.3. Given the probability values EMBED Equation.3, the probability values EMBED Equation.3 are calculated according to the inversion table for Allens interval relations [1], i.e. EMBED Equation.3=EMBED Equation.3. For example, the inverted relation for
RA,B={eeq=0.05, eb=0.2, ebi=0.1, ed=0.35, edi=0.01, eo=0.2, eoi=0.09}
is
RB,A={eeq=0.05, eb=0.1, ebi=0.2, ed=0.01, edi=0.35, eo=0.09, eoi=0.2}.
The operation of composition (symbol 196 \f "Symbol" \s 11) derives the relation RA,C, when the relations RA,B and RB,C are defined, and RA,C=RA,B(RB,C. We assume that the probability values EMBED Equation.3 and EMBED Equation.3, where ((X, are known. The probability values EMBED Equation.3 are calculated according to the algorithm for composition (Figure 1) presented in [10].
1. EMBED Equation.3=0, where ((X;
2. for i=1 to 13 do
3. for j=1 to 13 do
4. begin
5. X(={(1,(1,,(m}, where X( is a set of all Allens relations
which are possible between A and C when EMBED Equation.3 and EMBED Equation.3 are combined;
6. for k=1 to m do
7. EMBED Equation.3=EMBED Equation.3+EMBED Equation.3EMBED Equation.3 //(k(X(; (i,(j (X;
8. end.
Figure 1. Algorithm for the composition operation [10]
The algorithm in Figure 1 considers all possible combinations of the probability values from RA,B and RB,C. For example, the result of the standard non-probabilistic composition of b and d is {b,d,o,m,s}. We need to distribute the probability EMBED Equation.3 between the values from the set {b,d,o,m,s}. For example, the composition of the two uncertain relations RA,B={eeq=0.3,eb=0.7} and RB,C={ed=0.5,eo=0.5} results in RA,C={eb=0.42,ed=0.22, eo=0.22, em=0.07, es=0.07}.
The operation of addition (symbol 197 \f "Symbol" \s 12) combines the relations EMBED Equation.3 and EMBED Equation.3 into a single relation RA,B. In this case, we write RA,B = EMBED Equation.3symbol 197 \f "Symbol" \s 12EMBED Equation.3. We use the algorithm from [10] for performing addition (Figure 2).
1. EMBED Equation.3=0, where ((X;
2. for i=1 to 13 do
3. EMBED Equation.3, //where EMBED Equation.3 from EMBED Equation.3 and EMBED Equation.3 from EMBED Equation.3;
4. for i=1 to 13 do
5. EMBED Equation.3.
Figure 2. Algorithm for the addition operation [10]
For example, the addition of two uncertain relations EMBED Equation.3={eeq=0.3,eb=0.5,eo=0.2} and EMBED Equation.3={eeq=0.05, ed=0.2, eo=0.75} is RA,B={eeq=0.214, eo=0.786}.
3. PTI Networks
A PTI network N is a directed graph where the nodes represent intervals and the arcs represent the uncertain temporal relations between these intervals. We represent such a graph as a set of n variables (intervals) V={v1,v2,,vn} and the relations between them as EMBED Equation.3={e((((X}, where vi,vj(V. The set of all uncertain temporal relations for the network N is denoted as (.
For example, the PTI network N shown in Figure 3 has 4 intervals A, B, C, D, and 5 uncertain relations between them RA,B={eeq=0.3,eb=0.7}, RB,C={eb=0.5,ebi=0.5}, RA,C={eb=1}, RB,D={eb=1}, and RC,D={eb=0.2,ebi=0.8}. Note that there is no edge between A and D. In this case, we assume it is a totally uncertain relation with all possible entries having equal probability values.
Figure 3. The PTI network N
In later sections, we define a path consistency and a backtracking algorithm for PTI networks. The algorithms accept three types of input:
A PTI network: The interval relations within this network include probabilistic values for Allens relations (e.g., the network shown in Figure 3).
A standard qualitative temporal CSP: In this case, the network does not include probability values and needs to be converted to a PTI network. We assume that the Allen relations contained in the label on an edge are equally likely. For example, if we have the label {eq,b} on an edge, we convert this to a PTI with {eeq=0.5,eb=0.5}. In general, each of the n entries in a label are assigned the probability 1/n.
3) A qualitative temporal CSP with preferences: Assume we have a standard qualitative temporal CSP. In addition, we are given relation preferences for each edge. For example, if we have the label {b,m,o} and we also know that b is preferred over m and o. There is no preference between m and o. The PTI network label becomes {eb=2/(2+1+1), em=eo=1/(2+1+1)}, i.e. {eb=0.5, em=0.25, eo=0.25}. In general, we create a partial order and rank each element in the order. The smallest ranked element is assigned a rank of 1. The probability assigned to an element is its rank over the sum of the ranks.
4. Path Consistency Algorithm
The path consistency algorithm (PC-algorithm) can be used to test an Interval Algebra (IA) network for consistency as was proposed by Allen [1], as well as a part of the backtracking search algorithm ([7] and [3]). In this section we present a PC-algorithm (shown in Figure 4) adapted to PTI networks. Note that our PC-algorithm is almost identical to the one in [3]. We use probabilistic versions of inversion, addition, composition, and the test conditions in lines 7 and 14 in Figure 4.
As the name implies, the PC-algorithm repeatedly checks for 3-consistency for every possible three nodes i, j, and k. The values of the uncertain relations Ri,j and Rj,k potentially constrain the value of the relation Ri,k. Using the operations of composition and addition we compute a possible value for the relation Ri,k using the triangle t=Ri,k((Ri,j(Rjk). Analogous to standard qualitative temporal CSPs, Ri,k and t have the following properties:
If e( is zero in Ri,k then the same entry is also zero in t.
If e( is non-zero in t then the same entry is also non-zero in Ri,k.
From the above, t has the same number or fewer zero entries as Ri,k. Also, all non-zero entries in t are also non-zero in Ri,k. If the derived relation t is more certain than the initial value of Rik, we update Rik with t. The derived relation is more certain than the initial one if:
It has more zero entries (probability values for the basic relations), or
The relations are not equal and have the same number of zero entries, but the initial relation is lexicographically smaller than the derived one, when the entries are ordered in descending order. To illustrate the latter case, let us consider an example: Ri,k = {eeq=0.2,eb=0.5,em=0.3} and t = {eeq=0.25,eb=0.25,em=0.5}. Ordering the entries in descending order we obtain Ri,k={eb=0.5,em=0.3,eeq=0.2} and t={em=0.5,eeq=0.25, eb=0.25}. The maximum entries are equal to 0.5; therefore we need to compare the next ones. The second entry of 0.3 for Ri,k is bigger than 0.25 for t, so we conclude that the relation Ri,k is more certain than t. In this case, Ri,k would not be updated. Let us underline, that such a lexicographical comparison is utilized only when the two relations are not equal and have the same number of zero entries. The described procedure is also performed to tighten the relation Rj,k in a similar way. The motivation for the lexicographic comparison is to favor relations with comparatively larger probabilities.
1. L ( {(i,j) ( 1 ( i < j ( n}
2. while (L ( {(}) do
3. select and delete an (i,j) from L
4. for k = 1 to n do
5. if (k ( i) AND (k ( j) do
6. t = Ri,k ( (Ri,j ( Rjk);
7. if (t has more zero entries than Ri,k) OR ((t ( Ri,k) AND (t has the same number of zero entries as Ri,k)8. AND (Ri,k is lexicographically smaller than t, when entries in Ri,k and t are ordered in descending order))
9. then do
10. Ri,k = t;
11. Rk,i = Inverse (t);
12. L = L ( {(i,k)};
13. t = Rk,j ( (Rk,i ( Ri,j);
14. if (t has more zero entries than Rk,j) OR ((t ( Rk,j) AND (t has the same number of zero entries as Rk,j)15. AND (Rk,j is lexicographically smaller than t, when entries in Rk,j and t are ordered in descending order))16. then do
17. Rk,j = t;
18. Rj,k = Inverse (t);
19. L = L ( {(k,j)};
Figure 4. Path-consistency algorithm for PTI networks
The computational complexity of the path consistency algorithm is O(n3) when counting composition operations as taking unit time. As it was pointed out by many authors (e.g., [3] and [7]), for an implementation of the path consistency algorithm to be efficient, the reasoning operations used must be efficient. Particularly, the time performance of the algorithm in Figure 4 strongly depends on the method of calculating the composition of relations.
5. Finding Consistent Scenarios
A backtracking algorithm can be used to find a consistent scenario of an interval network, as was initially proposed by Allen [1]. Later, van Beek [3] presented methods for speeding up the performance of backtracking algorithms. Particularly, he proposed an alternative formulation of the problem and also designed heuristics for ordering the instantiation of the relations. In this section we propose a backtracking algorithm for finding a consistent scenario in PTI networks. We base our algorithm on the formulation of the backtracking algorithm proposed in [6] and [7].
Initially, we preprocess the whole network using the probabilistic PC-algorithm presented in Figure 4. Preprocessing using the PC-algorithm was found to be effective in [7]. A successful termination of the PC-algorithm is a necessary condition for consistency of the network. Sometimes, the PC-algorithm can determine that the network is inconsistent. If the PC-algorithm returns a reduced network, then only relations that cannot be part of a consistent scenario have been deleted.
Our backtracking algorithm is shown in Figure 5, together with the auxiliary procedure Next_edge in Figure 6. The backtracking algorithm in Figure 5 has the following properties: dynamic ordering of the edges, chronological backtracking, and the use of the PC-algorithm (Figure 4) for forward checking. Initially, the procedure Next_edge (Figure 6) is called to determine the starting edge. During the first iteration of the cycle (lines 3-8 in Figure 5) we select the entry in Ri,j having the largest probability value. If we backtrack to this point, we try the second largest value and so on until a consistent scenario is found or all the values are tried. When an entry rk is selected we label the relation Ri,j as follows. The probability for rk is assigned the value 1, and the rest of the entries within Ri,j are assigned zeros (line 4). Later, when a consistent scenario is found we replace the 1 entries with their original values in order to estimate the probability of the scenario. The intent of using the greedy approach of trying the entries in the order of descending probability value is to hopefully derive more probable scenarios first, since the most probable labels are checked first. An approach for estimating the probability of a consistent scenario is discussed in the next section.
1. function Backtracking (var R: relational matrix, i, j: Integer): Boolean;
2. R( = R;
for (each rk ( Ri,j selected in the order of decreasing probability value) do
4. Within Ri,j : Pr(rk)=1, other entries are zeros
5. if R is path consistent as determined by the PC- algorithm then6. Next_edge (R, next_i, next_j, last_edge);
7. if last_edge or Backtracking (R, next_i, next_j) then return True;
8. R = R(;
9. return False;
Figure 5. Backtracking algorithm for PTI networks
Line 5 of Figure 5 uses the PC-algorithm to determine if R is consistent. If it terminates successfully, we continue with the next edge (line 6), otherwise we backtrack to the last labeling. The next edge is selected using the procedure Next_edge (Figure 6) in the following way. Each entry in R is a vector. We ignore the vectors containing a 1 entry. Of the remaining vectors we select the vector Ri,j, containing the largest individual entry. If such a vector is not found, the last edge to be checked was reached and the backtracking algorithm should stop at this iteration.
1. procedure Next_edge (R: relational matrix, var next_i,next_j:Integer; var last_edge:Boolean)
2. // Each entry in R is a vector. Ignore vectors that contain a 1 entry.
3. // Of the remaining vectors, let Ri,j be the vector containing the largest individual entry.
4. if such an Ri,j exists then
5. next_i = i;
6. next_j = j;
7. last_edge = False;
8. else last_edge = True.
Figure 6. Procedure determining the next edge for the backtracking algorithm
With chronological backtracking, if we reach a situation where the R is inconsistent, we return to the last labeling and try a different entry for that relation. When Ri,j is the last edge considered and R was checked to be path consistent the function returns True (line 7 in Figure 5) meaning that a consistent scenario has been successfully found. Otherwise, when all possible entries for all the edges have been tried and no consistent scenario was found the function returns False (line 9 in Figure 5).
It is well known, that finding a consistent scenario for interval networks is NP-complete as was shown, for example, by Vilain and Kautz [13]. Even though backtracking algorithms can take an exponential amount of time to complete in the worst case, many authors point out (i.e., [3]) that these algorithms can work well in practice. A number of methods for speeding up execution of backtracking and path consistency algorithms were proposed, for example, in [3], [7], and [5].
6. Heuristic Methods
The order in which the uncertain relations are considered and labeled during backtracking greatly affects the performance of the algorithm. A number of heuristics were proposed in [3], [4], and [9]. These heuristics can be divided into two groups: 1) heuristics intended for labeling the uncertain relations (also called value ordering heuristics); 2) heuristics intended for selecting the next relation to be considered (variable ordering). There are three possible approaches to finding a consistent scenario:
The most probable solution first. The goal is to find the most probable scenario first, the second probable scenario next, and so on in descending order of scenario probabilities. This goal is applied to PTI networks considered in this paper.
The fastest solution. The goal is to speed up the performance of the backtracking algorithm in terms of time costs, i.e. to minimize the time of finding the first solution.
A reasonably probable solution in a reasonable amount of time. This goal is a combination of the two above and it is to find a reasonably probable solution (not necessarily the best one, but at the same time not the worst one) in a reasonable amount of time (also not necessarily the minimum, but not the worst).
We present several heuristics based on the approaches above. The backtracking algorithm uses the following approach for value ordering. We select the entries within an uncertain relation starting with the maximum probability value, label the relation with this entry, and proceed with the algorithm. If we backtrack to this point, we need to select the second largest entry, and so on. A similar approach was used for variable ordering. The next edge to be considered during backtracking is selected among all the yet unconsidered vectors containing the largest individual non-1 entry. The following example illustrates how value ordering is currently implemented.
Example 1. Let the relation Ri,j be defined as {eeq=0.15, eb=0.3, eoi=0.2, es=0.35}. Based on the approach of selecting the entries in the order of decreasing probability values, the relation Ri,j will be labeled during backtracking in the sequence: s, b, oi, and eq.
Van Beek and Manchak [3] present three heuristics for ordering variables. One of them, weight heuristics, is based on using the weights of interval relations. According to this heuristic, Allens relations o, oi, and d have a weight value equal to 4. Relations b, bi, and di have a weight value equal to 3. Relations m, mi, s, si, f, and fi have a weight value equal to 2. And, finally, the relation eq has a weight value equal to 1. This heuristic takes into account how much the label on the edge restricts the labels on other edges. The values of the weights were obtained in the following way. Each basic relation was composed with every possible label and the cardinalities of the results were summed up. Later, the obtained cardinalities were suitably scaled and the final values of the weights were derived. According to this heuristic, we can estimate the weight of any uncertain relation by summing up the weights of the entries included. For instance, for the relation Ri,j from Example 1 above the weight equals 1+3+4+2=10. This heuristic can be used for value ordering as shown in the example below.
Example 2. Let Ri,j be defined as in Example 1. Based on the decreasing weight values of the separate entries, we could try the following sequence for Ri,j during backtracking: oi, b, s and eq.
We propose a modification for the weight heuristic adapted for probabilistic representation of uncertain temporal relations. Instead of only considering weights, we calculate the probabilistic weight of an entry as a product of the probability value and weight:
EMBED Equation.3,( SEQ eq \n 1)where ((X, e((Ri,j, and w( is the weight value assigned to (. The maximum value of ( is 4, which is the product of the maximum value of w (equal to 4 for o, oi, and d) and e equal to 1. The minimum value of ( is 0 for any zero entry in Ri,j.
Example 3. Let Ri,j be defined as in Example 1. According to formula (1), the probabilistic weight values of the entries in Ri,j are: (eq=1(0.15=0.15, (b=3(0.3=0.9, (oi=4(0.2=0.8, and (s=2(0.35=0.7. Based on these values, we try the following sequence of labels for Ri,j during backtracking: b, oi, s and eq.
For variable ordering using this heuristic, we follow the approach discussed above and estimate the weight of the relation as a sum of the probabilistic weights of the entries. Considering the variables with the highest probabilistic weight values first is a tradeoff between testing the most probable variables and trying to solve the most constrained part of the network first. This heuristic may be practical for situations when we need to find a reasonably probable solution in a reasonable time.
7. Probability of a Consistent Scenario
In this section we present one approach for estimating the probability of a consistent scenario in a PTI network. Assume the consistent scenario was found using the backtracking algorithm presented earlier in this paper.
For each PTI network we have a set of interval relations R={R1,R2,,Rn}, where n is the total number of edges in the network. We define a set EMBED Equation.3 of thirteen events for the relation R1 where, for instance, E_eq is the event The relation R1 is equals. Similarly we define EMBED Equation.3,, and EMBED Equation.3.
Before we can define the formula for the probability of a consistent scenario we need to make the following assumption: EMBED Equation.3are jointly independent. This assumption means that if we select an event from each set, then all the selected events are jointly independent. It also means that the particular value of any uncertain relation within the network does not depend on any other relation value in the network. Assuming this, the probability of a scenario is:
EMBED Equation.3, where EMBED Equation.3.(2)Formula (2) suggests finding the probability of a scenario as a product of the probabilities of all the events that are included in the scenario, since these events are assumed to be independent. In this case, the probabilities of these events are the corresponding entries within the uncertain relations from the set R.
We present an example which uses the PTI network N in Figure 3. Using the backtracking algorithm, we find three consistent scenarios S1, S2, and S3 (Table 1).
S1S2S3RA,BbeqBRB,CbbBiRA,CbbBRB,DbbBRC,DbibiBP(S)0.280.120.07Table 1. Consistent scenarios for the network N and their probabilities
Using formula (2) and the probability values for the entries we estimate the probabilities of these three scenarios as P(S1)=0.28, P(S2)=0.12, and P(S3)=0.02. For example, the probability of scenario S1 is the product of EMBED Equation.3=0.7, EMBED Equation.3=0.5, EMBED Equation.3=1, EMBED Equation.3=1, and EMBED Equation.3=0.8. Note that the values in the last row of Table 1 do not sum to 1. We do purposely do not normalize the results because in practice, we do not have access to all the consistent scenarios.
Note that the example from Table 1 presents an alternative method for solving PTI networks. First remove the probabilities from the edges in the network. We now have a standard temporal CSP problem. Solve it using traditional methods and compute the solutions probability. Continue generating solutions until all are generated, or a sufficiently probable one is obtained. Since we are dealing with an NP-complete problem, this may not be feasible for large real world problems. It is hoped that the algorithms presented in this paper generate an optimal or near optimal solution initially. Future work will compare both approaches experimentally.
8. Conclusions
We defined a PTI network whose nodes represent temporal intervals and edges represent the uncertain relations between them. We then proposed a PTI path consistency algorithm, and an approach to finding a consistent scenario using backtracking. We also proposed heuristic methods for backtracking and an approach to compute probabilities of consistent scenarios.
Our results are theoretical, and experiments will be carried out in the near future. After implementing the algorithms, we will test them on PTI networks. The relative speed and the order that the scenarios are generated will be studied.
One limitation of our work is the independence assumption when defining the formula for the probability of a consistent scenario, which may not hold in practical situations. If it is known that some of the values are dependent, then a more sophisticated approach taking into account these dependencies should be developed.
References
1. Allen, J.: Maintaining Knowledge about Temporal Intervals. Communications of the ACM 26(11) (1983) 832-843
2. Badaloni, S., Giacomin, M.: A Fuzzy Extension of Allens Interval Algebra, In Proceedings of the 6-th Congress of the Italian Association for AI, Lecture Notes in Artificial Intelligence 1792 (2000) 155-165
3. van Beek, P., Manchak, D.: The Design and Experimental Analysis of Algorithms for Temporal Reasoning, Journal of Artificial Intelligence Research 4 (1996) 1-18
4. Dechter, R., Pearl, J.: Network-Based Heuristics for Constraint Satisfaction Problems. Artificial Intelligence 34(1) (1987) 1-38
5. Kondrack, G., van Beek, P.: A Theoretical Evaluation of Selected Backtracking Algorithms, Artificial Intelligence 89 (1997) 365-387
6. Ladkin, P., Reinefeld, A.: Efficient Solution of Qualitative Interval Constraint Problems, Artificial Intelligence 57 (1992) 105-124
7. Ladkin, P., Reinefeld, A.: Fast Algebraic Methods for Interval Constraint Problems, Annals of Mathematics and Artificial Intelligence 19(3-4) (1997) 383-411
8. Mouhoub, M., Charpillet, F., Haton, J.-P.: Experimental Analysis of Numeric and Symbolic Constraint Satisfaction Techniques for Temporal Reasoning, Constraints: An International Journal 3(2-3) (1998) 151-164
9. Nudel, B.: Consistent-Labeling Problems and their Algorithms: Expected Complexities and Theory-Based Heuristics. Artificial Intelligence 21 (1983) 135-178
10. Ryabov, V.: Handling Uncertain Interval Relations, In Proceedings of the 2-nd IASTED International Conference on AI and Applications, ACTA Press (2002) 291-296
11. Schwalb, E., Vila, L.: Temporal Constraints: A Survey, Constraints: An International Journal 3(2-3) (1998) 129-149
12. Stergiou, K., Koubarakis, M.: Backtracking Algorithms for Disjunctions of Temporal Constraints, Artificial Intelligence 120 (2000) 81-117
13. Vilain, N., Kautz, H.: Constraint Propagation Algorithms for Temporal Reasoning. In Proceedings of the Fifth National Conference of the American Association for Artificial Intelligence, AAAI Press (1986) 377-382
A
B
C
D
{eeq=0.3,eb=0.7}
{eb=0.5,ebi=0.5}
{eb=0.2,ebi=0.8}
{eb=1}
{eb=1}
!/=888$@/=888uesT:pp .&`7&MathTypep Times New RomanSw\w0-2
eq2
,q Times New RomanSw\w0-2
Bq2
AqTimes New RomanSw\w0-2
.eq
&
"System
0-:pHH ) . &H&MathTypep Times New RomanSw\w0-2
ZBy2
|Ay Times New RomanSw\w0-2
,yTimes New RomanSw\w0-2
^~yTimes New RomanSw\w0-2
:Ry
&
"System
0-:pp ) .&`7&MathTypep Symbolw@
Sw\w0-2
cy Times New RomanSw\w0-2
By2
Ay Times New RomanSw\w0-2
,yTimes New RomanSw\w0-2
.ey
&
"System
0-: ) .&`7&MathTypep Symbolw@e
$LSwUSw0-2
cy Times New RomanLSwUSw0-2
Ay2
By Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-T: .&`7&MathTypep Times New RomanLSwUSw0-2
oi2
,i Times New RomanLSwUSw0-2
Ai2
BiTimes New RomanLSwUSw0-2
.ei
&
"System
0-T:pf .&`7&MathTypep Times New RomanLSwUSw0-2
oy2
,y Times New RomanLSwUSw0-2
By2
AyTimes New RomanLSwUSw0-2
.ey
&
"System
0-D:| .`&@&MathType` Symbolw@
6Sw\w0-2
cy Times New RomanSw\w0-2
By2
A,Times New RomanSw\w0-2
.e,
&
"System
0-D:| .`&@&MathType` Symbolw@
hSw\w0-2
cy Times New RomanSw\w0-2
Cy2
B,Times New RomanSw\w0-2
.e,
&
"System
0-: ) .&`7&MathTypep Symbolw@
hLSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-: ) .&7&MathTypep Symbolw@
LSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-: U .&`;&MathTypep`Times New RomanLSwUSw0-2
(miyTimes New RomanLSwUSw0-2
.ey Symbolw@
>LSwUSw0-2
cy Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,y
&
"System
0-: U .&^&MathTypep`Times New RomanLSwUSw0-2
%zjyTimes New RomanLSwUSw0-2
.ey Symbolw@
LSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
By Times New RomanLSwUSw0-2
,y
&
"System
0-@: .&`;&MathTypep`Times New RomanLSwUSw0-2
(kyTimes New RomanLSwUSw0-2
.ey`Times New RomanLSwUSw0-2
(r y Times New RomanLSwUSw0-2
Cy2
Ay Symbolw@
"LSwUSw0-2
cy Times New RomanLSwUSw0-2
,y
&
"System
0-@: .&`;&MathTypep`Times New RomanLSwUSw0-2
(kyTimes New RomanLSwUSw0-2
.ey`Times New RomanLSwUSw0-2
(r y Times New RomanLSwUSw0-2
Cy2
Ay Symbolw@x
LSwUSw0-2
cy Times New RomanLSwUSw0-2
,y
&
"System
0-|:Fl .@&&MathType-@`Times New RomanLSwUSw0-2
iyTimes New RomanLSwUSw0-2
`ey Symbolw@
LSwUSw0-2
|cy Times New RomanLSwUSw0-2
oBy2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
Zmy2
r1y
&
"System
0-: U .&^&MathTypep`Times New RomanLSwUSw0-2
%zjyTimes New RomanLSwUSw0-2
.ey Symbolw@
LSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
By Times New RomanLSwUSw0-2
,y
&
"System
0-: ff - .&7&MathTypep Times New RomanLSwUSw0-2
1dy2
,y2
by2
,y Times New RomanLSwUSw0-2
Cy2
;By2
By2
AyTimes New RomanLSwUSw0-2
rey2
.ey
&
"System
0-H:O4@ .1&&MathType` Times New RomanN-2
%B2
GATimes New RomanN-2
@;R Times New RomanN-2
,Symbol-2
-3
&
"System-X:O4@ .1&&MathType` Times New Roman5-2
%B2
GATimes New Roman5-2
@;R Times New Roman5-2
,Symbol-2
-[2
-3
&
"System-H:O4@ .1&&MathType` Times New Roman=-2
%B2
GATimes New Roman=-2
@;R Times New Roman=-2
,Symbol-2
-3
&
"System-X:O4@ .1&&MathType` Times New Roman5-2
%B2
GATimes New Roman5-2
@;R Times New Roman5-2
,Symbol-2
-[2
-3
&
"System-: ) .&`7&MathTypep Symbolw@
4LSwUSw0-2
cy Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-\:= .
&`
u&MathType-``L
`Times New RomanLSwUSw0-2
x iy2
xiy2
.iy2
.wiy2
HpiyTimes New RomanLSwUSw0-2
ey2
$ey2
ey2
ey2
.ey Symbolw@
LSwUSw0-2
@ cy2
@=cy2
hcy2
cy2
cySymbolw@
sLSwUSw0-2
y2
y2
+y2
y2
y2
y2
y2
=y Times New RomanLSwUSw0-2
P} By2
PAy2
PBy2
PAy2
By2
Ay2
By2
Ay2
By2
Ay Times New RomanLSwUSw0-2
P8 ,y2
P,y2
,y2
=,y2
,y
&
"System
0-@: .&`;&MathTypep`Times New RomanLSwUSw0-2
(iyTimes New RomanLSwUSw0-2
.ey Symbolw@
]LSwUSw0-2
GcySymbolw@w
ULSwUSw0-2
y Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,y
&
"System
0-<:O4@ .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-2
@;R Times New Roman-2
,Symbol-2
-3
&
"System-P: .&`;&MathTypep`Times New RomanLSwUSw0-2
(iyTimes New RomanLSwUSw0-2
.ey Symbolw@
LSwUSw0-2
wcySymbolw@
LSwUSw0-2
y2
y Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,y
&
"System
0-L:O4@ .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-2
@;R Times New Roman-2
,Symbol-2
-[2
-3
&
"System-: zx .1&&MathType "-`=`~Symbol-2
C\ Symbol-2
Y2
YVc2
>c2
c2
cSymbol-2
= Times New Roman-2
YVX2
B2
A2
B2
ATimes New Roman-2
%e2
%e2
.e`Times New Roman-2
:di2
Hmi Times New Roman-2
JB2
JA,2
,2
,
&
"System-H:O4@ .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-2
@;R Times New Roman-2
,Symbol-2
-3
&
"System-X:O4@ .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-2
@;R Times New Roman-2
,Symbol-2
-[2
-3
&
"System-:0R\ 1 .&@&&MathType`Times New RomanSw\w0-2
jy2
iyTimes New RomanSw\w0-2
:Ry Times New RomanSw\w0-2
xvy2
gvy Times New RomanSw\w0-2
2,y
&
"System
0-:4@ A . &&MathType0 Symbolw@T
Sw\w0-2
_cy2
cy2
[cySymbolw@f
Sw\w0-2
y2
`=yTimes New RomanSw\w0-2
ey2
wyTimes New RomanSw\w0-2
.y
&
"System
0-:Rc
|* .`&`&MathTypepSymbolw@
)Sw\w0-2
~{ySymbolw@
USw\w0-2
~}yTimes New RomanSw\w0- 2
H_fie2
Ef2
_b,...,2
JEb 2
Neq,.2
_E_2
:E_`Times New RomanSw\w0-2
1_ Times New RomanSw\w0-2
@R_Symbolw@
WSw\w0-2
=_
&
"System
0-w@4:|>4 .`&`&MathTypep`Times New RomanSw\w0-2
2y Times New RomanSw\w0-2
ARyTimes New RomanSw\w0-2
:Ey
&
"System
0-4:|pf .`&`&MathTypep`Times New RomanSw\w0-2
ny Times New RomanSw\w0-2
ARyTimes New RomanSw\w0-2
:Ey
&
"System
0-:$|\ .`&`&MathTypep`Times New RomanSw\w0-2
ny2
2y2
Y1y Times New RomanSw\w0-2
$Ry2
Ry2
RyTimes New RomanSw\w0-2
$Ey2
Q y 2
0ande
2
.,...,2
E.2
,.2
E.Symbolw@
9Sw\w0-2
.2
".2
.2
]".2
k.2
.".Times New RomanSw\w0-2
E.2
kE.2
<E.
&
"System
0-2
:zz Q .@
&
&MathTypeSymbolw@
Sw\w0-2
~(ySymbolw@
Sw\w0-2
~)y
!"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopyswvz{|}~Root Entry F Ns="u@WordDocument8MObjectPool _=" Ns="_1143454633F="="Ole
CompObjfObjInfoOlePres0002
!$%&'()*+,.1456789:;<>ADEFGHIJKMPSTUVWXYZ\_adefghijkmpruvwxyz{|~
FMicrosoft Equation 3.0DS EquationEquation.39q
.&`7&MathTypep Times New RomanSw\w0-2
eq2
,q Times New RomanSw\w0-2
Bq2
AqTimes New RomanSw\w0-2
.eq
&
"System
0-]+ a4G
eA,BeqEquation Native
G_1143454634F="="Ole
CompObj
f#
Symbolw@
Sw\w0-2
~:(ySymbolw@
Sw\w0-2
~%
)ySymbolw@
Sw\w0-2
y Symbolw@
Sw\w0-2
p=ySymbolw@
Sw\w0-2
=y Times New RomanSw\w0-2
wny2
1y2
(iy2
iyTimes New RomanSw\w0-2
Pr2
Sr2
:PrTimes New RomanSw\w0-2
Er
&
"System
0-:[| 1 .``& &MathTypep`Times New RomanSw\w0-2
iy Times New RomanSw\w0-2
+Ry2
:iyTimes New RomanSw\w0-2
$Ey2
:EySymbolw@
kSw\w0-2
y
&
"System
0-T: .&`7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
By2
AyTimes New RomanSw\w0-2
.ey
&
"System
0-T: .&7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
Cy2
ByTimes New RomanSw\w0-2
.ey
&
"System
0-T: .&7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
Cy2
AyTimes New RomanSw\w0-2
.ey
&
"System
0-T: .&7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
Dy2
ByTimes New RomanSw\w0-2
.ey
&
"System
0-d:
.&7&MathTypep Times New RomanSw\w0-2
uiy2
by2
,y Times New RomanSw\w0-2
Dy2
CyTimes New RomanSw\w0-2
.ey
&
"System
0-
FMicrosoft Equation 3.0DS EquationEquation.39qpR ) . &H&MathTypep Times New RomanSw\w0-2
ZBy2
|Ay Times New RomanSw\wObjInfoOlePres000zEquation Native B_1143454635F="`="0-2
,yTimes New RomanSw\w0-2
^~yTimes New RomanSw\w0-2
:Ry
&
"System
0-]&81tF
2RA,BOle
CompObj fObjInfo"OlePres000#z
FMicrosoft Equation 3.0DS EquationEquation.39qR ) .&`7&MathTypep Symbolw@
Sw\w0-2
cy Times New RomanSw\w0-2
By2
Ay Times New RomanSw\w0-2
,yTimes New RomanSw\w0-2
.ey
&
"System
0-'
eA,BEquation Native -C_1143454636 !F`="@+="Ole
/CompObj0f
FMicrosoft Equation 3.0DS EquationEquation.39qR ) .&`7&MathTypep Symbolw@e
$LSwUSw0-2
cy Times New RomanLSwUSw0-ObjInfo2OlePres0003zEquation Native =C_1143454637F@+=" ="2
Ay2
By Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-'[
eB,AOle
?CompObj@fObjInfoBOlePres000 C2
FMicrosoft Equation 3.0DS EquationEquation.39q
.&`7&MathTypep Times New RomanLSwUSw0-2
oi2
,i Times New RomanLSwUSw0-2
Ai2
BiTimes New RomanLSwUSw0-2
.ei
&
"System
0-+@
eB,Aoi
FMicrosoft Equation 3.0DS EqEquation Native LG_1143454638'#F ="$="Ole
NCompObj"%OfuationEquation.39q
.&`7&MathTypep Times New RomanLSwUSw0-2
oy2
,y Times New RomanLSwUSw0-2
By2
AyObjInfoQOlePres000$&R2Equation Native [C_1143454639)F$="7="Times New RomanLSwUSw0-2
.ey
&
"System
0-'8%
eA,BoLW TOle
]PIC
(,^LCompObj+`fObjInfob
FMicrosoft Equation 3.0DS EquationEquation.39q .`&@&MathType` Symbolw@
6Sw\w0-2
cy Times New RomanSw\w0-OlePres000*-c"Equation Native lC_1143454640G0F7="@="Ole
n2
By2
A,Times New RomanSw\w0-2
.e,
&
"System
0-'
eA,BLW TPIC
/3oLCompObj2qfObjInfosOlePres00014t"
FMicrosoft Equation 3.0DS EquationEquation.39q .`&@&MathType` Symbolw@
hSw\w0-2
cy Times New RomanSw\w0-2
Cy2
B,Times New RomanSw\w0-2
.e,
&
"System
0-'"
eB,CEquation Native }C_11434546417F@="vL="Ole
CompObj69f
FMicrosoft Equation 3.0DS EquationEquation.39qR ) .&`7&MathTypep Symbolw@
hLSwUSw0-2
cy Times New RomanLSwUSw0-ObjInfoOlePres0008:zEquation Native C_11434546425A=FvL="`?]="2
Cy2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-'X
eA,COle
CompObj<?fObjInfoOlePres000>@z
FMicrosoft Equation 3.0DS EquationEquation.39qR ) .&7&MathTypep Symbolw@
LSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-'G
eA,CEquation Native C_1143454643CF`?]="@&i="Ole
CompObjBEf
FMicrosoft Equation 3.0DS EquationEquation.39q U .&`;&MathTypep`Times New RomanLSwUSw0-2
(miyTimes New RomanLSwUSw0-ObjInfoOlePres000DFEquation Native P_1143454644;SIF@&i="
u="2
.ey Symbolw@
>LSwUSw0-2
cy Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,y
&
"System
0-4o
eA,Bi
FMicrosoft Equation 3.0DS EquationEquation.39q U .&^&MathTypep`Ole
CompObjHKfObjInfoOlePres000JLTimes New RomanLSwUSw0-2
%zjyTimes New RomanLSwUSw0-2
.ey Symbolw@
LSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
By Times New RomanLSwUSw0-2
,y
&
"System
0-4D
eB,Cj
FMicrosoft Equation 3.0DS EquationEquation.39q Equation Native P_1143454645OF
u="~="Ole
CompObjNQfObjInfoOlePres000PR*Equation Native T_1143454646MYUF~="=".&`;&MathTypep`Times New RomanLSwUSw0-2
(kyTimes New RomanLSwUSw0-2
.ey`Times New RomanLSwUSw0-2
(r y Times New RomanLSwUSw0-2
Cy2
Ay Symbolw@
"LSwUSw0-2
cy Times New RomanLSwUSw0-2
,y
&
"System
0-8o
eA,C k
FMicrosoft Equation 3.0DS EqOle
CompObjTWfObjInfoOlePres000VX*uationEquation.39q .&`;&MathTypep`Times New RomanLSwUSw0-2
(kyTimes New RomanLSwUSw0-2
.ey`Times New RomanLSwUSw0-2
(r y Times New RomanLSwUSw0-2
Cy2
Ay Symbolw@x
LSwUSw0-2
cy Times New RomanLSwUSw0-2
,y
&
"System
0-8o
eA,CEquation Native T_1143454647[F="w="Ole
CompObjZ]f k
FMicrosoft Equation 3.0DS EquationEquation.39qF> .@&&MathTypeObjInfoOlePres000\^fEquation Native a_1143454648.aFw="ԫ="-@`Times New RomanLSwUSw0-2
iyTimes New RomanLSwUSw0-2
`ey Symbolw@
LSwUSw0-2
|cy Times New RomanLSwUSw0-2
oBy2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
Zmy2
r1y
&
"System
0-Eh8
1meA,Bi
FMicrosoft Equation 3.0DS EquationEquation.39qOle
CompObj`cfObjInfoOlePres000bd
"%&'()*+,.1456789:;=@CDEFGHIJLORSTUVWXY[^abcdefghiknqrstuvwxyz{|}~ U .&^&MathTypep`Times New RomanLSwUSw0-2
%zjyTimes New RomanLSwUSw0-2
.ey Symbolw@
LSwUSw0-2
cy Times New RomanLSwUSw0-2
Cy2
By Times New RomanLSwUSw0-2
,y
&
"System
0-4D
eB,CjEquation Native
P_1143454649gFԫ="`="Ole
CompObjfif
FMicrosoft Equation 3.0DS EquationEquation.39qZ - .&7&MathTypep Times New RomanLSwUSw0-2
1dy2
,y2
by2
,y ObjInfoOlePres000hjEquation Native b_1143454650eqmF`="@?="Times New RomanLSwUSw0-2
Cy2
;By2
By2
AyTimes New RomanLSwUSw0-2
rey2
.ey
&
"System
0-FhG
eA,Bb
eB,CdOle
CompObjlo!fObjInfo#OlePres000np$&
FMicrosoft Equation 3.0DS EquationEquation.39qO4 .1&&MathType` Times New RomanN-2
%B2
GATimes New RomanN-2
@;R Times New RomanN-2
,Symbol-2
-3
&
"System-(JI
2RA,BEquation Native -D_1143454651sF@?=" ="Ole
/CompObjru0f
FMicrosoft Equation 3.0DS EquationEquation.39qO4 .1&&MathType` Times New Roman5-2
%B2
GATimes New Roman5-ObjInfo2OlePres000tv36Equation Native <D_1143454652kyF ="~="2
@;R Times New Roman5-2
,Symbol-2
-[2
-3
&
"System-(JI
2RA,BJ
FMicrosoft Equation 3.0DS EqOle
>CompObjx{?fObjInfoAOlePres000z|B&uationEquation.39qO4 .1&&MathType` Times New Roman=-2
%B2
GATimes New Roman=-2
@;R Times New Roman=-2
,Symbol-2
-3
&
"System-(JI
2RA,BJ
FMicrosoft Equation 3.0DS EquationEquation.39qEquation Native KD_1143454653F~="d="Ole
MCompObj~NfObjInfoPOlePres000Q6Equation Native ZD_1143454654}Fd="K="O4 .1&&MathType` Times New Roman5-2
%B2
GATimes New Roman5-2
@;R Times New Roman5-2
,Symbol-2
-[2
-3
&
"System-(JI
2RA,B
FMicrosoft Equation 3.0DS EquationEquation.39qOle
\CompObj]fObjInfo_OlePres000`zR ) .&`7&MathTypep Symbolw@
4LSwUSw0-2
cy Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,yTimes New RomanLSwUSw0-2
.ey
&
"System
0-'G
eA,B
FMicrosoft Equation 3.0DS EquationEquation.39qEquation Native jC_1143454655FK="Y="Ole
lCompObjmfObjInfooOlePres000pFEquation Native !_1143454656wFY="="= .
&`
u&MathType-``L
`Times New RomanLSwUSw0-2
x iy2
xiy2
.iy2
.wiy2
HpiyTimes New RomanLSwUSw0-2
ey2
$ey2
ey2
ey2
.ey Symbolw@
LSwUSw0-2
@ cy2
@=cy2
hcy2
cy2
cySymbolw@
sLSwUSw0-2
y2
y2
+y2
y2
y2
y2
y2
=y Times New RomanLSwUSw0-2
P} By2
PAy2
PBy2
PAy2
By2
Ay2
By2
Ay2
By2
Ay Times New RomanLSwUSw0-2
P8 ,y2
P,y2
,y2
=,y2
,y
&
"System
0-HD
eA,Bi
=2eA,Bi
2eA,Bi
2eA,Bi
+2eA,Bi
FMicrosoft Equation 3.0DS EquationEquation.39q Ole
CompObjfObjInfoOlePres000*.&`;&MathTypep`Times New RomanLSwUSw0-2
(iyTimes New RomanLSwUSw0-2
.ey Symbolw@
]LSwUSw0-2
GcySymbolw@w
ULSwUSw0-2
y Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,y
&
"System
0-8
2eA,Bi
FMicrosoft Equation 3.0DS EqEquation Native T_1143454657F="`q%="Ole
CompObjfuationEquation.39qO4 .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-2
@;R Times New RomanObjInfoOlePres000&Equation Native D_1143454658F`q%="@:6="-2
,Symbol-2
-3
&
"System-(II
2RA,B
FMicrosoft Equation 3.0DS EquationEquation.39qOle
CompObjfObjInfoOlePres000: .&`;&MathTypep`Times New RomanLSwUSw0-2
(iyTimes New RomanLSwUSw0-2
.ey Symbolw@
LSwUSw0-2
wcySymbolw@
LSwUSw0-2
y2
y Times New RomanLSwUSw0-2
By2
Ay Times New RomanLSwUSw0-2
,y
&
"System
0-8(
2eA,BiEquation Native T_1143454659F@:6="yP="Ole
CompObjf
FMicrosoft Equation 3.0DS EquationEquation.39qO4 .1&&MathType` Times New Roman-2
%B2
ObjInfoOlePres0006Equation Native D_1143454660FyP="ro="GATimes New Roman-2
@;R Times New Roman-2
,Symbol-2
-[2
-3
&
"System-(II
2RA,BIOle
CompObjfObjInfoOlePres000
FMicrosoft Equation 3.0DS EquationEquation.39q z .1&&MathType "-`=`~Symbol-2
C\ Symbol-2
Y2
YVc2
>c2
c2
cSymbol-2
= Times New Roman-2
YVX2
B2
A2
B2
ATimes New Roman-2
%e2
%e2
.e`Times New Roman-2
:di2
Hmi Times New Roman-2
JB2
JA,2
,2
,
&
"System-ըII
eA,Bi
=eA,Bi
eA,B"X
"Equation Native _1143454661Fro="x="Ole
CompObjf
FMicrosoft Equation 3.0DS EquationEquation.39qO4 .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-ObjInfoOlePres000&Equation Native D_1143454662Fx="pτ="2
@;R Times New Roman-2
,Symbol-2
-3
&
"System-(II
2RA,B
FMicrosoft Equation 3.0DS EqOle
CompObjfObjInfoOlePres0006uationEquation.39qO4 .1&&MathType` Times New Roman-2
%B2
GATimes New Roman-2
@;R Times New Roman
!"#$&),-./0123456789;<?BCDEFGHIKNQRSTUVWXZ]`abcdefghijklmnpqruxyz{|}~-2
,Symbol-2
-[2
-3
&
"System-(II
2RA,BI
FMicrosoft Equation 3.0DS EquationEquation.39qEquation Native D_1143454663Fpτ="P'="Ole
CompObjfObjInfoOlePres000 Equation Native Z_1143454664FP'="@Ĝ="b 1 .&@&&MathType`Times New RomanSw\w0-2
jy2
iyTimes New RomanSw\w0-2
:Ry Times New RomanSw\w0-2
xvy2
gvy Times New RomanSw\w0-2
2,y
&
"System
0-]>0[tF
Rvi,vj
FMicrosoft Equation 3.0DS EqOle
CompObjfObjInfoOlePres000uationEquation.39q4 A . &&MathType0 Symbolw@T
Sw\w0-2
_cy2
cy2
[cySymbolw@f
Sw\w0-2
y2
`=yTimes New RomanSw\w0-2
ey2
wyTimes New RomanSw\w0-2
.y
&
"System
0-F^LG
=w
eEquation Native %b_1143454665F@Ĝ=" ="Ole
'CompObj(f
FMicrosoft Equation 3.0DS EquationEquation.39qR\ .`&`&MathTypepSymbolw@
)Sw\w0-2
~{ySymbolw@
USw\w0-ObjInfo*OlePres000+Equation Native :_1143454666F ="L="2
~}yTimes New RomanSw\w0- 2
H_fie2
Ef2
_b,...,2
JEb 2
Neq,.2
_E_2
:E_`Times New RomanSw\w0-2
1_ Times New RomanSw\w0-2
@R_Symbolw@
WSw\w0-2
=_
&
"System
0-
ER1
=E_eq,E_b,...,E_fi{}
FMicrosoft Equation 3.0DS EquationEquation.39qOle
=CompObj>fObjInfo@OlePres000A .`&`&MathTypep`Times New RomanSw\w0-2
2y Times New RomanSw\w0-2
ARyTimes New RomanSw\w0-2
:Ey
&
"System
0-((E
ER2
FMicrosoft Equation 3.0DS EquationEquation.39qEquation Native JD_1143454667FL="="Ole
LCompObjMf
! &".$%'()*+,-/R0123456789:;<=>?@ABCDEFGHIJKLMNOPQObjInfoOOlePres000PEquation Native YD_1143454668F="T=" .`&`&MathTypep`Times New RomanSw\w0-2
ny Times New RomanSw\w0-2
ARyTimes New RomanSw\w0-2
:Ey
&
"System
0-(TE
ERn
FMicrosoft Equation 3.0DS EquationEquation.39q Ole
[CompObj\fObjInfo^OlePres000_.`&`&MathTypep`Times New RomanSw\w0-2
ny2
2y2
Y1y Times New RomanSw\w0-2
$Ry2
Ry2
RyTimes New RomanSw\w0-2
$Ey2
Q y 2
0ande
2
.,...,2
E.2
,.2
E.Symbolw@
9Sw\w0-2
.2
".2
.2
]".2
k.2
.".Times New RomanSw\w0-2
E.2
kE.2
<E.
&
"System
0-
"E"EREquation Native o_1143454669FT="p;="Ole
sCompObjtf1
,"E"ER2
,...,and "E"ERn
FMicrosoft Equation 3.0DS EquationEquation.39q Q ObjInfovOlePres000wEquation Native _1143454670Fp;="@l=".@
&
&MathTypeSymbolw@
Sw\w0-2
~(ySymbolw@
Sw\w0-2
~)ySymbolw@
Sw\w0-2
~:(ySymbolw@
Sw\w0-2
~%
)ySymbolw@
Sw\w0-2
y Symbolw@
Sw\w0-2
p=ySymbolw@
Sw\w0-2
=y Times New RomanSw\w0-2
wny2
1y2
(iy2
iyTimes New RomanSw\w0-2
Pr2
Sr2
:PrTimes New RomanSw\w0-2
Er
&
"System
0-r`LG
PrS()=PrEi
()i=1n
"
FMicrosoft Equation 3.0DS EqOle
CompObjfObjInfoOlePres000uationEquation.39qb 1 .``& &MathTypep`Times New RomanSw\w0-2
iy Times New RomanSw\w0-2
+Ry2
:iyTimes New RomanSw\w0-2
$Ey2
:EySymbolw@
kSw\w0-2
y
&
"System
0->
Ei
"ERiEquation Native Z_1143454671F@l="0="Ole
CompObjf
FMicrosoft Equation 3.0DS EquationEquation.39q
.&`7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\wObjInfoOlePres0002Equation Native C_1143454672F0=" 5="0-2
By2
AyTimes New RomanSw\w0-2
.ey
&
"System
0-'pT5
eA,Bb
FMicrosoft Equation 3.0DS EqOle
CompObjfObjInfoOlePres0002uationEquation.39q
.&7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
Cy2
ByTimes New RomanSw\w0-2
.ey
&
"System
0-'B
eB,Cb
FMicrosoft Equation 3.0DS EquationEquation.39qEquation Native C_1143454673F 5="="Ole
CompObjfObjInfoOlePres0002Equation Native C_1143454674F="н+="
.&7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
Cy2
AyTimes New RomanSw\w0-2
.ey
&
"System
0-'\
eA,Cb
FMicrosoft Equation 3.0DS EquationEquation.39qOle
CompObjfObjInfoOlePres0002
.&7&MathTypep Times New RomanSw\w0-2
by2
,y Times New RomanSw\w0-2
Dy2
ByTimes New RomanSw\w0-2
.ey
&
"System
0-'
eB,Db
FMicrosoft Equation 3.0DS EquationEquation.39q
Equation Native C_1143454675Fн+="<="Ole
CompObjfObjInfoOlePres000BEquation Native GSummaryInformation(.&7&MathTypep Times New RomanSw\w0-2
uiy2
by2
,y Times New RomanSw\w0-2
Dy2
CyTimes New RomanSw\w0-2
.ey
&
"System
0-+H
eC,DbiOh+'0, DP
x
>Representation of Uncertain Relations between Temporal Pointstktlwn0
&Ph ^zX
&?2929&__&~&4h]$(VN&h$(aV9h`$(uQhC$(-()(*(X (X({0 &}fXX0 &;xx0 &0 &rr0 &Jrr0 &O0 &W0 &}z0 &bbDocumentSummaryInformation8CompObjj;<KLXZ!$-YaO
hk'*n45:;JKN-./02VcuDL|ceuD'DcvKuDcJ`cJc`c
V`chU`cV`c`c ]ck ]`c]cUcaccUcc C stw*+02UWYZRSTUVijklm~Jc`ch`ch`c
V`chU`cJcJccJc
JcchchVchUcVccHRScdefghxyz{}¹ߐ߆߆߆߆߆߆߆chchVchUcuDȈ`ceuD'D`cvKuDt`ceuD'D`cvKuD`ceuD'D`cvKuD<`ceuD'D`cvKcuD~`ceuD'D`cvK`cuD`c3
$%-/TUqrst
#$%&.켳uD``ceuD'D`cvKuD`ceuD'D`cvKJ`cuD`c`ch`c`ch
V`chU`cD./012UVfghi
&'(*+,-./234=>?~쿷청쪝첚첚첚쪝VcchJUchuDaUcJcJccuD@ceuD'DcvKuDcuD`ceuD'D`cvKuD`c`ccU`cJ`cJc`c;
0 1 2 3 6 7 8 9 : ; = > ? @ A C D 缴笤眔珌Ԁ珌珌JUchJcchJccuDceuD'DcvKuD ceuD'DcvKuDceuD'DcvKuDceuD'DcvKUcuDceuD'DcvKcuDcuDДceuD'DcvK2D E I P !!!!!!!"""""" """"""""!"""(")":";"<"=">"A"B"I"J"R"S"["\"d"e"m"""""""""""""uD(ceuD'DcvKuDc`chuD`ceuD'D`cvKuD`c`ch
V`chU`c`ccUcENormal
Andre Trudel
47TMicrosoft Word for Windows 95t@G@6L@n>@="s{c՜.+,0@HX`hpxtktl2>Representation of Uncertain Relations between Temporal Points
FMicrosoft Word Document
MSWo"""""""### #
###$#%#&#(#*#+#;#<#=#?#[#\#]#_#o#p#q#r###################
$$$$$$-$ŽuDceuD'DcvKJcJccuDhceuD'DcvKuDceuD'DcvKuDȮceuD'DcvKchVchUcuDpceuD'DcvKuDcc7-$.$/$0$6$7$G$H$I$J$O$P$`$a$b$c$i$j$z${$|$}$$$$$$$$$$$$$$$%%.%/%0%1%4%6%<%=%C%D%N%O%_%`%翷笤瘐頋uDƻ'DcvK`chuDpceuDŻ'DcvK`cuDlceuDĻ'DcvKUcuD ceuDû'DcvKuDceuD»'DcvKuDceuD'DcvKcuDcuDTceuD'DcvK3`%a%b%e%g%o%p%w%x%%%%%%%%%%%%%%%%&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&"'#'2'3'5'v'w'y'z'߲ݭݩV]c]cJYcJcJccJc
JcchuDceuDǻ'DcvKVcUccchVchUc`ch`cuDcuDce@z'|'}'''''''''''''''''''''''''''''''''''''''''''''''''(((((((((((`)n))*0+1+3+8+9+:+++,,,,,,,,chUcVcaccuDa]ch]ch
V]chU]cV]c]cQ,,,,,-------......./000000000+1,1/1E1F1I1J1K1L1O1P1Q1S111111111111111-2.212r2s2v222222233 34444444444444`ch`c
JcchJcJcch ]`c]cUccchS444444455555555%5'5+5455565<5>5F5G5L5555556)6*6-67 7#77777777777777777778888!8$8)8*8+85878;8<8@8C8G8H8L8S8T8U8j8ac ]ckuDaJcJcJcJ|cJcchUcc`c`chMj8k8n8o8p8r8s8v8w8x8y8z8|88888888888888888899 9
9
9C9D9G9}99999999999999:::::
:::::::::(:G:H:K:M:O:T:U:V:W:Z:\:_:::::JcuDaJcchUccJcJcacachUacR::::::::;;;;; ;3;4;7;P;Q;T;};~;;<<m<p<u<x<===>">4>7>????@@B$BCCCCCCCfDgDhDDDDDDDDDDDDDDFFFFGGGGGG#G]ch
V]chU]cV]c ]ck ]`c]ch]cJcuDachcUcM#G&G-G/G0G7G8G>GCGHGIGJGKGLGMGNGOGPGQGGGGGGGGGGGGGGGGG
HHH#H-H1H7H9H?HAHJHOHXHZH[HdHeHhHuHyHHHHHHHHHHHIIJJJJJ7K9KDKEKOKfKiKchVchUcVccV]c]chJ]c
V]chJ]cuDaU]c]cNiKjKpKqKwKxKKKKKKKKKLLLLLWLYLbLcLdLeLfLnLrLsLtLLLLLLLLLLMMMMM6OOOMPPPQQQQQQQ(QQQQQQQ)SJST1TTUVVXXXXXXXXXXXX]ch ]`c`cc]ch
V]chuDaU]cV]c]cRXXXX]Y^Y_Y`YaYYY]]]]]$^.^3^4^5^6^7^^^^^^^^__`` `
`
````````%`&`'`*`+`,`-`.`/`0`1`7`8`9`Z`[`r`ļ
Jc]chJ]cJc]cU]acuDU]cuD]euDȻ'D]cvKuD]cchVchcUc ]`c]ch
V]chU]c]c]chGGGMHHHHH5K6K7KKK 1e1 1&1
4hx.11Oe,<e"KOLsLLLLL5M6OQ(Q)STTVXY$^^_```aUbJdF+ !]!]"
e4hx7,<ee"1
1JdrdPefhhhhijjjjjjjjjjj(l 4uV7
F2!]!]e,<jjjjjjjjjjjjjjjjjjjjjjjjjjjCk\me#-l 4uV7
(l 4uV7 \mooo^qMrssssttuvvwwx$yy?zz{{{{{{{{{{{{{{{{{{x%77,<e'{{{{{|x;K @ Normal a ck(@( Heading 1
7Uc*@* Heading 2hUc@@@ Heading 3,U]ckn`n Heading 4I
<4U]ckj`j Heading 5G
<4 ]ckh`h Heading 6G
<4Vckj`j Heading 7G
<4 ]ckl`l Heading 8G
<4V]ckn `n Heading 9G
<4
UV]ck"A@"Default Paragraph Font.B@. Body Text7 ]ck:0@:List Bullet7xU]$/@$ListP>@"TitleUc"O2"Body Text 2c&OB&Body Text 27c*@R*Header9r a ck)@aPage Number @r Footer!,O,address ]ck&O&
Block Text
Vc&O&p1a ]ck>O>title ,U]ck.O.author ]ck*OB*email ]ck>O>heading1,U]ck>O>heading2,U]ck<O<heading3 $@,U]ck<O<equation!xx] ]ck:O:
figure legend"$x ]ck:O:table title#$x]ack.O.abstract$77$Xxc6OR6
referenceitem%$ ]ck&&@a&Footnote ReferencecehDOrDRunning head - left'] ]ck&Oq&Running head - right(ZoZBullet Item?)4??@nonItemQ*
4? ]ckVoV
Numbered Item:+
4.<@<
Footnote Text,V$ ]ckPOPprogramcode,-xxQOM ]ckDODFunotentext.Footnote.V$ ]ck4"@4Caption/xxU]ck.O.heading40@V]ck,O,Normal (Web)1dd ]ck0O"0Licentiate text27 ] ck0O20Balloon Text3 ]
ck$'@A$Annotation Referencec4@R4Annotation Text5 ]ck$OQR$annotation subject6U&Or&Body Text 27ec4OQR4annotation subject8U]kb1`bList NumberG9
h4h4OQR4annotation subject:U]k
#6HPX[y|#|.D "-$`%z',4j8:#GiKXr`fjl}~$1d;KJdj\m{|RcegxzTqs
#%Ufh 02* ; = > [ ] ^ o q
!!!-!/!6!G!I!O!`!b!i!z!|!!!!"."0"N"_"a"###\] ]
]]]bbbrccccccd.d0deeeeee i1i3i:iKiMiTieigili}iiiiiy::::::9:::::::::::9:::9:::::::::::::::::::::::%4*5T568/DDHsIy Iy 9i@Times New RomanSymbol"Arial
Tms RmnTimesSchoolBook1Courier New
1Courier"Arial Unicode MS PalatinoBook Antiqua"Tahoma"hzf_sf[f/s{c2a=Representation of Uncertain Relations between Temporal PointstktlAndre TrudelrdDocWord.Document.89q
FMicrosoft Word Document
MSWordDocWord.Document.89q