# Temporal reasoning with constraints on fluents and events

发布时间:2021-11-29 06:13:06

Temporal Reasoning with Constraints on Fluents and Events 3

Eddie Schwalb, Kalev Kask, Rina Dechter

Department of Information and Computer Science University of California, Irvine CA 92717 feschwalb,kkask,dechterg@ics.uci.edu

Abstract

We propose a propositional language for temporal reasoning that is computationally effective yet expressive enough to describe information about
uents, events and temporal constraints. Although the complete inference algorithm is exponential, we characterize a tractable core with limited expressibility and inferential power. Our results render a variety of constraint propagation techniques applicable for reasoning with constraints on
uents.

1 Introduction

Consider the issues raised by the following \story". At 8:00 the microlm was deposited in the safe and at 11:00 the microlm was gone. John was at the bar between 8:10 - 8:30 and between 9:10 -12:00. He was also at the poker table between 8:35 - 9:00. Fred was at the bar between 8:30 - 10:00 and between 10:45 12:00. The bar opened at 7:30 and closed at 12:00. We know that at least 15 minutes are required to take the microlm and return to the bar. Given the story above, we are interested in answering queries such as \Does the story entail that Fred took the microlm ?" and \What are all the possible scenarios in this story ?". We wish to capture the human ability to answer such queries without information about speed of movement or distances. We wish to describe information conditioned on occurrences of events. For instance, a sentence like \at least 15 minutes are required to take the microlm and return to the bar" should be accounted for only if someone took the lm; a query like \When did John take the microlm ?" assumes that John took the microlm.

This work was partially supported by NSF grant IRI9157636, by Air Force Oce of Scientic Research grant AFOSR 900136 and by grants from TOSHIBA of America and Xerox

3

In classical propositional logic the atomic entities are propositions. In dynamic environments the atomic entities are called
uents. They may repeatedly change their value as events occur and are functions of the situation or time. Our work builds upon temporal languages proposed by McDermott and Dean [11, 5], Allen [2], Kowalski and Sergot [9] and Shoham [14]. We accommodate various constructs proposed in these languages (time points and intervals). Our main goal, however, is to equip a temporal language with a computationally manageable inference engine. The primary task of any reasoning system is determining consistency of the given theory. For temporal languages this means determining the consistency of sentences involving a combination of temporal and propositional constraints. For example, consider the statement \Either Bob or Mary must tend the bar, but Bob has to leave on an errand and Mary has an appointment with the doctor". How do we infer that Bob's errand must be either before or after Mary's appointment ? In this paper we propose a temporal language whose inference engine is based on qualitative and quantitative temporal constraints [1, 6, 7, 12, 15, 16]. Decoupling the propositional and temporal constraints provides us with inference algorithms that are based on propositional satisability and temporal constraint satisfaction, and allows us to identify a useful tractable core. The proposed language, called HOT, is dened over Holds, Occurs and T emporal propositions. We assume that events are instantaneous and serve as the only time points at which
uents may change their values. We use Holds(F; E1; E2) to state that the
uent F is true between events E1 and E2, Occurs(E ) to state that event E occurred, and T ime(E ) for the time of its occurrence. We focus on the tasks of deciding consistency and computing consistent scenarios, which enables us to answer entailment and other queries of interest (such as inferring whether certain events must, might, or could not have occurred). Our language has a tractable core which allows us to make weak (sound but incomplete) inferences. When augmented with ad-

ditional axioms, our language yields sound and complete inference algorithms at the expense of increased computational complexity. The paper is organized as follows. Section 2 describes the syntax and semantics of our language. Section 3 gives an alternative propositional semantics for the language. Section 4 introduces a new model of conditional temporal constraint networks that serves as the computational engine.

2 The Language

with E and ends with E , (3) T ime(E ) fR1; . . . ; R g I j k where R1; . . . ; R 2 f before, starts; during, nishes, after g. 3. An interval-interval constraint I i j fR1; . . . ; R g I p q (4) where R1; . . . ; R ; m 13 are distinct and

j k i m E ;E m E ;E m m E ;E

Our language, called HOT, is a set of sentences over Holds, Occurs and T emporal propositions. We use two (disjoint) sets of symbols,
uent symbols and event symbols. A
uent is a propositional function of time and a
uent literal is either a
uent symbol or its negation. An event E is a pair (Occurs(E ); T ime(E )), where Occurs(E ) is a propositional variable that is assigned true i E occurred, and T ime(E ) is a real valued variable that species the time E occurred. We use two special events: E , for \the beginning of the world", and E , for \the end of the world". Unless otherwise noted, we use right-sided half open intervals [a; b) for reasons to be claried later. In addition to Occurs propositions there are Holds and Temporal propositions. A Holds proposition has the form Holds('; E ; E ) (1) where E and E are event symbols and ' = F1 _1 1 1_F is a disjunction of
uent literals. We also use the following abbreviations: If E = E we write (1) as Holds('; E ). If E = E we write (1) as Holds('; before E ). If E = E we write (1) as Holds('; after E ). If E = E = E or E = E = E or both E = E and E = E we write (1) as initially ', eventually ', always ' respectively. A Temporal proposition is a qualitative or quantitative temporal constraint over time points and time intervals [12]. Given a pair of events E ; E , I i j denotes an half-open interval that begins with (includes) T ime(E ) and ends with (excludes) T ime(E ). A temporal proposition is a constraint having one of three forms: 1. A point-point constraint T ime(E ) 0 T ime(E ) 2 I1 [ I2 [ 1 1 1 [ I (2) where I1 ; . . . ; I are intervals (over real numbers), specied by their end points. We also use the shortcuts T ime(E ) 2 I1 [ I2 [ 1 1 1 [ I , T ime(E ) = t and T ime(E ) T ime(E ) to have the obvious meaning. 2. A point-interval constraint between the time point at which event E occurred and the interval that begins

begin end i j i j k i j i i begin j j end j i i begin i j end i begin j end i j E ;E i j j i k k j k j j i i

R1 ; . . . ; R

m

8 before; after; meets; met0by; 9 > overlaps; overlapped0by; > < = 2 > during; contains; equals; > : starts; started0by; : ;

nishes; nished0by

Sentences in HOT are conjunctive normal form (CNF) formulas over Holds, Occurs and Temporal propositions as their atoms. Example 1: Consider the story in the introduction. The sentence \At 8:00 the lm was deposited in the safe and at 11:00 the lm was gone" is described by

Holds(Film in safe; Film deposited) ^ (Time(Film deposited) = 8 : 00) ^ Holds(:Film in safe; Film checked) ^ (Time(Film checked) = 11 : 00):

The sentence \at least 15 minutes are required to take the microlm and return to the bar" is described by A similar sentence can be described for Fred.

2.1 Semantics

f e

Occurs(John take film) ! (Time(end John go safe) 0Time(begin John go safe) 2 [15; 1])

< F ; M ; E ; M >, where F is a set of two-valued functions of time; M is a mapping M : F 7! F

f f e e

An interpretation of a formula in HOT is a quadruple

of
uent symbols into functions in F; E is a subset of event symbols and M is a mapping M : E 7! < of events in E into real valued time points. The value of M (') may change only when events occur, namely at a time point t = M (E ) for some event E . Intuitively, F is a set of
uents that corresponds to
uent symbols used in the formula and E is the set of events that actually occurred, mapped to the time points at which each of them occurred. Denition 1: An interpretation is a scenario (or a model) of a formula if all its clauses are assigned the truth value true under the following rules of evaluation: 1. Occurs(E ) is true i E 2 E. 2. We extend M to disjunction and negation, M (F1 _ 1 1 1 _ F ) = M (F1) _ 1 1 1 _ M (F ), M (:F ) = :M (F ).

f e f f k f f k

3. A holds proposition Holds('; E ; E ) is true i E ; E 2 E, and (a) in case E = E then M (')(M (E )) is true, (b) in case E 6= E then M (E ) < M (E ) and for any t such that M (E ) t < M (E ), M (')(t) is true. 4. A temporal proposition is true i the events specied occurred and the temporal constraint is satised, namely (a) a point-point temporal proposition (2) is true i E ; E 2 E, and M (E ) 0 M (E ) 2 I1 [ I2 [ 1 1 1 [ I . (b) a point-interval temporal proposition (3) is true i E ; E ; E 2 E and M (E ) < M (E ) and one of the relations R1; . . . ; R holds. (c) an interval-interval temporal proposition (4) is true i E ; E ; E ; E 2 E and M (E ) < M (E ) and M (E ) < M (E ) and one of the relations R1; . . . ; R holds. 5. The truth value of the clauses and the CNF formula is evaluated with respect to the truth values of occurs, holds and temporal propositions using standard rules of evaluation.

i j i j i j f e i j e i e j e i e j f i j e j e i k i j k e j e k m i j p q e i e j e p e q m

For the rest of this paper we will restrict our treatment to HOT sentences whose Holds('; E ; E ) propositions we call simple, namely holds propositions in which ' is a single
uent literal unless E = E and E = E (i.e. Holds('; always)). General holds propositions introduce computational complications which we will not address in this paper.

i j i begin j end

3 Propositional Semantics for HOT

A formula is s-satisable i it has a scenario. Note that Holds('1 ^ '2 ; E ; E ) Holds('1 ; E ; E ) ^ Holds('2 ; E ; E ). However, Holds('1 _ '2; E ; E ) is obviously not equivalent to Holds('1 ; E ; E )_ Holds('2 ; E ; E ). Also note that Holds(:'; E ; E ) is not equivalent to :Holds('; E ; E ). The formula Holds(F; E ; E )^ Holds(:F; E ) is inconsistent but Holds(F; E ; E )^ Holds(:F; E ) is consistent because the interval I i j is half-open. If we used closed intervals, Holds(F; E ; E ) ^ Holds(:F; E ; E ) would have been inconsistent and the values of the
uents would not be allowed to change when events occur. If we had used open intervals, specifying Holds(F; E ) would have been useless since it does not induce a constraint on the value of M (F )(t) for the open interval t 2 (T ime(E ); T ime(E )). An occurs, holds, or temporal proposition q is entailed by 9, denoted 9 j= q, i it is true in all scenarios of 9. As usual, 9 j= q i 9 ^ :q is inconsistent.

i j i j i j i j i j i j i j i j i j i i j j E ;E i j j k i f i j

In this section we address the task of deciding whether a formula is s-satisable. We wish to show that the task of deciding s-satisability and nding a scenario reduces to a two-step process of propositional satisability and temporal constraint satisfaction. Although both of these tasks are NP-complete, such a reduction opens the way for using known heuristics and known tractable classes. The idea is to view 9 as a propositional CNF formula. Once a propositional model is available, using temporal constraint satisfaction we can determine whether all temporal constraints, specied by temporal propositions assigned true by the model, can be satised simultaneously. Denition 2: [ p-model ] Given a set of event and
uent symbols, a p-interpretation is a truth value assignment to holds, occurs and temporal propositions when viewed as propositional variables. A p-interpretation is a p-model of a HOT formula 9 i it is a propositional model of 9 and the set of temporal constraints specied by the temporal propositions assigned true is consistent. Upon trying this approach we see immediatelythat this process may yield p-models that do not correspond to any real scenario. The reason is twofold: holds propositions impose implicit temporal constraints that are not explicit in the formula, and temporal propositions should be assigned true i the temporal constraint they induce is satised (p-models capture only one-way implication). For instance, a formula consisting of just one holds proposition Holds(F; E ; E ) will have a pmodel that allows any assignment to temporal variables T ime(E ) and T ime(E ), since there is no explicit temporal proposition specifying T ime(E ) < T ime(E ). In order to avoid these super
uous p-models, we augment 9 with axioms that explicate the intended meaning. In the following paragraphs we will augment a formula 9 with additional HOT sentences that will be called axioms. The resulting augmented theory 9 describes the same set of scenarios as the original theory 9. However, every p-model of 9 corresponds to a set of scenarios of 9 and every scenario of 9 corresponds to a p-model of 9 . Denition 3: [ axiom set A1 ] Given a formula 9, the axiom set A1 has four parts:

i j i j i j 0 0 0

Consider the statement \John was at the bar from 8:10 to 8:30". It is described by the formula 9 = Holds(John at bar; 8:10; 8:30).1 9 j= Holds(John at bar; 8:15; 8:25) but 9 6j= Holds(John at bar; 8:15; 8:35) because the value of the
uent John at bar is not constrained after 8:30 and thus it can be either true or false.

Example 2 :

For the sake of convenience we will use real time points as events.

1

1. For all events add T ime(E ) < T ime(E ) < T ime(E ), and for all pairs of events E ; E add I i j fequalsgI j i . 2. For every event E specied in a temporal proposition T we add the axiom T ! Occurs(E ). 3. For every holds proposition Holds('; E ; E ) of 9 we include sentences stating that if a holds proposition is true, the corresponding events should have occurred and in the intended order:

begin end i j E ;E E ;E i j

and John was not at the bar at 10 : 00" which can be represented by the formula The axiom set A1 includes T ime(E ) < 8:00 < 10:00 < T ime(E ), and the axiom set A2 includes

begin

Holds(John at bar _ Fred at bar; always) ^ Holds(:Fred at bar; after 8:00) ^ Holds(:John at bar; 10:00)

end

Holds('; E ; E ) ! Occurs(E ) ^ Occurs(E ); Holds('; E ; E ) ! (Time(E )fstartsgI i j ); Holds('; E ; E ) ! (Time(E )ffinishesgI i j ):

i j i j i j i E ;E i j j E ;E

4. For every pair of holds propositions with opposing
uents, Holds(F; E ; E ) and Holds(:F; E ; E ), we add a sentence stating that the two intervals are disjoint. In general we will add

i j p q

although there are special cases that are simpler. The next set of axioms deals with the complications introduced by disjunctive holds propositions. Here is an example. Example 3: Consider the example statement \Either Bob or Mary must tend the bar, but Bob has to leave on an errand and Mary has an appointment with the doctor". It can be represented by the formula 9 = In order to guarantee consistency of (5), it is necessary that the intervals of Bob's errand and Mary's appointment be disjoint. Otherwise, there will be a time point at which both Bob tend bar and Mary tend bar are false, contradicting Holds(Bob tend bar _ Mary tend bar; always): The set of axioms A2 , dened next, includes a constraint that enforces those intervals to be disjoint. Denition 4: [ axiom set A2 ] Given a formula 9, if there exists a holds proposition h0 = Holds(F1 _ . . . _ F ; always) then for any set of k holds propositions fh = Holds(:F ; E i ; E i ) j 1 i kg we include the sentence

k i i p q

Holds(F; E ; E ) ^ Holds(:F; E ; E ) ! (I i j fbefore; meets;met0by; aftergI

i j p q E ;E

E

p ;Eq )

:

Holds(Bob tend bar _ Mary tend bar; always) ^ Holds(:Bob tend bar; begin errand; end errand) ^ (5) Holds(:Mary tend bar; begin apnt; end apnt)

Since, the constraints introduced by A1 and A2 are inconsistent, the statement is inconsistent. The set of axioms A1 and A2 is not sucient to eliminate all super
uous p-models. They do guarantee that for every holds proposition Holds(F; E ; E ) assigned true we can assign M (F )(t) = true for every t 2 I i j without creating con
icts. However, A1 and A2 do not guarantee that when the holds proposition is assigned false, the negation of the intended constraint is satised in every p-model. To guarantee completeness we provide yet another set of axioms, denoted A3 , which specify that the truth value of a holds proposition is inherited by sub- and super-intervals and that a temporal proposition is assigned true i the temporal constraint is satised. Denition 5: [ axiom set A3 ] Given a formula 9, for every disjunction of
uent symbols ' = F1 _ ::: _ F used in the formula, all
uent symbols F , every set of events E , E , E , E and every temporal proposition T we include:

i j f E ;E k i j p q

Holds(John at bar _ Fred at bar; E ;E ) ^ Holds(:Fred at bar; 8:00; E ) ^ Holds(:John at bar; 10:00) ! (I8:00 end fbefore; meets;met0by; afterg10:00):

begin end end ;E

:Holds( ;E ; E ) ^ Occurs(E ) ^ Occurs(E ) ! W f(I I ) ^ Holds(: ; E ; E )g p q i j 8

i j i j p;q E ;E E ;E p q i j E

(6)

Holds( ;E ; E ) ^ (I

2

:T

^

p ;Eq

I

E ;E

i

Holds( ;E ; E )

p q

j)

!

(7) (8)

8E

Occurs(E ) ! T

specif ied in T

where 2 f'; F g, stands for the constraint fstarts, during, nishes, equalsg and T denotes the complement of the temporal constraint T . For example, if T = (I1 fstarts,during,nishesgI2 ) then T = (I1 fbefore, after, meets, met-by, overlaps, overlapped-by, contains,nished-by,started-by,equalsgI2).

Lemma 1: The size of axiom sets A1 ; A2 and A3 is at most O(n2), O(nk2 ( ) ) and O(n 1 n4) respectively, where n is the size of the theory axioms are added to, n is the number of event symbols and k is the maximum number of
uent literals in a disjunctive holds proposition.

n k k e e

although there are special cases that are simpler. Example 4: To illustrate the utility of axioms A1 and A2 , consider the statement \John or Fred was always at the bar, but Fred was not at the bar after 8 : 00

hW^ h1 ^ . . . ^ h ! 0 (I pi qi fbefore; meets; met0by; after gI

k i<j k E ;E

Ep ;Eq ) j j

This axiom enables contrapositive reasoning with temporal propositions.

2

Propositional Constraints

Conditions (Buffer) Temporal Network

The truth values of conditions control the temporal subnetwork that needs to be satised. Clearly as more conditions are assigned true the corresponding temporal network is more constrained. We can conclude:

Theorem 2: A conditional temporal network N is

consistent i there exists a minimal model of the propositional part of N such that the set of temporal constraints whose condition is assigned true is satisable.

Figure 1: The structure of CTNs. We use 9 [ A1 [ A2 [ A3 to denote the closure under axioms A1; A2 and A3 . Lemma 2: The HOT formulas 9 and 9 = 9 [ A1 [ A2 [ A3 are equivalent with respect to s-satisability. Theorem 1: Every p-model of 9 [ A1 [ A2 [ A3 corresponds to a set of scenarios of 9 and every scenario of 9 corresponds to a p-model of 9 [ A1 [ A2 [ A3 .

0

4 Conditional Temporal Networks The notion of p-models decouples the propositional

This suggests a procedure for determining the consistency of a CTN. We enumerate all minimal models of the propositional part of a CTN and for each of them determine whether the applicable temporal network is consistent. The task of computing the minimal models of a CNF formulahas been investigated and is known to be hard [4, 3]. For Horn formulas, the minimal model is unique and can be computed in polynomial time, thus tractability depends on the temporal constraints.

is Horn and temporal part is tractable, consistency can be determined in polynomial time.

constraints from the temporal constraints and enables us to discuss them in isolation. We call this framework conditional temporal networks. Denition 6: A conditional temporal network (CTN) has two types of variables: propositional and temporal (point and interval), and two types of constraints: propositional and temporal. Every temporal constraint T is associated with a unique propositional variable C , called its condition. A conditional temporal constraint is a pair (C : T ). A propositional constraint is a propositional CNF formula over propositional variables and temporal conditions. A solution to a CTN is a truth value assignment to the propositional variables and temporal conditions, an assignment of values to the temporal point variables and a selection of a single relation from every qualitative temporal constraint, such that every propositional constraint and all temporal constraints whose condition is assigned true are satised simultaneously. Using these denitions, we can intuitively divide every CTN into propositional and temporal parts. Propositional constraints impose certain restrictions on the conditions that act as a buer and allow us to perform computations on the propositional and temporal parts of the network separately (see Figure 1). Example 5: Consider a network with seven variables: a propositional variable P , a point variable X1 , two interval variables I2 ; I3 , and three conditions C1; C2; C3, with the constraints One solution is P = C1 = C2 = C3 = true, X1 = 1:0, X1 fstartsgI2 , X1 ffinishesgI3 , I2 fmet0bygI3 .

P $ C 1 $ C2 $ C 3 ; (C1 : X1 fstartsgI2 ); (C2 : X1 ffinishesgI3 ); (C3 : I2 fbefore; after; meets;met0bygI3 ):

Corollary 1: Given a CTN whose propositional part

4.1 Tractable Core

We determine the consistency of 9 = 9[ A1 [ A2 [ A3 by checking the consistency of a CTN in which propositional constraints are the propositional clauses of 9 , conditions are the temporal propositions of 9 and temporal constraints are specied by those temporal propositions. Axiom set A1 introduces Horn clauses and tractable temporal constraints. Axiom set A2 and axioms (6) and (8) of A3 are intractable since they introduce non-Horn clauses. If we do not add axiom sets A2 and A3, p-satisability and p-entailment become tractable for Horn temporal formulas.

0 0 0

Theorem 3: If 9 is a Horn temporal formula in which every holds proposition species a single
uent literal and every temporal proposition species either single interval (if point-point) fstartsg or fnishesg (if point-interval), fequalsg, fbefore,meetsg,fafter,metbyg or any of their disjunctions (if interval-interval), then p-consistency of 9 [ A1 can be determined in O(j9j2 + n3) steps, where n is the number of event symbols.

e e

We will examine the inferences that 9 [ A1 is capable of making. We use 9 j= to denote s-entailment and 9 j= to denote p-entailment. Clearly, for every sentence , if 9[ A1 j= then 9[ A1 [ A2 [ A3 j= and thus 9 j= . However, it might be that 9 j= and 9 [ A1 6j= . Still, if there is a clause ! in 9 and 9 [ A1 j= then 9 [ A1 j= .

p p p p p p

Example 6: When adding only A1,

Holds(F; always) j= Holds(F; always) 6j= Holds(F1; E ; E ) j= Holds(F1; E ; E ) 6j=

i j i j p p

Acknowledgments

i j j

p

p

:Holds(:F; E ; E ); Holds(F; E ; E ); :Holds(:(F1 _ F2); E ; E ); Holds(F1 _ F2 ; E ; E ):

i i j i j

We would like to thank Andre Trudel for his comments on an earlier version of this paper.

References

[1] Allen, J.F., 1983. Maintaining knowledge about temporal intervals, CACM 26 (11):832-843. [2] Allen, J.F., 1984. Towards a general Theory of Action and Time, Articial Intelligence 23:123-154. [3] Ben-Eliyahu, R., Dechter, R., 1993. On computing minimal models, In Proc of AAAI-93, 2-8. [4] Cadoli, M., 1992. On the complexity of model nding in nonmonotonic propositional logics, In Proceedings of the Fourth Italian Conference on Theoretical Computer Science, October 1992. [5] Dean, T.M., McDermott, D. V., 1987. Temporal data base management, Articial Intelligence 32:155. [6] Dechter, R., Meiri, I., Pearl, J., 1991. Temporal Constraint Satisfaction Problems, Articial Intelligence 49:61-95. [7] Golumbic, C.M., Shamir, R., 1991. Complexity and Algorithms for Reasoning about Time: A graph theoretic approach, Rutcor Research Report 22-91 (May 1991). [8] Kautz, H., Ladkin, P., 1991. Integrating Metric and Qualitative Temporal Reasoning, In Proc. of AAAI91, pages 241-246. [9] Kowalski, R., Sergot, M., 1986. A Logic-based Calculus of Events, New Generation Computing 4:6795. [10] Ladkin, P.B., Reinefeld, A., 1992. Eective solution of qualitative interval constraint problems, Articial Intelligence 57: 105-124. [11] McDermott, D.V., 1982. A Temporal Logic for Reasoning about Processes and Plans, Cognitive Science 6:101-155. [12] Meiri, I., 1991. Combining Qualitative and Quantitative Constraints in Temporal Reasoning, In Proc. of AAAI-91, pages 260-267. [13] Schwalb, E., Dechter, R., 1993. Coping with Disjunctions in Temporal Constraint Satisfaction Problems, In Proc. AAAI-93, 127-132. [14] Shoham, Y., 1986. Reasoning about Change: time and causation from the stand point of articial intelligence, Ph.D. dissertation, Yale Univ. [15] Van Beek, P., 1992. Reasoning about Qualitative Temporal Information, Articial Intelligence 58:297326. [16] Vilain, M., Kautz, H., Van Beek, P., 1989. Constraint Propagation Algorithms for Temporal Reasoning: A revised Report. In Readings in Qualitative Reasoning about Physical Systems, J. de Kleer and D. Weld (eds).

The anomalies of the second and fourth inference can be avoided by adding some subsets of axioms A3 . In principle, as a topic for future research, it would be worthwhile to associate classes of queries with a subset of axioms A1 ; A2 and A3 that, if added, will guarantee sound and complete inferences with respect to these queries. Qualitative and quantitative Temporal constraint networks can be processed with a variety of algorithms, presented in [1, 6, 12, 10, 15, 13]. In particular, it was reported in [10] that qualitative temporal networks can be eciently solved using path-consistency as a preprocessing procedure before backtracking. In [13] an eective preprocessing procedure for quantitative temporal networks is presented.

5 Conclusion

We have proposed a propositional language for temporal reasoning that is computationally eective yet is expressive enough to describe information about
uents, events and temporal constraints. The language, called HOT, is a set of propositional CNF formulas over Holds, Occurs and Temporal propositions as their atoms. A model (or a scenario) of an input theory determines what events happened and species the value of every
uent at every point in time. We dene an alternative propositional semantics for HOT that decouples propositional constraints from temporal constraints and allows to consider them separately. We call this framework conditional temporal networks. A conditional temporal network is consistent i there exists a minimal model of the propositional constraints such that the set of temporal constraints whose condition is assigned true is satisable. These results render a wide variety of temporal constraint propagation techniques applicable to reasoning about events and
uents. In particular, we identify a syntactically characterized tractable core for which a weaker (sound but incomplete) tractable inference procedure exists. This tractable core can be used as an upper bound approximation. Additional axioms yield more inferential power but at the cost of increased computational complexity. In practice, when it is known which queries are of interest, a user can add only an appropriate subset of the axioms. 6