Short Time Periods

SHORT TIME PERIODS

Patrick J. Hayes Schlumberger Palo Alto Research 3340 Hillview

Palo Alto, CA. 94304

ABSTRACT

Earlier papers ( Allen and Hayes 1985,1986) described a compact axiomatic theory which provided a formal basis for temporal reasoning. This theory makes a sharp distinction between time points and periops of time. We show here, by considering possible models of the theory, that it can be slightly extended to give a better fit to intuition. In particular, the extended theory is preserved under changes of temporal granularity.

TIMEPERIODS AND MEETING

The original period theory (Allen 1984, Allen & Hayes 1986 ) used periods rather than points as its temporal primitive. ( The terminology used earlier was 'interval' rather than 'period'. We have changed to avoid confusion with the mathematical use of 'interval'. ) The thirteen possible relationships between periods, including for example overlapping, inclusion, and before are defined in terms of MEETS, which we will write as in infix colon, with p:q:r meaning p:q and q:r. The basic axioms of the theory are then

as follows:

• Ml forall p,q,r,s. p:q and p:s and r:q ) implies r:s

M2 forall p,q,r,s. p:q and r:s ) implies ( p:s

xor exists t. p:t:s

xor exists t. r:t:q

• M3 forall p. exists q,r. q:p:r
• M4 forall p,q,r,s. ( p:q:s · and p:r:s ) implies q-r

MS fora·ll p,q. p:q implies

exists r,s. r:p:q:s and r:(p+q) :s

These five axioms the theory makes. their implications and Hayes 1986 ). are all the assumptions which For a longer discussion of and justification, see ( Allen

A key intuition is that propositions are true or false during periods, rather than at points of time . This -overcomes the problem of the 'divided instant' (Van Bentham 1982). Consider switching on a light, so that the proposition "light on" is first false, then immediately true. If the timeperiods are thought of as sets of points, then only artificial constructions can avoid the dilemma of there being a point at which the light is neither on nor off ( or, worse, both on and off ) .

However, timepoints can be defined within the James F. Allen Computer Science University of Rochester Rochester, NY. 14627

theory as the 'places' where periods meet. In (Allen & Hayes 1986 ), a set-theoretic construction is given of points from periods, but we can introduce points directly, and it can be shown that the theory obtained is identical. We will use variable names u,v,w, .. for points, p,q,r, .:for periods, and introduce two functions START and END from pefiods to points.

• Pl forall p,q. p:q iff end(p)·start(q)
• P2 forall u exists p. u·end(p)

It is possible now to show that points, whatever they are, have all the properties one would directly expect, such as being a totally ordered infinite set with no limits.We could also start with points as the primitive idea and define periods as pairs of points from the totally ordered set. In ( Allen and Hayes 1986 ) we show how the natural construction of periods from points by forming pairs <u,v> is a proper inverse to the derivation of points from periods defined by these axioms, so that such intuitively compelling results as p·<start(p),end(p)> are provable from the axioms. These points, however, are mere mathematical abstractions, and not times at which an event occurs or when some proposition

is true.

POINTS AND MOMENTS

Points in time are pla·ces where periods meet, but they arent themselves periods, not even very short ones. A timeperiod is the sort of thing that an event might occupy: it has substance, while a point is merely an abstraction. Consider for example a ball tossed into the air on the one hand, and a flash of lightning on the other. The time of the balls flight can be divided into two periods, one of rising, the other of falling. The ball spends no actual time at the top of its flight: it does not hover there for a period, no matter how small. The periods of rising and falling MEET each other directly. The point at their meeting is a conceptual abstraction, not a real physical timeperiod. In contrast, the time taken by a flash of lighting, although pointlike in many ways, must be a period because it contains a real physical event. Other things can happen at the same time as the flash, such as a photograph being exposed or a horse dying. This is how we characterise such very brief moments of time:

forall p. Moment(p) iff not exists q,r. p·q+r

ie, a moment is indivisible into subperiods.

Moments have many of the properties of points. For example, if a period has moments at its ends then they are unique, and they uniquely define the period between them, by MS. But they also differ in many ways. For example, being periods, they have distinct endpoints.

The theory developed so far is somewhat unintuitive on this matter of truth at points and the qualities of moments. On one hand, some points seem to be natural receptacles of truth, and on the other, it is sometimes natural to treat a moment as being more pointlike. For example,the tossed balls vertical velocity is positive on the way up, negative on the way down, so must be zero somewhen, by the intermediate value theorem: and the point where these periods meet is the obvious candidate. Qualitative reasoning uses such points liberally, and it is hard to see how it could do without them. On the other hand, it seems unnatural to distinguish the start from the end of a lightning flash, but we must if it is to occupy more than a point.

We might try to rescue the formalism by 'inserting' a moment whenever a proposition needs to be true at a point. The intuitive argument here would be that since the ball is motionless, there must be a period- perhaps an 'infinitely short' one, whatever that means for it to be motionless in. But this leads to the dual problem: just as points are too small to be occupied by events, moments ( as we have defined them ) are too long to be suitably infinitesimal. Since a moment is a period, it has distinct endpoints, even though no points inside it. We cant identify these points without denying the existence of the moment itself, for to identify them is to claim that periods before and after the moment MEET, by Pl. Thus, the time the ball comes to rest and the time it starts to fall would be separated by an interval during which the ball would be hovering, an unacceptable consequence.*

we seem to need to be able to treat moments as points, and vice versa, to capture intuition better .

MAPPING MOMENTS INTO POINTS

Suppose we introduce a mapping which identifies the endpoints of moments, so that moments are mapped into points. This is what Hobbs (1985) calls a change of granularity. The tolerance relation which defines it in this case is that two periods are indistinguishable if their endpoints are at most a moment apart. We

can define this as follows:

forall u,v. u--v iff u-v

or Moment(<u,v>) or Moment(<v,u>)

forall p,q. p--q iff start(p)--start(q) and end(p)--end(q)

As Hobbs notes, the change of granularity is well-understood only in the case where the tolerance relation is transitive, and hence is an equivalence relation. It is easy to see that is transitive just when moments never meet:

M6 forall m,n. Moment(m) and Moment(n) implies not m:n

( for if two moments meet, then the start of the first does not -- the end of the second ) . If we add this to our axioms, then the extended theory is preserved under the blurring which introduces. We prove this by defining relations which 'imitate' those of the basic theory but with a moments 'blur' at their ends.

* This is sometimes what naive intuition predicts, in fact: the 'road-runner effect'.

forall p,q. p: :q iff end(p)--start(q)

or equivalently

forall p,q. iff p : q p: :q or exists m. Moment(m) and p:m:q or m-overlap(p,q)

forall p,q,m. p:q implies p++q- p+q and

( Moment(m) and p:m:q implies p++q - p+m+q

Now,let Ml' through M6' be rewriting Ml through M6 with ., + the · result oi and - replaced by::, ++and Then we have

THEOREM. Ml-M6 entails Ml'-M6'

The proof is elementary but tedious and omitted

here.

It is ·easy to see that if-- is the relation:: reduces to the similarly ++ becomes the same as axioms Ml'-M6' may ·be regarded as -- -equivalence classes. equality, then primitive : and + . Hence, the the theory of

This result shows that the theory with M6 applies uniformly at any level of coarsness in which moments are identified with their endpoints. We can reason about periods and move flexibly from one level of acuity to another, needing only a truth-maintenance system to keep track of the various granularity assumptions being made from time to time.

This seems to provide . a solution to the intuitive problems with which we began. A moment can be treated as a point, or vice versa, without changing the axioms of the temporal theory. The extended theory is stable under changes of scale. Notice that since the blurred relation .. includes the basic meets relation, we could use both relations in a description, and the theory would still be preserved under ::collapsing, so that we do not have to treat all the moments as points or vice vers~. Thus, in the balltoss example, the topmost point can be talked of as though it were a moment, but all other points retain their inferior status as real points which do not expand into moments and in which nothing can be asserted. Or as an alternative, we could claim that all points have this expandable status, and then be forced into describing the

door's status at the moment it closes.

Intuitive arguments for the reasonableness of M6 include the idea of perceptual acuity. When two dots are close enough, we perceive them as one. Imagine three dots x,y,z with x and y so close that they would seem dot-like if seen alone, and similarly y and z. One now perceives a short line, a dash . Two adjacent spatial 'moments' become a short, dense, 'period'. Adjacent 'moments' cannot be perceived. Similarly, for example, a succession of flashes with no periods between them are seen as a continuous light filling an period, which is why the movies work.

However, it is not yet clear what the models of the theory with M6 are. In the next section we will show that they are similar to the usual model of continuous time as .the rational or real

line .

The axiom M6 seems rather strange at first sight, since in the two most obvious categories of model of the basic theory, it is either vacuous or false. These are respectively the dense and discrete models. 'In the latter, time is clock time, a sequence of discrete ticks. While many nonstandard models exist, the simplest is of course the integers. In these models, every moment meets the next moment, and so M6 is as false as it can be, everywhere. On the other hand, in a dense model, every period can be split into consecutive subperiods, so no moments exist, and M6 is true but boring. However, there is a nontrivial class of models which are neatly

characterised by M6.

In a dense model, the points must form an unbounded dense linear order.If the model is countable { and one always is ) then this is the rational line, but everything here applies equally well to the reals. Periods then can be interpreted as open iptervals, with {a,b): {b,c) defining the meets relation. The fact that the intervals, considered as sets of points, dent contain their endpoints, is not relevant to the way in which they stand for periods in this model. An exactly isomorphic model is obtained by interpreting periods as closed intervals with [a,b]:[b,c], for example.

Notice however what happens if we include ALL rational intervals, open and closed, and try to define MEETing in the intuitively straightforward way which takes account of intervals as sets of points. Take for example the intervals

{a,b) {a,b] [b,c) {b,c)

called, say, p,q,r and s respectively. Then we would want it to be true that p:r and q:s, but not that p:s. It follows then { from M2 and a little work ) that there must be an period t such that p:t:s. The only candidate for such an period is the singleton {b), ie the closed interval [b]. Now this must be a moment, since evidently [b] has no subperiods. So this interpretation is not a model of the dense theory. On the other hand, it certainly is not isomorphic to the integers of the discrete model. In fact, this is a {rather extreme) example of a third class of interpretations, in which moments are intuitively point-like.

The general form of a .model of this sort - call it a PACKED model - over the rationals, is as follows. The domain of periods contains open rational intervals and perhaps some singleton closed intervals, and all intervals which can be generated by taking the interiors of the unions of the closures, and the simple concatenation, of other intervals. Thus if it contains {a,b) and {b,c) and [d], then it will also contain {a,c), {b,d] and {a,d], for example. MEETS is defined as follows: if [b] is not in the domain, then {a,b) :{b,c); but otherwise, meets is interpreted settheoretically, so that {a,b): [b]: {b,c) ,and {a,b]: {b,c), etc .. At one extreme, a packed model is simply a dense model when no closed singleton instants are present. At the other, it is the fully set-theoretical interpretation in which periods are rational intervals. But many others are possible., for example one in which the only singleton moments are the integers, or where parts of the line are dense, parts dense with moments; or where just a few isolated points are distinguished as being the interiors of moments.

These singleton intervals, being periods, have distinct endpoints. Thus in a crowded model, the axioms Pl, P2 assert the existence of 'points' on either side of a rational point: start{[a]) and end{[a]). The granularity-coarsening mapping defined ealrlier can be seen as making the claim that this distinction is irrelevant.

It follows from the earlier result that there is no way of formalising the distinction between these point-intervals and more substantial moments within the vocabulary of the time theory so far developed. One can see this intuitively by observing that any model which contains such instants can be replaced by a model i~ which instants are real intervals, simply by 'stretching' the line apart at those positions and inserting a gap. Exactly the same sentences in the language would be made true by such a stretched model, since these enlarged gaps would contain no meeting-points referred to by the sentences of the theory, so would be moments just as before: and the way they interact with the other periods will be unchanged. In order to express the distinction, we would need to introduce some way of talking about the size or duration of periods, and then point-intervals are

moments with no duration.

The overall picture .is this. The axiom M6 forces us to interpret moments as things with no extent, merely pointlike objects, and also exactly permits us to systematically treat them as points within the same theory, by a simple change of granularity. Thus there can be a moment during which the tossed balls velocity is zero, and we can consistently treat it as though it were a point. And when we examine the models of our assumptions, there turns out to be a single point, in fact, where the moment should be. And yet other periods can meet directly, when time is dense, without there being moments between them. So we can have our moments and eat

them.

ACKNOWLEDGEMENTS

We would like to thank Peter Ladkin for many instructive discussions. Much of this paper is based on insights found in {Van Benthem 1982) .