Introduction
Reverse-engineering the "hidden logic" of time-sensitive systems is a critical task in modern engineering. At AAAI-21, a new approach was presented to learn these models directly from event logs. The proposed algorithm, TAG (Timed Automata Generator), learns deterministic Timed Automata by combining state-merging with a novel "transition division" strategy. This method achieves a superior balance between model simplicity and temporal precision compared to existing state-of-the-art (SOTA) methods.
The Challenge of Passive Learning
Many complex systems—ranging from industrial controllers to biological ecosystems—generate logs of timestamped events. To understand or verify these systems, researchers often use Timed Automata (TA). These are state-transition diagrams where transitions are gated by "clocks" and "guards." For example, a system might only transition to a new state if an event occurs within a specific time window.
Learning these models "passively"—using only logs without the ability to probe the system—is an NP-hard problem. Existing algorithms typically struggle with two issues:
- Over-generalization: Creating guards that are too broad, leading to high False Positive Rates (FPR).
- Over-complexity: Producing massive, non-deterministic models that are difficult for humans to interpret.
The TAG Algorithm
TAG addresses these issues through a two-phase process:
1. Conciseness and Determinism
The algorithm begins by constructing a prefix tree from the logs. It then merges states that exhibit the same "k-future" (identical behavior for the next $k$ steps). If a merge introduces non-determinism—where a single event could lead to multiple states—TAG continues merging until the model is deterministic.
2. Temporal Precision via Transition Division
The core innovation of TAG is "transition division." The algorithm identifies instances where the timing of an event alters subsequent behavior. If an event at time $t_1$ leads to a different future than the same event at time $t_2$, TAG splits the transition and its target state into distinct paths. This allows the model to capture precise temporal constraints that standard merging algorithms often overlook.
The resulting model is a PDRTA (Probabilistic Deterministic Real-Time Automaton) that remains concise while maintaining high sensitivity to timing.
Experimental Evaluation
The authors evaluated TAG using a synthetic benchmarking approach. A known Timed Automaton served as the ground truth to generate 1,000 positive event sequences (70% training, 30% testing). Additionally, 300 negative sequences were designed to test the False Positive Rate.
Key Results
In head-to-head testing against SOTA algorithms, TAG was the only one to achieve a perfect score across all metrics.
While RTI+ exhibited a high FPR (accepting 66 "illegal" sequences) and GenProgTA failed to recognize some "legal" sequences, TAG successfully reconstructed the exact target automaton with the optimal number of states.
Conclusion and Future Work
TAG demonstrates that selectively "splitting" transitions is as vital as merging states for learning accurate Timed Automata. By enforcing determinism, the algorithm ensures the resulting models are practical for formal verification and controller synthesis. Future work will focus on scaling the algorithm for massive real-world datasets and developing better distance metrics for model validation.
Summary updated