Abstract
Traditional temporal reasoning models, such as Allen’s Interval Calculus, often face computational bottlenecks due to their reliance on complete graphs. This paper proposes Sequence Graphs, a sparse representation designed for technical domains where events follow a linear flow. By leveraging sequence chains and monotony properties, the proposed model significantly reduces memory and processing overhead while maintaining logical consistency.
Introduction
In the early 1990s, James Allen’s Interval Calculus became a cornerstone for representing temporal relationships in AI. However, its requirement for a complete graph—where every pair of $n$ intervals must have an explicit relationship—leads to $O(n^2)$ complexity. In large-scale technical systems like factory monitoring or power plant management, this "computational explosion" in both memory and processing time hinders real-time performance.
Jürgen Dorn argues that technical processes are inherently sequential. Calculating the relationship between distant events (e.g., an event on Monday and one on Friday) is often redundant if they are linked by a chain of intermediate steps. The Sequence Graph addresses this by providing a sparse yet sufficient representation that avoids the overhead of a complete graph.
The Sequence Graph Approach
The core of the proposed method is the reduction of explicit relations through two key concepts:
- Sequence Chains: These are paths in the graph where intervals are strictly ordered (e.g., Task A meets Task B). Transitivity allows the system to deduce that A is before C without storing an explicit edge.
- Monotony: This property allows the system to identify "weaker" constraints that do not require full transitive closure updates, further streamlining the propagation algorithm.
By focusing on "comparable" intervals—those explicitly connected or part of the immediate temporal flow—the system avoids checking every node in the database during updates. This approach shifts the computational burden from storage at update time to search at query time, which is more efficient for technical monitoring.
Efficiency and Implementation
The Sequence Graph maintains efficiency by proactively deleting "superfluous" edges that are already covered by the transitivity of the sequence chain. This keeps the graph lean and improves the speed of constraint propagation.
In a practical evaluation involving a steelmaking plant's scheduling system with 31 intervals, a standard complete graph would require 496 edges. The Sequence Graph approach reduced this to just 143 edges, representing a nearly 70% reduction in storage requirements and a significant boost in computational efficiency.
Results and Discussion
The reduction in edge count directly translates to faster updates in real-time monitoring scenarios. Despite the "incomplete" nature of the graph, the author proves that the system remains robust, identifying all logical inconsistencies and ensuring information integrity for safety-critical applications.
However, there is a trade-off: querying the relationship between two distant intervals is no longer an $O(1)$ operation, as it may require a path search through the sequence chain. In technical domains, where updates are frequent and long-range queries are less common, this is a favorable compromise.
Conclusion
Sequence Graphs offer a scalable alternative to complete temporal models for technical applications. Future work aims to integrate quantitative data (exact durations) and handle inexact reasoning more effectively, bridging the gap between qualitative logic and precise engineering requirements.
Summary updated