TL;DR
This paper extends James Allen’s classic interval calculus to handle "non-convex" intervals—time periods with gaps, like "every Tuesday." By introducing formal primitives to dissect and combine these intervals, the author provides a robust framework for reasoning about intermittent events and standardized time units (years, months, days) within a unified logical system.
What Problem Does This Paper Address?
In the mid-80s, temporal reasoning in AI was largely dominated by James Allen’s interval calculus. While powerful, Allen’s model focused on convex intervals: continuous blocks of time without gaps. This works well for "the meeting lasted from 2 PM to 3 PM," but it fails for intermittent events, such as "the committee meets every Monday" or "the heater cycles on and off."
Peter Ladkin identifies a need for a "non-convex" calculus—one that can treat a collection of discrete time segments as a single logical entity. Furthermore, there was a lack of a formal, axiomatic way to handle standard time units (weeks, months, years) and map them to the abstract relations of interval logic.
Methods
The paper proposes an assertional definition of temporal primitives using Horn clauses, intended for implementation in the REFINETM system. The core approach relies on two new operators:
dissect(i): A selector that breaks a non-convex interval into its constituent "maximal convex subintervals" (the continuous chunks).combine(S): A constructor that takes a set of convex intervals and unions them into a single non-convex interval.
Ladkin uses these to define duration (the sum of the lengths of the parts) and diameter (the total span from the start of the first segment to the end of the last).
The paper also formalizes Standard Time Units using integer sequences. For example, [1986, 3, 21] represents a specific day. By defining how these sequences "meet" or "start" one another, the author builds a hierarchy from years down to seconds. To define a "week," the author uses an iterated "meet" relation ($\phi_7$) to specify a sequence of seven consecutive day-intervals.
Datasets
As a theoretical paper in formal logic and knowledge representation, no empirical datasets were used. The work provides a mathematical framework and a set of axioms rather than an experimental evaluation on a benchmark.
Key Insights and Ideas
- The Infinite Algebra: Unlike Allen’s convex algebra, which is finite (based on 13 atomic relations), Ladkin’s non-convex algebra is infinite. This provides the expressive power needed to describe complex, repeating temporal patterns.
- A-Series vs. B-Series: The paper bridges the gap between the "moving present" (A-series: past, present, future) and "fixed timestamps" (B-series). It treats
nowas a convex interval of "smallest granularity," allowing standard temporal logic operators (like $\Box$ and $\Diamond$) to be rephrased as interval relations. - The "Maxconsubints" Concept: By focusing on maximal convex subintervals, the author avoids the messy logic of overlapping segments within a single non-convex interval, ensuring a unique and clean representation for any set of time points.
- Hierarchical Units: Time units are not just labels but classes of intervals. A "Monday" is defined by its relationship to a specific reference point in the calendar hierarchy.
Key Results
- Axiomatization: The paper successfully provides a complete set of axioms for
dissect,combine,duration, andconvexify. - Temporal Logic Integration: It demonstrates how to define the temporal operators "always" ($\Box$) and "sometimes" ($\Diamond$) using interval relations like
overlapsandcontained-inrelative to afutureinterval. - Implementation: The primitives were integrated into the REFINETM system, a knowledge-based software environment, proving the framework's utility for practical AI applications.
Limitations and Future Work
- Linearity Assumption: The model assumes time is linearly ordered. While the author notes the work is "equally applicable" to branching time (common in planning), he admits that measure functions (like duration) would require significant modification to work in non-linear models.
- Granularity: The definition of
nowas an interval of "smallest granularity" is a pragmatic choice for AI systems but avoids the deeper philosophical questions of whether time is truly continuous or discrete. - Computational Complexity: While the paper provides the logic, it does not detail the computational cost of reasoning within an infinite algebra, which is typically much higher than in Allen's original 13-relation system.
- Future Work: The author points toward a more complete development of temporal logic within this interval framework, which was a work-in-progress at the time of publication.
Summary updated