Best-practice time point ontology for event calculus- based temporal reasoning Robert C. Schrag Digital Sandbox, Inc. McLean, VA USA bschrag@dsbox.com Abstract—We argue for time points with zero real-world time scale consisting of successive steps, two distinct instants duration as a best ontological practice in point- and interval- may be expressed by the same time point,” and also based temporal representation and reasoning. We demonstrate (unfortunately, apparently circularly) defines an instant as a anomalies that unavoidably arise in the event calculus when real- “point on the time axis.” We hope, by demonstrating world time intervals corresponding to finest anticipated calendar anomalies resulting from incorrect time point treatment and by units (e.g., days or seconds, per application granularity) are taken presenting effective correct implementation techniques, to (naively or for implementation convenience) to be time “points.” motivate future best-practice event calculus-based applications. Our approach to eliminating the undesirable anomalies admits durations of infinitesimal extent as the lower and/or upper II. EVENT CALCULUS ONTOLOGY AND AXIOMS bounds that may constrain two time points’ juxtaposition. Following Dean and McDermott, we exhibit axioms for temporal We have implemented a temporal reasoning engine for an constraint propagation that generalize corresponding naïve event calculus variant including the following ontological axioms by treating infinitesimals as orthogonal first-class elements. quantities and we appeal to complex number arithmetic • Time intervals are convex collections of time points— (supported by programming languages such as Lisp) for intuitively, unbroken segments along a time axis. straightforward implementation. The resulting anomaly-free operation is critical to effective event calculus application in • The ontological status of time points is an issue commonsense understanding applications, like machine reading. contended here. We argue that in the best practice they are taken to be instants with no real-world temporal Index Terms—temporal knowledge representation and extent, while naïvely (we argue incorrectly) finest reasoning, event calculus, temporal ontology best practices, anticipated calendar or clock units—which actually are temporal constraint propagation intervals—have been taken as time “points.” We take a time point to be a degenerate time interval—one I. INTRODUCTION whose beginning and ending points both are the time point itself. Machine reading technology recently has been applied to • Fluents are statements representing time-varying extract temporal knowledge from text. The event calculus [8] properties—e.g., the number of living children a presents appropriate near-term targets for formal statements person has. about events, time-varying properties (i.e., fluents), and time • The events of interest occur at individual time points points and intervals. While at least one implemented event and may cause one or more fluents to change truth calculus-based temporal logic [2] also has included calendar value. E.g., the event of adopting an only child will dates and clock times, most classical event calculus treatments cause the fluent hasChildren(Person, 0) to become address real-world time only abstractly. None so far has false and the fluent hasChildren(Person, 1) to become adopted the carefully crafted formulation of points (instants), true. intervals, dates, and times in Hobbs’ and Pan’s RDF temporal ontology [4]—which correctly treats all time units as intervals. Figure 1 exhibits axioms defining the predicates we use to We say, “correctly,” because the casual treatment of a calendar say when fluents “hold” (are true) and when events “occur” or clock unit as a time point unavoidably leads to undesirable (happen). anomalies. This point may be subtle—ISO standard 8601 [3] pertaining to representation of dates and times states, “On a holdsThroughout(fluent, interval) ↔ ∀(point): pointInInterval(point, interval) → holdsAt(fluent, point) holdsThroughout(fluent, interval) ↔ ∀(sub): hasSubInterval(interval, sub) ˄ holdsThroughout(fluent, sub) holdsAt(fluent, point) ↔ ∃(interval): intervalIsPoint(interval, point) ˄ holdsThroughout(fluent, interval) holdsWithin(fluent, interval) ↔ ∃(sub): hasSubInterval(interval, sub) ˄ holdsThroughout(fluent, sub) occursWithin(event, interval) ↔ ∃(point): pointInInterval(point, interval) ˄ occursAt(event, point) Figure 1. Axioms relating holds and occurs predicates. Variables appearing on the left-hand side of an initial implication are universally quantified. Variables introduced on the right-hand side are quantified as indicated. The predicates relating time points and intervals are defined in the appendix. Informally, a fluent holds throughout an interval I iff it A given event calculus application also will include axioms to indicate which transition events initiate or terminate which holds at every point and throughout every subinterval contained fluents, as summarized by Schrag [7]. We don’t need that by I. It holds (or occurs) within I iff it holds (or occurs) within some subinterval (or point) contained by I. much detail here, however, to demonstrate our concerns about undesirable anomalies arising from the naïve approach. In the naïve approach, it’s perfectly acceptable to assert that a fluent holds or that an event occurs “at” a specific “point” on III. ANOMALIES ARISING FROM THE NAÏVE TIME POINT the calendar or clock. We believe that under the preferred APPROACH approach, in which the only (true) points directly accessible delimit the boundaries of measured time units, such assertions We discuss the following anomalies. (or even queries) should be rare—perhaps limited to issues of A. Inability to order time points within a finest legal status (e.g., one reaches the age of majority at exactly represented time unit (e.g., a calendar day—see 12:00 midnight on one’s 21st birthday). Thus, we commend section A) preferred use of holdsWithin and occursWithin to replace naïve B. Inability to avoid inferred logical contradiction use of holdsAt and occursAt. when contradictory statements hold at different Besides being correct, the preferred approach is also more real-world times within a finest represented time robust. In the naïve approach, supposing an enterprise decides unit (see section B) to enhance its represented granularity from days to hours, it C. Inability to order real-world events occurring will need to replace all existing occurrences of holdsAt with within a finest represented time unit (see section holdsWithin (because its working definition of a “point” will C) have changed). As such, naïve approach users might as well D. Inability to avoid inferred logical contradiction avoid holdsAt and just use holdsWithin, which has equivalent when real-world events occur within a finest semantics when its interval argument is a time point. represented time unit and initiate contradictory fluents (see section D) The time map in Figure 2 illustrates these anomalies, as discussed in the following subsections. hasMaritalStatus(John, Married) hasMaritalStatus(John, Unmarried) hasMaritalStatus(John, Married) , , DivorceEvent(John, Sally) MarriageEvent(John, Mary) 12:00 AM A B 11:59 PM Figure 2. Time map illustrating naïve approach anomalies. Fluent observations (top) include fluents and the intervals throughout which they hold. Dark-filled points indicate that associated fluents are known not to hold beyond their intervals’ beginning or ending. Constraint graphics (with arrows) are defined in Figure 9, in the appendix. Transition event occurrences (middle) include the events and points where these occur. Contradictory fluents cannot overlap temporally, and, per event calculus convention, initiated fluent observations begin immediately after triggering transition events. The calendar (bottom) shows the initial and final minutes of a given day, plus two included time points, ordered as shown. D. Inability to order occurs statements initiating contradictory A. Inability to order time points fluents As is apparent in Figure 2, this basic problem underlies the Without the ability to order events, we don’t know whether other three listed above. In the naïve approach, the only way to any axiom proscribing polygamy has been violated or not. An order time points is to associate them with distinct finest implementation might take one position or another, depending calendar or clock units. Suppose days are the finest time unit on the order in which it happened to visit the transition events represented. We’d like to assert the point-wise temporal and to apply its rules for initiating and terminating fluents, relations (i.e., constraints) Figure 2 indicates, but in the naïve detecting contradictions, and propagating constraints. approach such constraints would be contradictory—all the points shown would resolve to the same calendar day’s time IV. TEMPORAL CONSTRAINT REPRESENTATION AND “point,” which cannot precede itself. This anomaly can be PROPAGATION particularly troubling in the representation of statements extracted by machine reading from news articles, which Compared to an application’s finest represented calendar or frequently exhibit only calendar dates but cover sequences of clock unit, available real-world information may be more or events occurring within single days. The option of discarding less precise. E.g., we may know the year that a given event such fine ordering information—and treating all within-day occurred but not the month or the day. If our finest represented events as if they were simultaneous—is equally problematic. units are days, this gives us an earliest and a latest possible date Rendering event orderings correctly is critical to representing on which the event could have occurred (the first and last days causality—just one fundamental element of a true of the year given). We use the notation distance(a, b, [x, y]) to commonsense understanding that machine reading is hoped indicate that the number of finest time units along a path from ultimately to support. time point a to time point b has as a lower bound x and as an Even when our representation isn’t fine enough to specify upper bound y. absolutely when during a given day (e.g.) a time point occurs, Rather than expose our system-internal time units, we when we can order the points, we can avoid contradictions provide a user interface in terms of calendar and clock units— resulting from an incorrect presumption of simultaneity. affording users source code-level robustness against future Absent total (or even partial) ordering, we also can still granularity enhancements. A distinguished calendar/clock hypothesize orders that might not lead to contradictions. point (e.g., the beginning point of the interval for 12:00 midnight, January 1, 1900) affords a reference against which B. Inability to order contradictory holds statements the distance to other dates/times is calculated. A person can’t be both married and unmarried at the same We refer to an asserted distance statement (or to a user- time, as would be required if all the constraint-linked points in provided statement from which it is derived) as a temporal Figure 2 were collapsed onto a single day “point.” In the naïve constraint. approach, it is (from a real-world perspective) as if we forced Real-world information also may give us only qualitative every marriage or divorce (indeed, every event) to occur at the information about the relationship between two time points— stroke of midnight. e.g., one is before or one is after the other. The following two figures exhibit axioms to define qualitative relations among C. Inability to order events time points—Figure 3 following the naïve approach, Figure 4 In the naïve approach, we can say that a person divorced the preferred one. (See also Figure 9 in the appendix for one spouse and married another on the same day, but we can’t graphical definitions of these relations.) Notice that the only say in what order these events occurred. difference between these two axiom sets is in their representation of the smallest possible distance between any two time points. In the naïve approach, it is one finest time unit. In the preferred approach, it is arbitrarily small—taken to be infinitesimal. timePointEqualTo(a, b) ↔ distance(a, b, [0, 0]) timePointLessThan(a, b) ↔ distance(a, b, [1, ∞]) timePointGreaterThan(a, b) ↔ distance(a, b, [–∞, −1]) timePointGreaterThanOrEqualTo(a, b) ↔ distance(a, b, [0, ∞]) timePointLessThanOrEqualTo(a, b) ↔ distance(a, b, [–∞, 0]) hasNextTimePoint(a, b) ↔ distance(a, b, [1, 1]) hasPreviousTimePoint(a, b) ↔ distance(a, b, [−1, −1]) timePointTouching(a, b) ↔ distance(a, b, [−1, 1]) timePointGreaterThanOrTouching(a, b) ↔ distance(a, b, [−1, ∞]) timePointLessThanOrTouching(a, b) ↔ distance(a, b, [–∞, 1]) Figure 3. Axioms defining qualitative relations between time points in the naïve approach, where finest time units are treated as “points” and the smallest possible distance is one such time unit timePointEqualTo(a, b) ↔ distance(a, b, [0, 0]) timePointLessThan(a, b) ↔ distance(a, b, [ϵ, ∞]) timePointGreaterThan(a, b) ↔ distance(a, b, [–∞, −ϵ]) timePointGreaterThanOrEqualTo(a, b) ↔ distance(a, b, [0, ∞]) timePointLessThanOrEqualTo(a, b) ↔ distance(a, b, [–∞, 0]) hasNextTimePoint(a, b) ↔ distance(a, b, [ϵ, ϵ]) hasPreviousTimePoint(a, b) ↔ distance(a, b, [−ϵ, −ϵ]) timePointTouching(a, b) ↔ distance(a, b, [−ϵ, ϵ]) timePointGreaterThanOrTouching(a, b) ↔ distance(a, b, [−ϵ, ∞]) timePointLessThanOrTouching(a, b) ↔ distance(a, b, [–∞, ϵ]) Figure 4. Axioms defining qualitative relations between time points in the preferred approach, where all time units are treated as intervals and we use an infinitesimal (denoted ϵ) to separate points that are (in the limit) “adjacent” Both approaches use infinity (denoted ∞) to represent the difference between the two approaches’ computational largest possible distance between time points. Handling this in complexity for constraint propagation is that the preferred temporal constraint propagation (computing tightest distance approach enables finer (and thus more numerous unique) bounds, considering all constraints) requires axioms defining constraints. non-standard arithmetic, as in Figure 5. Figure 6 exhibits Implementation is straightforward for addition and axioms for the constraint propagation process in which Figure arithmetic negation in a programming language such as Lisp 5’s arithmetic axioms are applied. Note that all but the last of that supports complex numbers and arithmetic. While complex Figure 5’s axioms handle only the infinities specially. By numbers with unequal real and/or imaginary parts are treating the positive infinitesimal denoted ϵ as the imaginary incomparable with respect to magnitude, in our imaginary-as- number i (as in [2][5][6]) and by appealing to complex infinitesimal interpretation the real parts always dominate and arithmetic, we can use the same axioms to support propagation the imaginary parts are compared only when the real parts are in both approaches. equal—per the last axiom defining finite>, in which the Note that in the naïve approach using only real numbers all predicates real>, real=, and imaginary> invoke the indicated the imaginary parts will be zero. The only substantive comparisons on the real and imaginary parts of their arguments. infinite(–∞) infinite(∞) infinite+(–∞, –∞, –∞) infinite+(∞, ∞, ∞) infinite+(a, –∞, –∞) ← ¬infinite(a) infinite+(–∞, b, –∞) ←¬infinite(b) infinite+(a, ∞, ∞)← ¬infinite(a) infinite+(∞, b, ∞) ← ¬infinite(b) infinite+(a, b, a + b) ← ¬infinite(a) ˄ ¬infinite(b) infinite–(–∞, ∞) infinite–(∞, –∞) infinite–(a, –a) ← ¬infinite(a) infinite>(∞, –∞) infinite>(a, –∞) ← ¬infinite(a) infinite>(∞, b) ← ¬infinite(b) infinite>(a, b) ← ¬infinite(a) ˄ ¬infinite(b) ˄ finite>(a, b) finite>(a, b) ← real>(a, b) ˅ (real=(a, b) ˄ imaginary>(a, b)) Figure 5. Axioms supporting constraint propagation arithmetic (addition, subtraction, and comparison) over temporal duration bounds of infinite extent distance(b, a, [–y, –x]) ↔ distance(a, b, [x, y]) ˄ infinite–(x, –x) ˄ infinite–(y, –y) distance(a, b, [w, y]) ← distance(a, b, [x, y]) ˄ distance(a, b, [w, z]) ˄ infinite>(w, x) distance(a, b, [x, z]) ← distance(a, b, [x, y]) ˄ distance(a, b, [w, z]) ˄ infinite>(y, z) distance(a, c, [mo, np]) ← distance(a, b, [m, n]) ˄ distance(b, c, [o, p]) ˄ infinite+(m, o, mo) ˄ infinite+(n, p, np) Figure 6. Axioms for propagating lower and upper temporal bounds to infer tightest bounds considering all constraints [6, 8] [1, 1] [6–2ϵ, 7+ϵ] [2ϵ, 1–ϵ] [ϵ, 1–2ϵ] [ϵ, 1–2ϵ] [ϵ, 1–2ϵ] [ϵ, ∞] [ϵ, ∞] [ϵ, ∞] [5, 7] Day 1 A B Day 2 C Figure 7. Raw (solid arrow) and inferred/propagated (dashed arrow) constraints, with lower and upper bounds, in the preferred approach. Constraints have directions indicated by arrows (all oriented from left to right) A to Day 2, as well as many inferred constraints relating pairs V. HOW THE PREFERRED APPROACH AVOIDS ANOMALIES of points not connected in the figure. The two-dimensional (in To see how constraint propagation works—and avoids the implementation, complex) arithmetic treating infinitesimal anomalies—in the preferred approach, see Figure 7, which and non-infinitesimal quantities orthogonally effectively supposes days are our finest time unit. maintains qualitative point ordering—both within finest represented calendar or clock unit boundaries (e.g., relating By way of raw constraints, we know that points A and B points A and B) and across them (relating B and C). See both fall between Day 1 and Day 2, that A follows B, and that Figure 8. point C is between five and seven days after Day 2. For clarity, Figure 7 omits the [ϵ, ∞] constraint from Day 1 to B and from [6–2ϵ, 8–2ϵ] ϵ ϵ 1–2ϵ [5, 7] Day 1 A B Day 2 C [5+ϵ, 7+ϵ] ϵ 1–2ϵ ϵ [5, 7] Day 1 A B Day 2 C [5+ϵ, 7+ϵ] 1–2ϵ ϵ ϵ [5, 7] Day 1 A B Day 2 C Figure 8. Extreme cases for the time points A and B in Figure 7, including (at the extremes) greatest lower and least upper bounds in the inferred constraints shown there As we explained in section III, resolving this time point ordering anomaly simultaneously resolves the other three REFERENCES anomalies described there as well. Now, we also can order the [1] J. Allen, “Maintaining knowledge about temporal intervals,” in events that occur at time points and avoid spurious Communications of the ACM. 26, pp. 832–843, November 1983. contradictions that arise from the naïve approach’s inability to [2] T. Dean and D. McDermott, “Temporal data base management,” order events and fluent observations. When our finest time Artificial Intelligence, vol. 32, pp. 1–55, 1987. units are days, we no longer have to pretend that all events [3] International Standards Organization, “Data elements and occur at the stroke of midnight. With appropriate ordering of interchange formats—information interchange—representation of events, we’ll be able to put machine reading in a better position dates and times,” international standard ISO 8601:2004(E), third to support commonsense understanding of causality. edition, 2004. [4] J. Hobbs and F. Pan, “An ontology of time for the semantic web,” VI. SUMMARY ACM Transactions on Asian Language Information Processing, We have demonstrated temporal reasoning anomalies that Vol. 3, No. 1, pp. 66–85, March 2004. arise when implementation of the event calculus naively [5] R. Schrag, J. Carciofini, and M. Boddy, “Beta-TMM Manual follows classical treatments that casually treat finest (version b19),” Technical Report CS-R92-012, Honeywell SRC, represented calendar or clock time intervals as “points.” We 1992. have presented axioms and described implementation [6] R. Schrag, M. Boddy, and J. Carciofini. “Managing disjunction techniques to resolve these anomalies when all time intervals for practical temporal reasoning,” in Principles of Knowledge are correctly treated as time intervals and when time points are Representation and Reasoning: Proceedings of the Third taken to be instants with zero real-world duration extent. We International Conference (KR-92), pp 36–46, 1992. argue that this preferred approach, rather than the naïve one, is [7] R. Schrag, “Exploiting inference to improve temporal RDF needed for the event calculus to be useful in applications, like annotations and queries for machine reading,” 7th International machine reading, intended to support commonsense Conference on Semantic Technologies for Intelligence, Defense, understanding including causality. and Security (STIDS), 2012. [8] M. Shanahan, “The event calculus explained,” in Artificial ACKNOWLEDGMENT Intelligence Today, ed. M. Wooldridge and M. Veloso, Springer Lecture Notes in Artificial Intelligence no. 1600, pp.409–430, Thanks to other participants in DARPA’s Machine Reading 1999. research program that supported our temporal reasoning implementation—especially to other members of the SAIC APPENDIX: TIME POINT AND INTERVAL RELATIONS evaluation team, including Global InfoTek (the author’s former The set of predicates illustrated in Figure 9 (repeated from employer). Figure 4) supports every qualitative binary time point relation over the time point distance landmark values indicating equality, adjacency, and lack of constraint above or below. (A user also may specify arbitrary bounds on the number of time units intervening between any two points.) As illustrated in Figure 10 selected examples, this point orientation yields a much broader set of qualitative interval relations than does Allen’s classical formalism [1], which is purely interval oriented, without points. [lower, upper] bounds on the calendar or clock distance (in the preferred approach) from time point S to time point O Subject on top timePointEqualTo(S,O) [0, 0] marked Object on bottom timePointLessThan(S,O) [ϵ, ∞] time points may not coincide. timePointGreaterThan(S,O) [−∞, −ϵ] timePointLessThanOrEqualTo(S,O) [0, ∞] , marked time points are timePointGreaterThanOrEqualTo(S,O) [−∞, 0] consecutive. hasNextTimePoint(S,O) , [ϵ, ϵ] hasPreviousTimePoint(S,O) ‘ [−ϵ, −ϵ] ∞ = Infinite ‘ duration timePointTouches(S,O) ‘ [−ϵ, ϵ] timePointLessThanOrTouching ‘ [−ϵ, ∞] ϵ = Infinitesimal timePointGreaterThanOrTouching ‘ [−∞, ϵ] duration pointInInterval pointIsInterval Figure 9. Qualitative relations over time points, with graphical icons that we use to illustrate the definitions of point-and-interval relations (here) and interval-interval relations (in Figure 10). Such illustrated definitions include beginning and ending points super-imposed on interval icons, to elucidate the constraints. hasSubTimeInterval(S,O) timeIntervalBefore(S,O) timeIntervalStarts-X(S,O) timeIntervalFinishedBy(S,O) timeIntervalMeets-X(S,O) , timeIntervalOverlaps(S,O) timeIntervalEquals(S,O) timeIntervalIntersects(S,O) ‘ ‘ ‘ timeIntervalTouches(S,O) ‘ Figure 10. Selected relations over time intervals (with defined time point relations indicated)