A Common-Sense Theory of Time

Introduction

The literature on the nature and representation of time is full of disputes and contradictory theories. This is surprising since the nature of time does not cause any worry for people in their everyday coping with the world. What this suggests is that there is some form of common sense knowledge about time that is rich enough to enable people to deal with the world, and which is universal enough to enable cooperation and communication between people. In this paper. we propose such a theory and defend it in two different ways.

First, the theory is powerful enough to include the distinction between "intervals" (i .e., times corresponding to events with duration), and "points" (i.e.. times corresponding to instantaneous events). as well as allowing substantial reasoning about temporal ordering relations (including the abilities described in [Allen, 1984]). l n addition, it includes a formalization of the beginning and ending of events by introducing the corresponding beginning and endings of times. We show that beginnings and endings act in many ways like "points," yet can be distinguished from them.

This research was supported in part by the Office of Naval Research under gram NOOO 14-80-C.l97. the National Science Foundation under grant OCR-8351665 and the US i\nny under grant Di\i\K2l84-C·0089.

A Common-Sense Theory of Time

James F. Allen and Patrick 1. Hayes Departments of Computer Science and Philosophy University of Rochester Rochester, NY 14627

Second, the theory has as allowable models a number of the temporal models that are suggested in the literature. This includes models that equate time with intervals and points on the real number line, models that hypothesize discrete time, and any model which mixes real points and intervals. Our claim is that if our common-sense theory of time excluded any one of these models, then there would be no debate as to whether that model was valid, since in that case our own primitive intuitions on the matter would be extremely clear. We do make one restriction on the models considered: they must allow the possibility that two intervals MEET, which is defined as the situation where there is no time between the two intervals, and no time that the intervals share. The importance of this relationship for naive theories of time has been argued elsewhere (e.g., [Allen. 1983: 1984]), and so will not be defended again here. Even with this requirement, we shall see that substantially different models are possible.

One important intuition which guides us is that time is occupied by events. lf the universe did not change. there would be no time. Any sort of event or happening which can be described or thought of has a corresponding time. and the universe of times consists of these. We will often appeal to this intuition, which notoriously sometimes indicates continuity and sometimes discreteness. (In particular. it is the source of the need to allow time intervals to be able to MEET.)

In Section I, we axiomatize a theory of time in terms of intervals and the single relation MEETS. It is then shown in Section II that this axiomatization subsumes the interval-based theory proposed in [Allen. 1983: 1984].

We then extend the theory in Section lil by formally defining the beginnings and endings of intervals and show that these have the properties we normally would associate with points. ln Section IV, a distinction is made between these point-like objects and the concept of moment as hypothesized in discrete time models. Finally, in Section V, we examine the theory in terms of each of several different models.

This paper is a condensed version of a report, [Allen & Hayes, 1985], henceforth referred to as the fonger paper, which presents additional discussion and the proofs for all the theorems below.

I. An Axiomatization of Interval Time

We start the formal development by positing a class of objects in our ontology that we shall call TIMES. These are intended to correspond to our intuitive notion of when some event occurs. We do not, at this early stage, make any committment as to whether all times are decomposable or not.

The essential requirement of our intuition above is that two time intervals can MEET. We will take MEET as our primitive relationship between times and show that we _can constructively define the complete set of possible relationships between intervals in terms of MEETS. Other reductions to a small set are possible; for example, Hamblin [1972] uses a relation we could define as less­ than-or-MEETS.)

For example, we can define a relationship BEFORE to hold between intervals only if there exists an interval that spans some time between them. Thus

As a notational convenience, we shall abbreviate conjunctions such as the above into a chain, i.e., I MEETS k MEETS J. We shall also use the abbreviations used in [Allen, 1983) for disjunctions between pairs of intervals. Thus "J (o oi s f d) I" is shorthand for the formula

(J OVERLAPS I) OR (J OVERLAPPED-BY I) OR (J STARTS I) OR (J FINISHES I) OR (J DURING 1).

All the possible relationships between times are defined in Figure 1. By including the inverses ?f th~se relations in the obvious way, we have thirteen relationships defined constructively in terms of MEET. Each entry defines the ordered relation between I and J (I BEFORE J, I OVERLAPS J, etc.). The inverses are also between I and J and are equivalent to the original relationship between J and I (e.g., I BEFORE J <= => J AFTER I, etc.). The small letters listed with each give the abbreviation for the relation that will be used later in some examples.

With this reduction, we can axiomatize the interval logic entirely in terms of the MEETS relation, as follows.

The first two axioms are based on the intuition that intervals have a unique beginning position and a unique ending position. As a consequence of this, if two intervals both meet a third interval, then any interval that one meets, the other meets as well.

Axioms for Uniqueness of"Meeting Places" :

The third axiom captures the notion of ordering. It simply states that given two "places" where two intervals meet, then these places are either equal or one precedes the other. This is axiomatized without referring to places as follows:

Ordering Axiom:

1. (i MEETS I) XOR
2. (EXISTS m . i MEETS m MEETS I) XOR
3. (EXISTS n . k MEETS n MEETSj)

In other words, we have exactly three possible cases, shown in Figure 2, for any four intervals i, j, k, and I.

Figure 2: The Three Possible Orderings of i, j, k, and I in Axiom M3

Finally, we need some existence axioms. First, given any interval, there exists an interval that meets it, and an interval that it meets, i.e.,

(M4) ALL i EXISTS j, k . j MEETS i MEETS k

A consequence of this axiom is that no infinite time intervals are allowed in our theory.

We need one more existence axiom, guaranteeing the existence of an interval which is the "union" or sum ( +) of two adjacent intervals, defined by:

Using the defined relations above, this axiom can be restated as

We can prove that when l+J exists it is unique, and that + is associative.

With these five axioms and the definitions given in figure 1, the entire transitivity table for interal relationships given in [Allen, 1983] can be derived. Thus, this set of five axioms concisely captures that logic. This is not to say, however, that an implementation should not use the expanded set of relations. There are some important efficiency gains from the larger set of primitives, as described in [Allen, 1983].

II. Nests: Beginnings and Endings

There are classes of events described in English that cannot be associated with a temporal duration. These are often called "instantaneous" events, or "accomplishments" (e.g., [Mourelatos, 1978]). Thus, we can say "I closed the door," but if we say "I closed the door for three hours," it means we are repeatedly performing the action (contrast "I sat on the floor."). Similarly, a click, or the flash of a strobe, cannot be qualified by a duration, Furthermore, the world after a click, or flash, could be essentially the same as before it, showing that these events cannot be idenlified with simple changes of state.

One common approach to handling the times for such events is to model them as points (real points in the conlinuous model; integers in the discrete model). In this section and the following one, we shall develop two distinct notions of points from our interval logic. These will be compared in the final section.

In this section we shall construct the equivalent of points within the interval logic defined in Section II by adopting a variant of filters, one of the standard mathematical constructions of points from intervals.

In particular, we define the beginning of an interval to be the set of all intervals that "touch the beginning" in any way, and the end similarly. We can define the ending of an interval similarly.

This can be defined solely in terms of the MEETS relation if one desires, but the above definition is simplest to understand. For convenience, we can define a nesl as a beginning or an ending, and can now define relations over the set of nests which show them to have the properties of points. We shall say a nest N is before a nest M iff there is at least one interval in N that is before some interval in M.

We show in the longer paper that nests have the important properties of points. The main result is that nests are totally ordered, i.e.,

Theorem 8: For any two nests N and M, either N < M, M < N or N = M

We can also show that the intuitive definitions of the interval relations in terms of nests are theorems. For example, we have

The second of these is especially important, as it shows that there is only one "place" where two meeting intervals actually meet. This is, perhaps surprisingly, a delicate matter. Very small changes in the definitions of BEGIN and END fail to achieve this. It is perilously easy to get a point structure, which distinguishes two "sides" of a single point, and other oddities, as discussed in [Van Benthem, 1982]. (We are grateful to Professor Dana Scott for bringing this and Hamblin's work to our attention, and emphasizing some of these subtleties.) We discuss this at greater length in the longer paper.

IV. Discrete Time and Time Points

We can now show that discrete time models introduce a different kind of "point" than the points that are defined above. In particular, discrete time hypothesizes times that are not decomposable. Let us introduce a distinction between true-intervals and moments as follows:

Thus. a true-interval has at least two sub-intervals (which might in turn be moments or true-intervals)--one that STARTS it and one that FINISHES.

Before we continue. it is important to remember that all of the earlier theorems were proven before any distinction was made between moments and true-intervals, so they all hold for both classes: none of the proofs ever depended on the decomposability of an interval. These definitions allow us to prove that two moments cannot overlap in any way, yet they can MEET each other. More precisely,

Let us now consider the relationship between nests and moments. The definition of nests did not exclude nests defined at the beginning or ending of moments. In fact. we can show that the beginning of a moment is before the ending of that same moment! Thus. although a moment cannot be decomposed, we can distinguish its beginning from its ending.

We can also show that moments and nests cannot be considered to be isomorphic · to each other. This is easily seen from the observation that moments can MEET each other. whereas nests cannot. Intuitively, a moment is a time during which some event (a flash, a bang) occurs. while a nest defines an abstract "position" in the sequence of times.

V. Discussion

It is interesting to interpret these ax1oms in various possible models. The simplest one is discrete time: intervals are pairs of integers <n,m> with n < m, and <n,m> MEETS <m,k>. Then a moment is a nondecomposable interval <n,n + l>, and nests pick out integers, the places "between" moments. In this model there is a clear distinction between moments and points. We can also define several models based on the real line. For example. time intervals can be mapped into open or closed real intervals: however, then times can never MEET. A simpler continuous model, based on the integer model above, defines time intervals as pairs of reals <a.b>. with <a.b> MEETS <b,c>. Following through the axiomatic definitions with this as a basis makes nests define points on the real line, as expected, but now there are no moments at all. since even the smallest interval is decomposable. We might try to extend the model to allow intervals of the form <a.a>, which would qualify as moments, but now consider <a.b>. <b,b> and <b.c>. By our definitions, the first MEETs the last. yet they have the second between them, so the first is BEFORE the last, violating the ordering axiom. We have tried to fit real. substantial-­ though very small--time intervals into merely mathematical "places." and they don't fit.

However. another possible model is one which mixes these, using the same definitions of interval and MEET (from which all else follows) but allowing pans of the time line to be discrete and pans to be continuous. Intuitively, if we have only coarse time measuring tools available, then we can treat time as discrete. but the possibility always remains of turning up the temporal magnification arbitrarily far. if we have access to events which can make the finer distinctions, distinctions which can split "moments" into smaller and smaller parts.

Our axiomatic theory allows all of these models and others: it is uncommitted as to continuity or discreteness of the sequence of times, yet is powerful enough to support a great deal of the temporal reasoning of common sense.