Reified Temporal Theories and How to Unreify Them

1 Introduction

There is now a broad consensus within the AI community that a wide range of tasks such as planning, explanation, diagno­ sis, and narrative understanding cannot be adequately accom­ plished without some form of temporal reasoning capability. There is much less agreement as to what form this capability should take. Even amongst those who would advocate some form of logic for this purpose, there are disagreements as to the syntactic form required of such a logic, let alone the way in which it is to be interpreted.

Increasingly, however, there has been a move towards what are known as reified temporal logics [Shoham, 1986]. Syntactically, a reified temporal logic is distinguished by the fact that expressions which we would ordinarily re­ gard as propositional in nature, e.g. Kiss(john, mary) or In(john, london), acquire the status of terms in a first-order theory. Thus where a non-reified temporal logic might ex­ press the fact that John kissed Mary on Monday in a form such as 1 Kiss(john, mary, monday) or, using a modal operator R in the style of Rescher and Urquhart [1971], Rmonday(Kiss(john, mary)), a reified logic will introduce a term kiss(john, mary) which can serve as an argument to a predicate such as Occur:

1 I use the convention of writing a predicate with an initial capital letter, and function symbols and terms in lower-case.

Semantically, to reify a concept is to accord it full onto­ logical status, so that it becomes an entity we can ascribe properties to and, in principle, quantify over. In general, the ontology of a first-order theory is the domain of its intended interpretation, i.e., the set of entities which can be referents of terms in the theory.

In this paper I argue that much of the reification that has been proposed is both technically unnecessary and philosophically suspect, and shall propose a general procedure for excising such reification from a temporal theory.

2 Allen's Theory

In the reified theory of Allen [1984], we can write formulae such as (1) abovel or

In order to apply to formulae (1) and (2) the standard model­ theoretic semantics of first-order logic, we must postulate a domain which includes not only people (referents of john and mary), places (referent of london), and times (referent of monday), but also entities to be the referents of the complex terms kiss(john, mary) and in(john, london). Moreover, the predicates Holds and Occurs must be mapped onto rela­ tions between the referents of these complex terms and times. To be specific, formula(1) states that the entity denoted by the term kiss(john, mary) stands in the relation of occurrence to the time denoted by monday; and (2) likewise states that the entity denoted by in(john, london) stands in the relation of holding to the time denoted by monda'!}.

What are the entities referred to by these complex terms? For Allen, a term such as kiss(john, mary), which can oc­ cur as the first argument of the Occur predicate, denotes an

1 Actually, (1) for Allen would imply that the kiss lasted all day. In the terminology of Galton [1990], Allen's predicate Occur is Occurs-on, whereas the Occur of(l) is Occurs-in. For simplicity of exposition I write as if Allen's predicate was also Occurs-in, since this is closer to the way in which we usually ascribe events to times in ordinary language. The resulting slight discrepancy with Allen's actual theory in no way invalidates what I say about it, which would apply equally to either interpretation of Occur.

3 0f course, the word 'Monday' normally refers to all the days of a certain class, not just to one particular day: for simplicity, though, I assume that the term monday is mapped onto one particular Monday.

'event', whereas a term such as in(john, london), which can occur as the first argument of the Holds predicate, denotes a 'property'. Beyond this, Allen does not give an explicit se­ mantics, but a plausible clue comes from McDermott [1982], whose system has many points in common with Allen's and has often been compared with it. McDermott says 'we will take a fact to be a set of states, intuitively those in which it is true'. A state for McDermott is 'an instantaneous snapshot of the universe'; the set of all states is partially ordered, and there is a mapping d from the states to real numbers, giving the date at which each state obtains 4 · McDermott goes on to define an event as 'a set of intervals, intuitively those intervals over which the event happens once, with no time "left over" on either side.'

These ideas can be applied, after suitable modification, to Allen's theory. Allen does not have McDermott's notion of a state; instead, he makes his Holds predicate map properties (the analogue of McDermott's facts) directly onto times-this is possible for Allen as he does not model alternative possible futures in his system. So the obvious semantics to give to Allen's formulae oftype (2) above is as follows:

in(john, london) denotes a set of intervals.

H olds(in(john, london), monday) is true iff the interval denoted by monday is a member of the set of intervals denoted by in(john, london).

And for formulae oftype (1),

Occur(kiss(john, mary), monday) is true iff the interval denoted by monday is a member of the set of intervals denoted by kiss(john, mary).

The difference, for Allen, between properties and events is captured by his axioms

which imply that, in Shoham's terminology [Shoham 1988], properties are downward-hereditary (i.e., a property holds on any subinterval of an interval on which it holds) whereas events are gestalt (i.e., an event does not occur on any proper subinterval of an interval on which it occurs) 5 · Semantically, this means that for the set of intervals I associated with a property, whenever i E I and i' c i, then i' E I, whereas for the set of intervals associated with an event, the conjunction of i E I, i' c i, and i' E I never occurs.

3 Unreifying Allen's Theory

A non-reified way of writing (1) and (2) would be

Kiss(john, mary, monday)

In(john, london, monday).

Why doesn't Allen do this? The semantics for these formulae would be isomorphic to the semantics suggested above for the reified syntax that Allen actually uses. Thus the predi­ cate Kiss would be mapped onto a relation between pairs of people and times, so that, in particular, the one-place pred­ icate Kiss(john, mary,_) would correspond to a set of times, i.e., the set of times which stand in the aforemen­ tioned relation to the referents of john and mary. Hence the predicate K iss(john, mary,_) naturally acquires an interpretation identical to what, in our plausible construc­ tion for the semantics of Allen's system, is ascribed to the term kiss(john, mary). A similar reduction holds for terms denoting properties.

4 Note that, contrary to what is often stated, McDermott's system does not use branching time: time itself is represented by the linear ordering of the real numbers; branching only occurs with respect to the totality of possible states ordered by date.

5 Axiom (01) only holds when Occur is understood to mean Occurs-on; but it is easily modified to apply to Occurs-in instead: Occur(e,t)-+ 3t'(Occur(e,t 1 )/\Vt"(In(t",t')-+ ...,Occur(e, t"))).

The non-reified system is less artificial than the reified one, sincetheallocationofthepredicate Kiss(john, mary,_) to a set of intervals comes out naturally as a consequence of the usual rules for specifying the semantics of a first-order lan­ guage, whereas the mapping of the term kiss(john, mary) onto a set of intervals has to be postulated ad hoc, there be­ ing nothing in first-order logic which constrains terms to be mapped onto sets of domain elements.

Since the non-reified version of Allen's notation has the advantages of greater simplicity and naturalness, Allen must have cogent reasons for not using it. His choice of represen­ tation might be justified if it enabled us to express important ideas which cannot be expressed without some unacceptable cost in a non-reified notation. The most plausible candidate for such a justification is Allen's handling of causation. Allen introduces a predicate Ecause (for event causation-i.e., one event causing another), with syntax Ecause( e1 , t 1, e2, t2). The intended meaning is that the occurrence of event e1 at time t1 causes the occurrence of e2 at t2, as, for example, in

The fundamental axiom governing Ecause is

To express these propositions in our suggested non-reified replacement for Allen's system, we should have to postu­ late something like a binary operator Ecause which forms a proposition out of two propositions, giving

and

But this new operator is not truth-functional, and hence can­ not be accommodated within first-order logic-in fact the semantics of Ecause becomes altogether problematic in this treatment, and this, surely, amounts to an unacceptable cost of unreification.

The solution to this problem lies, in fact, in unreifying Allen's theory in a different way from what was suggested above. Before looking at this, though, we shall examine another attempt at providing a reified temporal theory.

4 Shoham's Theory

Shoham [ 1986, 1988, 1990] is more hospitable to higher -order and modal logics than Allen is. He has criticised Allen's approach on the grounds that for the new language, but in fact we have given up the off-the-shelf FOPC and the associated model theory.

... the set of properties looks suspiciously like the set of first order formulas. If that is the case, then not only have we not given precise syntax and semantics

What Shoham doesn't like about Allen's properties is that Allen wants to allow them to have all the structural complex­ ity of first order formulae, so that he can say, for example, H olds(3z(¢(z)A t/l(z)), i). Here we should have to construe ¢and t/1 as denoting (base-level) functions which map objects onto "properties", 3z as a higher-order function which maps base-level functions onto properties, and Holds as a pred­ icate which maps property-interval pairs onto truth-values, though as Shoham notes, Allen does not, in fact, give precise semantics for these expressions.

Shoham 's approach is to introduce a set of primitive propo­ sitions and a predicate True which is in some ways analo­ gous to Allen's Holds; his atomic formulae are of the form True(tt, t2, p), where t1 and t2 denote instants, and the whole says that the primitive proposition p is true with respect to the interval (t1 , t2). Unlike Allen, however, Shoham does not allow the propositional argument of True to be logically complex. He does, to be sure, allow one to write things like True(tt, t2, Pt A -.P2) but this is just "syntactic sugar" for

Bacchus et al. [1989] have proposed a way to unreify Shoham's logic in a manner exactly parallel to the treatment of Allen's system suggested above: instead ofTrue(t1, t2, p), they write P( t1, t2). Semantically, P must get mapped onto a function from pairs of times to truth-values, or, equivalently, onto a set of pairs of times (i.e., the set of pairs of times which get mapped onto 'true').

In Shoham 's notation, the primitive propositional term p must be mapped onto some sort of object, while the predicate True is mapped onto a ternary relation between pairs of times and these "propositional" objects. Unlike Allen, Shoham is explicit about the formal semantics of his logic: the "proposi­ tional" objects onto which he maps his primitive propositions are in fact sets of pairs of times. The predicate True then gets mapped onto the membership relation, i.e., True(t1 , t2, p) is true just so long as the pair of times denoted by t1 and t2 belongs to the set of pairs of times denoted by p. In other words, the semantics Shoham gives for his reified theory is precisely analogous to the natural semantics that one would give for the unreified theory proposed by Bacchus et al.. At the semantic level, then, reification would appear to carry no advantages.

In [Shohaln, 1990], the reified logic is used to support inferences about causation. Unlike Allen, Shoham is quite happy to make use of modal operators 6 · He gives an example about what can cause the motor of a car to start, and what can prevent it from starting. He writes down axioms such as

D(t, t, dead-battery) -+ D(t, t, -.situation-normal-11).

6 For a critique of Shoham's use of modal operators in causal reasoning, see [Galton, 1991].

Here D(t, t,p) is an abbreviation for DTrue(t, t,p). These axioms can easily be unreified as

Shoham does nothing with his reified formulae that cannot be done with our non-reified ones; in particular, the inference he draws from his axioms, namely that 0(6,6, start-car), can also be drawn, in the fonn DStart-car(6, 6). Again, later on Shoham introduces what he calls some "meta-notation": he writes

to 'denote the fact that True(tt, t2, p) causes True(t3, t4, q) with respect to theory <I»'. He could just as well have written

todenotethefactthatP(tt, t2) causes Q(t3, t4) withrespectto theory <1». Nothing of substance would thereby be lost. Like­ wise, his Definition 7, in which the notation DCAUSES (for 'direct causation') is introduced, can be rewritten, with­ out loss of content, in unreified form. And since CAUSES and DC AU S E S are here "meta-notations", it is no argument against my paraphrases of Shoham that these capitalized ex­ pressions appear to function as higher-order predicates.

5 Some Ontological Considerations

Let us take stock of our results so far. We have noted that both Allen's and Shoham's reified theories can readily be unreified, but that in Allen's case there appears to be a price to pay, namely that in order to adapt the language he uses for modelling causal statements it is necessary to employ syntactic devices that go beyond the limits of first-order logic. In Shoham's case, this is not important, since he is in any case already committed to the use of modal operators in his analysis of causality.

Philosophically, the artificial and ad hoc nature of terms with propositional content, such as appear in the reified theo­ ries, is unacceptable; on the other hand, there is a clear need, both for philosophy and for AI, to express the causal notions discussed by Allen and Shoham. Our problem is how to do this without (a) philosophically dubious reification or (b) stepping outside the bounds of first-order logic.

We attack this problem by describing the semantics of ex­ pressions like Occur(kiss(john, mary), monday) in intu­ itive rather than formal, model-theoretic terms. Formally, the term kiss(john, mary) is, as we have seen, mapped onto a set of intervals; but intuitively this bears no relation to the mean­ ing of an expression such as 'John kisses Mary'. Intuitively, this expression ''refers to an event"; it does so in a generic way, i.e., what it picks out is an event-type, which abstracts a common core of meaning from the details which differentiate the numerous possible and actual occurrences of John's kiss­ ing Mary. The formula Occur(kiss(john, mary), monday) says that this event-type stands in a particular relation (that of occurrence) to the interval Monday-so that the generic event-type is, if you will, instantiated by a particular occur­ rence, an event-token which takes place on Monday.

We are thus led to consider the distinction between event­ types and event-tokens. The fonner, we might say, are uni­ versals, the latter are particulars. Now, if you had to choose between populating your ontology with event-types or event­ tokens, which would you go for? Unless you are an out-and­ out Platonist, you will surely choose event-tokens, exactly as, given the choice between species (such as lion, tiger, horse) and specimens (this lion, that tiger, these horses), none but a Platonist would choose the fonner. And yet the curious thing about the ontology implicit in Allen's theory is that while it includes state and event types, it has no place for state and event tokens.

Thus, taking Allen's formal language at face value, we find that he admits into his ontology the general event of John's kissing Mary, but not the particular instances of this event which are what actually occur. In order to state that John kissed Mary on Monday, Allen has to assert that a certain re­ lationship {the relationship of occurrence) holds between the general John-kissing-Mary event and (a certain subinterval of) the interval Monday. And to state that there is a causal con­ nection between two particular event occurrences, say John's kissing Mary at i and Mary's hitting John at i + 1, he has to introduce a four-place relation between the two event-types in question and the times at which the particular tokens of those types that we are interested in occur. It must be admitted that, presented in this way, Allen's theory takes on a rather bizarre appearance.

6 Reification of State and Event Tokens

An obvious alternative to reifying state and event types is to reify state and event tokens. This would have a much less Platonist feel to it, since we can with greater justice claim that individual occurrences are particulars (i.e., things in the world) than that general types of occurrence are. So on this scheme, we could have a term referring to a particular kissing of Mary by John, but not to the notion of John's kissing Mary taken in its full generality. Our sentence 'John kissed Mary on Monday' now receives a representation such as

(ignoring for now the complication about Monday not being a single day).

This kind of analysis was first proposed by the philosopher Donald Davidson [Davidson, 1967]. Davidson's primary mo­ tivation was to give an account in first -order logic ofinferences such as that from John kissed Mary in the kitchen on Monday to John kissed Mary on Monday. In Davidson's analysis, the inference becomes trivial: for

3e(Kiss(john,mary,e) 1\ In(kitchen,e) 1\ Occur(e, monday)) logically implies 3e(Kiss(john, mary, e) 1\ Occur(e, monday)).

Note in passing that neither Allen nor Shoham has anything to say about inferences of this kind, and it is not immediately clear how their systems would handle them.

If we drop the existential quantifiers (in effect, skolemiz­ ing), we obtain

which is essentially the kind of representation adopted by Kowalski and Sergot in the earlier part of their exposition of the Event Calculus [Kowalski and Sergot 1986].

With a notation such as this, we can now paraphrase Allen's predicate Ecause strictly within the confines of first-order logic. Where Allen writes Ecause( e, t, e', t'), we can write

The key idea here is that the causal relation holds between event-tokens, not event-types. That is why Allen introduced times as arguments of E cause, because it was only by doing so that he was able to secure reference to individual occurrences of his event-types.

Of course, one might wish to argue that a causal connection between event tokens depends on the existence of a general law connecting their respective types, and that the Ecause relation should therefore be between event-types rather than event-tokens. John's kissing Mary on this occasion caused Mary to hit John just because some causal law holds to the effect that whenever John kisses Mary she hits him 7 :

Here it is worth noting that there is no explicit mention of cause at all; the causal relation has been reduced to ('Humean') in­ variable succession. We can still define Ecause as a relation between event-tokens, treating Ecause( et, e2) as an abbrevi­ ation for any fonnula of the fonn

7 State Types in the Event Calculus

Although Kowalski and Sergot base their Event Calculus on an ontology of event-tokens rather than event-types, they still succumb to the temptation of reification. What they reify, though, is not event-types but state-types. Initially, they allow rules such as

which says that if e is an event of John's travelling to London, then there is an interval after( e), starting immediately after the time of e, during which it is true that John is in London. In short, the event of John's travelling to London initiates a period characterised by the holding of the state of John's being in London. They then go on to note that an event may initiate more than one state; for example, a particular occasion of John's travelling to London may also be an occasion of his travelling to England (e.g., he may be flying in from America). Thus we also have

where e can refer to the same event token as in the previous fonnula. But now what interval does after( e) refer to? Is it the interval during which John is in London, or the interval during which he is in England? The former may be a proper subinterval of the latter.

7 0f course this is over-simple; the ttue form of a causal law should mention background conditions that are required in order for the cause to be effective. See, for example, [Shoham 1990].

In order to resolve this difficulty, Kowalski and Sergot complicate their function symbol after by adding an extra argument to specify the state, initiated by the event, with which the interval is to be associated. This allows a general rule to be stated as follows

with instances of 'initiation' given by rules such as

Here Kowalski and Sergot have reified states, as, for example, with the term in(john, london), which refers to the state of John's being in London. Moreover, it is s~types that are here reified.

8 A Procedure for Unreifying Reified Types

In the same spirit of anti-Platonism that we have applied to Allen and Shoham's theories, can we unreify Kowalski and Sergot's state-types? Following the lead of Davidson, I wish to propose a very general strategy for avoiding philosophically unsound reification. Specifically, it is the reification of types that we want to avoid: we want the terms of our formal theory, as far as possible, only to refer to entities that can reasonably be regarded as individuals: individual physical objects, people, places, times, events, but not types of these things.

Suppose we have a theory containing a class T of terms whose intended referents are types. We want to replace it by a theory in which no such terms occur. Let us introduce instead a class T' of terms whose intended referents are the particular instances of the types denoted by elements ofT. Let P be a predicate in the original theory which applies to terms of type T. Then in the new theory we treat Pas applying instead to terms of type T', and in addition, for each element a in T, we introduce a new predicate A which applies to terms of category T'. If a has the form f(tt, ... , tn). where f is a function symbol and t 1 , ··· , tn are terms of a category allowed in the new theory, this is done by replacing f by a predicate F, of arity n + 1, whose first n argument places correspond to those off, and whose (n + l}th argument place is for a term of type T'.

We now replaceaformulaofthe form P(a) by 3z(A(z) /1. P( z )). This is just what we did to Allen's theory when we rewrote

as

Here P(_) is instantiated as Occur(_, monday), a as kis8(iohn, mary), and A(_) as Ki8s(john, mary,_).

If we apply the same procedure to the Event Calculus for­ mula

we obtain a formula

The term s here plays a role somewhat similar to that of a situation in the Situation Calculus [McCarthy and Hayes 1969], the difference being that a situation is supposed to incorporate the complete state of the world at a given time, whereas our 8 just refers to, for example, the circumstance of a particular person's being in a particular place over a particular period. It refers, in other words, to a state-token.

Unfortunately, there are problems about how to understand the notion of a s~token. Event-tokens are discrete, unitary individuals, each occupying a definite place and time; they are pretty well-individuated 8 · States, on the other hand, are much less clearly individuated(Cf. [Galton,l984], ch.2). For example, is the circumstance of John's being in London on Monday the same as the circumstance of his being in England on Monday? And if John is in London all day on Monday, how many individual s~tokens must we admit into our ontology? Just one, or infinitely many, corresponding to all the subintervals of Monday-each of which is, of course, a time of John's being in London?

I propose that we aim to make our ontology as sparse as possible. Thus we only posit state tokens to correspond to maximal stretches of a given state of affairs holding. By 'a given state of affairs' I mean an assignment of properties or relationships to a collection of objects. What we are allowed to count as a state of affairs is limited only by our ability to pick out a stretch of the history of some object or objects by means of some (possibly very complex) predicate which applies throughout that stretch. Given a state-token s, we define an interval time( 8) which is the full temporal extent of s. In addition, we define a predicate Holds, relating state­ tokens to times, in such a way that

Note that (ii) is not the same as Allen's (HI), since the former deals with state-tokens whereas the latter deals with state­ types ('properties'). Note also a certain symmetry between states and events. We can equally well apply the functor time to yield the interval over which an event happens; and our axiom for the predicate Occurs then ensures that the time of an event-token is minimal in just the way that (ii) above ensures that the time of a state-token is maximal:

Note that (ii) implies that Occurs is Occurs-in rather than Occurs-on.

It might be argued that we do not really need to treat state­ tokens and event-tokens as separate categories. Instead, sup­ pose we have a single class, of tokens. A token is speci­ fied by picking out the content of some chunk of space-time; we can be very liberal about what chunks of space-time are allowed-anything is in principle allowed, the only limitation is our ability to single out a particular chunk by means of some description that applies uniquely to it 9 · Then any token can, in principle, be treated either as an event-token or as a state­ token, according as we apply to it the predicate Holds or the predicate Occurs. Some tokens would more naturally lend themselves to being treated as states (e.g., an object's being in a certain position for a given period of time), others as events (e.g., an object's changing from one specified position to an­ other over a period of time); some, which correspond to the problematic category of processes, lend themselves equally well to being treated as states or as events (e.g., an object's rotating about an axis over a period of time).

1 But see [Davidson, 1969], for a discussion of some of the problems.

9 This is not to say, of course, that the world is not itself intrin­ sically structured: some chunks may be more naturally picked out than others.

The system proposed here bears some resemblance to that of Hobbs [1985]. In both systems, there are terms denoting state and event tokens, following Davidson [1967]. How­ ever, Hobbs and I reach this position from radically different ontological perspectives. My aim has been to purge some ex­ isting theories of excessive ontological liberality-my state and event tokens are ontologically more modest than the state and event types they are designed to replace. Hobbs, on the other hand, throws all ontological scruples to the winds, "al­ lowing as an entity everything that can be referred to by a noun phrase". As a result, he is prepared to countenance terms de­ noting such etherial entities as the quickness of the building of a boat. This is neither a state-token nor an event-token, and in particular it cannot be identified with a chunk of space-time. Hobbs introduces terms like this in order to handle reference in intensional contexts, a problem which I have not attempted to address in this·paper. Thus the apparent similarity between Hobbs' system and mine is only skin-deep.

We conclude this section with some examples of proposi­ tions which we can express using state and event tokens, but no types:

'John arrived at midday':

3e(Arrive(john, e) 1\ Occur( e, midday))

'John has arrived':

• 3e3s(Arrive(john, e) 1\ Result(e, s)l\ H olds(s, now))
• 'John arrived while Mary was asleep':
• 3e3s3i(Arrive(john, e) 1\ Asleep( mary, s)l\ Occur(e, i) 1\ Holds(s, i))

'Mary hit John because he kissed her':

• 3et3ez(Kiss(john, mary, e1 )A Hit( mary, john, ez) 1\ Cause(et, ez))
• 'Whenever John kisses Mary she hits him':
• VNe(Kiss(john, mary, e) 1\ Occur(e, i)--+ 3i'3e'(H it(mary, john, e') 1\ Occur(e', i')A Meets( i, i')))

I do not claim that these formulae capture the meanings of the English sentences exactly-just sufficiently closely to indicate the expressive potential of the formal language.

9 Concluding Remarks

In conclusion, then, what has been achieved? First, we showed how a reified temporal theory of the kind advocated by Allen can be unreified, admittedly with some loss of ex­ pressive power. We then noted that Shoham 's attempt to purge Allen's theory of what he saw as its undesirable features re­ sulted in a theory which, though it uses reified notation, is not really reified at all, the desired expressive power coming not from reification but from the use of modal operators. Next, we found that some of this expressive power can be recov­ ered in a first-order framework by using Davidson's device of event-token reification rather than event-type reification, as exemplified by part of Kowalski and Sergot's Event Calculus. This led us to propose a general method for converting type­ reification into token-reification, a result deemed philosophi­ cally desirable since tokens just are more suitable candidates for full ontological status than types. Finally we applied this procedure to the reified state-types which Kowalski and Ser­ got introduce into the Event Calculus, to yield a theory based on state and event tokens only. The expressive power of this theory was illustrated by means of a number of examples.