Issue 98033 Editor: Erik Sandewall 1.4.1998

Today

 

The discussion about the ontology of time started with a question to Jixin Ma. Today Jixin comes back into the discussion, together with an additional contribution by Pat Hayes.


Debates

Ontologies for time

Jixin Ma:

What follows is our response to the arguments about the ontology of time from Pat Hayes, Ray Reiter, and John McCarthy.

Response to John

The example of car accelerating demonstrates the need of time points for time ontology.

A similar example is throwing a ball up into the air. The motion of the ball can be modelled by a quantity space of three elements: going-up, stationary, and going-down. Intuitively, there are intervals for going up and going down. However, there is no interval, no matter how small, over which the ball is neither going up nor going down. The property of being stationary is naturally associated with a point, rather than any interval (including Allen and Hayes' moment), a "landmark" point which separates two other intervals.

Response to Ray

  During all the years that the debate has raged about time points vs intervals, we devotees of the sitcalc have never seen it as an issue.

It has already been an issue of the sitcalc. For instance, in Pinto and Reiter's 1995 paper, Reasoning about Time in the Situation Calculus, [j-amai-14-251], the concept of situation is extended to have a time span (an interval?) which is characterised by a starting time and an ending time (two points?). During the time span of a situation no fluents change truth value. Also, an action with duration is modelled with two instantaneous actions (start-action and end-action). So, all the debates about time points vs intervals apply here, and the Dividing Instant Problem still arises. In fact, all Ray's arguments show again, with his revised formulation of the sitcalc to accommodate temporal reasoning, either there is no way of expressing the claim that a proposition (like Light is on) is true or false at some time points, or one has to artificially take the unjustifiable semi-open interval solution. This is not surprise at all and is what one would expect, since the problem is actually there for the underlying time theory itself, and therefore would be there for any formalism which wants to support explicit time representation.

Response to Pat

  ...For example, the 1990 AIJ critique of Allen's account by Galton (wrongly) assumes that Allen's intervals are sets of points on the real line.

After re-reading Galton's paper [j-aij-42-159], as we understand, Galton's arguments are in general based on the assumption that Allen's intervals are primitive, rather than sets of points on the real line. In fact, the main revision Galton proposes to Allen's theory is a diversification of the temporal ontology to include both intervals and points. That is, in Galton's revised theory, intervals are still taken as primitive. Having pointed out this, however, as shown in Ma, Knight and Petrides' 1994 paper [j-cj-37-114], Galton's determination to define points in terms of the "meeting places" of intervals does not, as he claims, axiomatise points on the same footing as intervals, and hence that some problems still remain in these revisions.

  there does seem to be a simple, basic, account which can be extended in various ways to produce all the other alternatives, and this core theory is the one I was referring to.

Does this core theory refer that one in which "intervals are uniquely defined by their endpoints (which are also the points they fit between) and two intervals meet just when the endpoint of the first is the startpoint of the second"? Or Allen's one? - It seems the former one.

Anyway, yes. There does seem to be such a simple, basic core theory. For general treatments, in Ma and Knight's CJ 94 paper, [j-cj-37-114] a time theory is proposed (as an extention to Allen and Hayes' interval-based one) which takes both intervals and points as primitive on the same footing - neither intervals have to be constructed out of points, nor points have to be created as the places where intervals meet each other, or as some limiting construction of intervals. The temporal order is simply characterised in terms of a single relation "Meets" between intervals/points. Some advantages of this time theory are:

(1) It retains Allen's appealing characteristics of treating intervals as primitive which overcomes the Dividing Instant Problem.

(2) It includes time points into the temporal ontology and therefore makes it possible to express some instantaneous phenomenon, and adequate and convenient for reasoning correctly about continuous change.

(3) It is so basic that it can be specified in various ways to subsume others. For instance, one may simply take the set of points as empty to get Allen's interval time theory, or specify each interval, say  T , as   <T-leftT-right>   where  T-left < T-right , to get that one Pat prefers.

  The way I prefer, myself, is to say that propositions hold only during intervals, so that it is simply ill-formed to assert a proposition of a single point; but to allow the possibility of pointlike intervals, of the form  <t,t> , to be the temporal durations of propositions which are (intuitively) thought of as happening at a single 'point'. Or, put another way, some intervals may consist of just a single point, and some points may completely fill an interval. These pointlike intervals are the way that (this version of) the theory encodes the times when instantaneous truths hold. This doesnt require us to say that every point fills an interval, notice: since 'interval' is a basic predicate, it is perfectly consistent to say  ¬ interval( <tt> ) ; this would entail, for example, that nothing changed at that particular time. But it allows us to consider the proposition that a tossed ball's vertical velocity is zero, and assert that it is true at a single 'point', ie formally, that its interval of truth was pointlike. And since it is easy to characterise pointlike in the theory:
    ((pointlike i) iff ((begin i) = (end i)))

Yes, it's true. And, it seems that, all these can be reached equivalently by simply taking pointlike interval  <t,t>  as identical with point  t  in the case where both intervals and points are included in the time ontology.

  one can, for example, say something like
   ((illuminated i) or (dark i)))  implies (not (pointlike i))
so that the light is neither on nor off at the switching point. In this theory, every proposition has a 'reference interval' during which it is true, and a proposition might not be true of subintervals of its reference interval. (Though some propositions might be. This kind of distinction has often been made in the linguistic literature. Note however that this intuition is basically incompatible with the idea that an interval is identical to the set of the points it contains.)

This can be distinguished by applying  Holds_In  and  Holds_On  (that is Allen's Holds, see Galton's paper [j-aij-42-159]. Actually, as shown in Ma and Knight's 1996 paper [j-cj-37-114], to characterise the intuitive relationship between  Holds_On  and  Holds_In , in the case where intervals are allowed, some extra axiom is needed.

Also, it seems that, in Pat's formulation, for expressing that interval  <a,b>  is a subinterval of interval  <c,d> , one would have  c < a < b < d . In this case, we get that pointlike intervals  <a,a>  and  <b,b>  (or equivalently, points  a  and  b ) fall in interval  <c,b> .

  We certainly need something corresponding to 'points', I agree. I meant only that the formal theory can be crafted in the way Ive outlined above, or alternatively by identifying the pointlike intervals with their endpoints, and allowing a proposition to hold at a single point. This is in many ways more intuitively transparent but it is formally a bit more awkward, since pointlike isnt definable any more, and one has to put in special axioms forbidding points to meet each other. The 'reference interval' of a proposition could now be a single point in the theory. This is essentially the theory that Allen and I described in our 1985 paper [c-ijcai-85-528], though it takes a little work to see it.

On the one hand, many cases suggest the need of allowing a proposition to holds at a single point. For instance, see the example of throwing a ball up into the air described earlier in the response to John McCarthy.

On the other hand, allowing a proposition to holds at a single point doesn't necessarily make pointlike un-definable. It depends on if one would impose some extra constraints, such as

    ((illuminated i) or (dark i)))  implies (not (pointlike i))
as introduced by Pat for the light switching example, which actually leads to the assertion that the light is neither on nor off AT the switching point.

Actually, in the later version of Allen and Hayes's theory that appears in 1989 [j-ci-5-225], an awkward axiom is proposed to forbid moments to meet each other. It is interesting to note that, although moments are quite like points (moments are non-decomposable), they still have positive duration (they are not pointlike). Moments are included in Allen and Hayes' time ontology, while points are not. One of the reasons that such an axiom is awkward is that it doesn't catch the intuition in common-sense usage of time. In fact, in many applications, one would like to take some quantity as the basic unit of time. E.g., we may take a second as the basic unit. In other words, seconds are treated as moments - they cannot be decomposed into smaller units. However, for a given second, we may still want to express the next one, that is, a second can meet another second, although they are both non-decomposable.

  True, and indeed the Allen relations only have their usual transitivity properties when applied to intervals which are nonpointlike and forward-oriented. Of course both these are properties expressible in the theory, so that the Allen transitivity relationships can be stated there, suitably qualified. (When the alternative extension axioms are added, the qualifications become tautologous.)

...BTW, the claim that "meets" and "before" being exclusive is "intuitive" depends on how one's intuition is formed. Part of what I learned by having to construct alternative formalisations is that intuition is very malleable. Having gotten used to pointlike intervals, I dont find this exclusivity condition at all intuitive.

If the exclusivity condition is not intuitive at all, as Pat's claims, then why is is proposed for Allen's relations applied to intervals? Is it simply because they can be easily defined as exclusive when applied to nonpointlike intervals? Why not when applied to pointlike ones? (Simply because it cannot be conveniently defined?). Actually, in the case where both intervals and points are treated as primitive on the same footing, it is straightforward to extend Allen's 13 exclusive temporal relations between intervals to govern both intervals and points, while without losing the property of exclusivity. Vilain's [c-aaai-82-197] and Ma and Knight's [j-cj-37-114] systems are two examples.

  But these cases only make sense if one thinks of interval and points in the usual mathematical way, which is exactly what Im suggesting we don't need to do. We can get almost everything we need just from the ordering structure: we don't need to get all tied up in distinguishing cases which can only be formally stated by using all the machinery of real analysis.

The cases make sense not only if one thinks of intervals and points in the usual mathematical way. In fact, all the three cases are demonstrated under the assumption that both intervals and points are treated as primitive, rather than in the usual mathematical way.

  Again I was careless in using the word "knowledge", sorry. I should have said: in order to answer the question whether the light is on or off, one has to specify the interval with respect to which this question is posed. On this view, the truth or otherwise of a proposition is only meaningful with respect to certain intervals. I dont mean that the facts are determined by knowing more about the details of the interval, but that the question is a different question when asked about one interval than when asked about another, and for some intervals in may be simply meaningless. Is the light on or off at (exactly) 3.00 pm? The only way to answer this is to find a suitable non-pointlike interval of light or darkness completely surrounding 3.00 pm, because 'being on' is the kind of proposition that requires a nonpointlike reference interval.

But it seems that there are also some other kind of proposition to which one cannot assign any nonpointlike reference interval. For instance, in the throwing ball up into the air example, proposition "the ball is stationary" can only be true at points, and for any point we cannot find any non-pointlike interval (completely) surrounding it over which the ball is stationary.

  This has nothing to do with whether an interval is open or closed: in fact, there is no such distinction in this theory. It only arises in a much more complicated extension which includes set theory and an extensionality axiom for intervals.

In the time theory where both intervals and points are taken as primitive, we can (if we like) talk about the open and closed nature of intervals with some knowledge being available. This kind of knowledge can be given in terms of the Meets relation, rather than some "much more complicated extension which includes set theory and an extensionality axiom for intervals". In fact, we can define that:

  interval I is left-open at point P iff  Meets(PI

interval I is right-open at point P iff  Meets(IP

interval I is left-closed at point P iff there is an interval I' such that  Meets(I'I) ^ Meets(I'P

interval I is right-closed at point P iff there is an interval I' such that  Meets(II') ^ Meets(PI'

That's all, and it seems quite intuitive. For instance, with the knowledge  MEETS(PI which says that interval  I  is immediately after point  P , one can intuitively reach that point  P  is on the left of interval  I  and  P  is not a part of  I , and there is no other time element standing between  P  and  I . Therefore, we say interval  I  is left-open at point  P . Similarly, with knowledge  MEETS(II') ^ MEETS(PI', one can reach that point  P  is a part and the "finishing" part of interval  I , that is interval  I  is "right"-closed at  P .

It is important to note that the above definition about the open and closed nature of intervals is given in terms of only the knowledge of the  Meets  relation. However, if one would like to specify intervals as point-based ones, such a definition will be in agreement with the conventional definition about the open and closed intervals.

Jixin

Pat Hayes:

John McCarthy wrote:

  McCarthy and Hayes 1969 paper [n-mi-4-463] used time as a fluent on situations, i.e. time(s). ...

My chief motivation for this was the fact that the mapping from situations to times is many-one, since the sitcalc can distinguish different situations with the same clocktime. The differences between how precisely times are known, etc., can be handled by making the set of "times" obey different axioms. For example, in R-sitcalc the appropriate kind of time for a situation would be an interval of clocktimes, presumably; something like 'from 4.12 to 5.15'.

 My previous message gave a reason for including time points in a theory of events and actions. The theory could be founded so as to regard them as degenerate intervals, but I don't see any advantage in that, although I suppose the idea stems from the fact that people and robots can't measure time precisely.

Actually no. The motivation for introducing 'pointlike intervals' was just to maintain a certain expressive neatness, where all propositions, even instantaneous ones, are asserted w.r.t. a reference interval.

That idea - that intervals are approximations to points, and the length of an interval represents a degree of ignorance about the location of a point - gives a rather different ontology. In that case, for example, it doesnt really make sense to be able to refer to the precise endpoints or meeting-points of intervals (since if one can, then absolute precision about timepoints comes for free.) The Allen set of thirteen relations reduces to just six (before, overlap, inside, and inverses) since those that require endpoints to be exactly identified (meets, starts, ends, equal, endby, startby, meetby) are undefinable (except in an infinite limit.) This is the theory called 'approximate-point' in my time catalog. There arent any points in this theory, of course, though they could be defined if one added enough mathematical machinery to be able to talk about limits of infinite sequences.

Pat Hayes