Temporal reasoning is a cornerstone of artificial intelligence, vital for tasks ranging from natural language processing to the verification of real-time systems. While many systems rely on point-based time, interval-based time offers a more intuitive framework for describing events with duration, such as "during a meeting" or "while eating."
The Challenge of Interval Logic
The primary framework for interval-based reasoning is Halpern-Shoham (HS) logic. It defines a comprehensive set of relations between intervals, such as overlaps, during, or starts.
Despite its expressive power, full HS logic is "undecidable," meaning no algorithm can consistently determine the logical consistency of a set of statements. To make this logic practical for AI, researchers seek "fragments"—restricted versions of the logic that remain useful while becoming computationally tractable. A significant gap in existing fragments is "referentiality": the inability to refer to a specific, unique interval (e.g., "the exact moment the alarm triggered").
Methods: Horn Clauses and Hybrid Machinery
This research introduces "well-behaved" fragments by combining two strategies:
- Syntactic Restriction (Horn Fragments): Utilizing Horn clauses—a restricted rule format (if $A$ and $B$, then $C$)—which are known for their efficiency in classical logic.
- Hybrid Machinery: Incorporating "nominals" (labels for specific intervals) and "satisfaction operators" (the
@symbol) from Hybrid Logic. This allows the logic to "jump" to and reference specific labeled intervals.
Complexity and the Logical Hierarchy
The paper provides a rigorous complexity analysis of these new fragments across various temporal semantics (e.g., continuous vs. discrete time). A key finding is the Expressiveness-Complexity Trade-off:
- The base Horn fragment ($HS^{\Box}_{horn}$) is highly efficient, falling into the P-complete class.
- Adding hybrid naming features increases complexity to NP-complete. While more demanding than P-complete, NP-complete remains manageable for many practical applications, unlike the undecidability of the full logic.
The hierarchy of these fragments is mapped out in a Hasse diagram, providing a roadmap for selecting the optimal balance between logical strength and computational speed.
Conclusion and Future Outlook
The primary contribution is the formal proof that hybrid Horn fragments like $HS^{\Box, i, @}_{horn}$ are NP-complete, regardless of whether time is viewed as dense or discrete. While this clarifies the complexity landscape, future work is needed to explore the "expressiveness gap"—determining exactly which real-world problems these fragments can effectively describe—and identifying specific application domains, such as robotics or database querying, where they excel.
Summary updated