Runtime Verification under Split Past and Future
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: I'm Tom.
Jane: And I'm Jane, here with Lu, Meng and our in-house large language model, Lalam.
Tom: We're looking at the paper: "Runtime Verification under Split Past and Future".
Paper summary: Tom: We’ve talked about the setup, but I want to get back to the basics of what this paper is actually trying to achieve with "Runtime Verification under Split Past and Future." It claims that traditional verification only checks the history, so this new approach combines monitoring observed execution with analyzing multiple predicted continuations >
Jane: Right. The main innovation is Split Linear Temporal Logic, which gives a single specification both past and future requirements evaluated relative to the current time point >
Lu: They define a SplitLTL rule as a pair of formulas where one is in PastLTL and the other is in FutureLTL, with the satisfaction defined as an "or" relationship between them >
Meng: So, when you look at a specific time point, say t over behavior w, it's satisfied if either the past component holds for the actual execution up to that point or if one of the predicted futures holds against its future requirement >
Lalam: They outline this framework by assuming the system provides one or more predicted trajectories describing its future states and environment over a finite prediction horizon at each time point >
Tom: The key action they take is evaluating each of those predicted trajectories against the future-time requirements only for those rules whose past-time requirements are already satisfied by the actual execution prefix >
Jane: This means they filter out any predicted trajectories that violate the requirements, leaving you with a set of continuations that are consistent with the specified assurance conditions >
Lu: The semantics for these time points, like "Y" and "X," are defined relative to immediately preceding and succeeding time instants respectively >
Meng: They use reflexive semantics for modalities like "S" and "U," meaning the current time instant can act as the witness if it meets the conditions >
Lalam: The paper shows that common temporal modalities, like "P" for sometime in the past or "G" for always, are treated as syntactic abbreviations that you can use directly in your specification >
Tom: So, to summarize: they use SplitLTL to separate past and future needs and filter predicted futures based on what's already happened >
Jane: It really matters because it allows you to verify safety properties not just against what has occurred, but also against the set of behaviors the system is currently planning >
Conclusion: Tom: So wrapping up this paper, "Runtime Verification under Split Past and Future" by Dogan Ulus. It’s about moving beyond just checking the past to actively using predicted futures to ensure safety during runtime >
Jane: It’s a framework that introduces SplitLTL to handle those two temporal aspects in one go, which is a general pattern for integrating monitoring with prediction-based decision making >
Lu: The implication is that you can create a specification-based layer that operates between prediction, monitoring, and the actual decision making process in autonomous systems >
Meng: For deployment at scale, they’re focusing on how efficient the monitoring infrastructure is because modern systems generate a lot of candidate behaviors over long horizons >
Lalam: The work suggests that runtime verdicts from these predicted behaviors can serve as feedback to guide or refine the prediction mechanisms in subsequent control cycles >
Bogazižci University
cs.LO
Submitted: 2026-08-21
Updated: 2026-11-17
Comments: In Proceedings FMAS 2026, arXiv:2611.21375
Journal ref: EPTCS 457, 2026, pp. 46-53
DOI: 10.4204/EPTCS.457.4
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 83/100
The gist: Runtime Verification under Split Past and Future proposes a formal framework that combines monitoring of observed execution with analysis of multiple predicted continuations to support runtime…
Key concepts
- SplitLTL
- A temporal logic that splits specifications into past (PastLTL) and future (FutureLTL) requirements. A rule is satisfied if the system satisfies the past requirement OR the future requirement, which is equivalent to saying it must satisfy both in sequence.
- Monitoring Architecture
- An architecture where separate monitors handle past and future checks. Past-time monitors track observed history incrementally, while future-time monitors evaluate a set of predicted behaviors against their corresponding requirements at each time step.
- Temporal Symmetry
- The idea that future-time formulas can be transformed into past-time formulas by reversing the temporal direction. This symmetry allows the system to reuse monitoring infrastructure efficiently for both past and future checks using the same underlying tools.
Terminology
Summary
Runtime Verification under Split Past and Future proposes a formal framework that combines monitoring of observed execution with analysis of multiple predicted continuations to support runtime assurance in autonomous systems This approach introduces Split Linear Temporal Logic (SplitLTL), a linear-time temporal logic that assigns complementary roles to past and future temporal specifications within a single specification The framework filters predicted continuations according to the requirements induced by the observed history, identifying admissible continuations that can support subsequent decision making
The core concept of SplitLTL
SplitLTL is introduced as a linear-time temporal logic that separates a specification into past and future requirements evaluated relative to the current time point A splitLTL rule is defined as a pair of formulas where one component is in PastLTL and the other is in FutureLTL The satisfaction of a SplitLTL rule φ = (ϕpast, ϕfuture) at time t over behavior w is defined by (w,t) ⊨ φ ⇐⇒ (w,t) ⊭ ϕpast ∨(w,t) ⊨ ϕfuture This formulation is semantically equivalent to the LTL formula ϕpast → ϕfuture
The monitoring architecture
The proposed framework outlines an architecture where a separate past-time monitor evaluates the antecedent and a future-time monitor assesses the consequent of each rule in the formula The observed history is fed incrementally to all past-time monitors, which update their internal states without reprocessing the entire history At each time point, a set Ct of predicted future behaviors is provided to the monitoring framework The future-time monitors evaluate each predicted behavior c ∈ Ct against the corresponding future-time requirement and produce a verdict for each behavior
Efficiency through temporal symmetry
The authors exploit the temporal symmetry between past-time and future-time fragments of LTL to reuse monitoring infrastructure A future-time formula ϕfuture can be transformed into a corresponding past-time formula ϕ′past = rev(ϕfuture) by reversing the temporal direction and replacing future-time operators with their past-time counterparts Given a predicted behavior, the past-time monitor M(rev(ϕfuture)) constructed from the reversed formula processes its states in reverse temporal order starting from the last state and proceeding to the current time point This symmetry allows for reusing high-performance monitoring infrastructure for both past- and future-time formulas
Practical implementation details
The framework is implemented using Reelay, an online runtime verification library for past-time temporal logic specifications Reelay employs sequential network-based past-time monitors for efficient online monitoring The authors construct Reelay monitors directly from the past-time component of each rule and share monitors for common subformulas across rules whenever possible This sharing provides an efficient foundation for the past-time monitoring component of the framework
Future directions and learning integration
The paper suggests that runtime verdicts for predicted behaviors can be used as feedback to guide or refine prediction mechanisms in subsequent control cycles This creates a feedback loop where formal monitoring informs future prediction while remaining an independent assurance layer The architecture allows runtime verification to support learning-based prediction without requiring the prediction mechanism itself to provide formal guarantees The performance of monitors becomes critical as modern autonomous systems may generate thousands of candidate behaviors over prediction horizons up to 30 seconds
Conclusion on generality
SplitLTL is presented as a general pattern for integrating temporal-logic monitoring with prediction-based decision making The approach is not tied to a particular temporal-logic formalism and can accommodate other formalisms whose specifications admit past- and future-oriented components with efficient monitoring procedures This makes SplitLTL a specification-based assurance layer that can operate between prediction, monitoring, and decision making in autonomous systems The computational cost of monitoring grows with the number and length of predicted behaviors
AI Usage Disclosure
Generative AI tools were used to assist with language editing, proofreading, and improving the clarity and organization of this manuscript The author reviewed and verified all AI-assisted content and remains fully responsible for its accuracy, originality, and integrity
References
[1] Howard Barringer, Michael Fisher, Dov M Gabbay, Graham Gough & Richard Owens (1989): METATEM: A Framework for Programming in Temporal Logic. In: Stepwise Refinement of Distributed Systems, Models, Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings
[2] Arinç Demir & Dogan Ulus (2026): Multi-Property Temporal Logic Monitoring. CoRR abs/2605. p. 6 [2] Arinç Demir & Dogan Ulus (2026): Multi-Property Temporal Logic Monitoring. CoRR abs/2605. [2] Arinç Demir & Dogan Ulus (2026): Multi-Property Temporal Logic Monitoring. CoRR abs/2605. [2] Arinç Demir & Dogan Ulus (2026): Multi-Property Temporal Logic Monitoring. CoRR abs/2605. CoRR abs/2605. 13668,
doi:10. CoRR abs/2605. 13668,
doi:10. CoRR abs/2605. 13668,
doi:10. 13668,
doi:10. 48550/ARXIV. 13668,
doi:10. 48550/ARXIV. 13668,
doi:10. 48550/ARXIV. 13668,
doi:10. 48550/ARXIV. 13668,
doi:10. 48550/ARXIV. 13668,
doi:10. 48550/ARXIV.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[3] Dieter Fox, Wolfram Burgard & Sebastian Thrun (1997): The dynamic window approach to collision avoidance. IEEE Robotics Autom. p. 6 [3] Dieter Fox, Wolfram Burgard & Sebastian Thrun (1997): The dynamic window approach to collision avoidance. IEEE Robotics Autom. [3] Dieter Fox, Wolfram Burgard & Sebastian Thrun (1997): The dynamic window approach to collision avoidance. IEEE Robotics Autom. [3] Dieter Fox, Wolfram Burgard & Sebastian Thrun (1997): The dynamic window approach to collision avoidance. IEEE Robotics Autom. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[4] Dov M Gabbay (1981): Expressive functional completeness in tense logic (preliminary report). In: Aspects of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. p. 6 Gabbay (1981): Expressive functional completeness in tense logic (preliminary report). In: Aspects
of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. Gabbay (1981): Expressive functional completeness in tense logic (preliminary report). In: Aspects
of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. Gabbay (1981): Expressive functional completeness in tense logic (preliminary report). In: Aspects
of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. In: Aspects
of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. 91–
117, doi:10. In: Aspects
of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. 91–
117, doi:10. In: Aspects
of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. 91–
117, doi:10.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[5] Dov M Gabbay (1987): The Declarative Past and Imperative Future: Executable Temporal Logic for Interactive Systems. In: Temporal Logic in Specification, Altrincham, UK, April 8-10, 1987, Proceedings
[6] Klaus Havelund, Doron Peled & Dogan Ulus (2020): First-order temporal logic monitoring with BDDs. Formal Methods Syst. p. 6 [6] Klaus Havelund, Doron Peled & Dogan Ulus (2020): First-order temporal logic monitoring with BDDs. Formal Methods Syst. [6] Klaus Havelund, Doron Peled & Dogan Ulus (2020): First-order temporal logic monitoring with BDDs. Formal Methods Syst. [6] Klaus Havelund, Doron Peled & Dogan Ulus (2020): First-order temporal logic monitoring with BDDs. Formal Methods Syst. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[7] Klaus Havelund & Grigore Rosu (26) 26: Efficient monitoring of safety properties. Int. J. Softw. Tools Technol. p. 6 [7] Klaus Havelund & Grigore Rosu (2004): Efficient monitoring of safety properties. Tools Technol. [7] Klaus Havelund & Grigore Rosu (2004): Efficient monitoring of safety properties. Tools Technol. [7] Klaus Havelund & Grigore Rosu (2004): Efficient monitoring of safety properties. Tools Technol. Tools Technol. 158–173, doi:10. Tools Technol. 158–173, doi:10. Tools Technol. 158–173, doi:10.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[8] Dogan Ulus (26) 26: Online Monitoring of Metric Temporal Logic using Sequential Networks. Log. Methods Comput. p. 6 [8] Dogan Ulus (2026): Online Monitoring of Metric Temporal Logic using Sequential Networks. Methods
Comput. In: Stepwise Refinement of Distributed Systems, Models,
Formalisms, Correctness, REX Workshop, Mook, The Netherlands, May 29 - June 2, 1989, Proceedings, pp. 94–129, doi:10.Where the paper says it
Where the paper says it
[9] Dogan Ulus (26) 4: Reelay: Online Temporal Logic Monitoring Framework. CoRR abs/2604. p. 6 [9] Dogan Ulus (2026): Reelay: Online Temporal Logic Monitoring Framework. CoRR abs/2604. [9] Dogan Ulus (2026): Reelay: Online Temporal Logic Monitoring Framework. CoRR abs/2604. [9] Dogan Ulus (2026): Reelay: Online Temporal Logic Monitoring Framework. CoRR abs/2604. CoRR abs/2604. 22384,
doi:10. CoRR abs/2604. 22384,
doi:10. CoRR abs/2604. 22384,
doi:10.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
[10] Dogan Ulus & Calin Belta (26) 19: Reactive Control Meets Runtime Verification: A Case Study of Navigation. In: Runtime Verification - 19th International Conference, RV 2019, Porto, Portugal, October 8-11, 2019, Proceedings
[11] Moritz Werling et al (26) 4: Optimal trajectory generation for dynamic street scenarios in a Frenét Frame. In: IEEE International Conference on Robotics and Automation, ICRA 2010, Anchorage, Alaska, USA
[12] (No reference provided)
[1] Howard Barringer et al (1989): METATEM: A Framework for Programming in Temporal Logic. In: Stepwise Refinement of Distributed Systems, Models, Formalisms, Correctness, REX Workshop, Mook
[2] Arinç Demir & Dogan Ulus (2026): Multi-Property Temporal Logic Monitoring. CoRR abs/2605.13668, doi:10.48550/ARXIV.2605.13668
[3] Dieter Fox et al (1997): The dynamic window approach to collision avoidance. IEEE Robotics Autom. Mag. 4(1), pp. 23–33, doi:10.1109/100.580977
[4] Dov M Gabbay (1981): Expressive functional completeness in tense logic (preliminary report). In: Aspects of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. 91–117, doi:10.1007/978-94-009-8384-7 4
[5] Dov M Gabbay (1987): The Declarative Past and Imperative Future: Executable Temporal Logic for Interactive Systems. In: Temporal Logic in Specification, Altrincham, UK, April 8-10, 1987, Proceedings
[6] Klaus Havelund et al (2020): First-order temporal logic monitoring with BDDs. Formal Methods Syst. Des. 56(1), pp. 1–21, doi:10.1007/S10703-018-00327-4
[7] Klaus Havelund & Grigore Rosu (26) 26: Efficient monitoring of safety properties. Int. J. Softw. Tools Technol. Transf. 6(2), pp. 158–173, doi:10.1007/S10009-003-0117-6
[8] Dogan Ulus (26) 4: Reelay: Online Temporal Logic Monitoring Framework. CoRR abs/2604.22384, doi:10.48550/ARXIV.2604.22384
[9] Dogan Ulus & Calin Belta (19): Reactive Control Meets Runtime Verification: A Case Study of Navigation. In: Runtime Verification - 19th International Conference, RV 2019, Porto, Portugal, October 8-11, 2019, Proceedings
[10] Moritz Werling et al (26) 4: Optimal trajectory generation for dynamic street scenarios in a Frenét Frame. In: IEEE International Conference on Robotics and Automation, ICRA 2010, Anchorage, Alaska, USA
[11] (No reference provided)
[1] Howard Barringer et al (1989): METATEM: A Framework for Programming in Temporal Logic. In: Stepwise Refinement of Distributed Systems, Models, Formalisms, Correctness, REX Workshop, Mook
[2] Arinç Demir & Dogan Ulus (2026): Multi-Property Temporal Logic Monitoring. CoRR abs/2605.13668, doi:10.48550/ARXIV.2605.13668
[3] Dieter Fox et al (1997): The dynamic window approach to collision avoidance. IEEE Robotics Autom. Mag. 4(1), pp. 23–33, doi:10.1109/100.580977
[4] Dov M Gabbay (1981): Expressive functional completeness in tense logic (preliminary report). In: Aspects of Philosophical Logic: Some Logical Forays into Central Notions of Linguistics and Philosophy, pp. 91–117, doi:10.1007/978-94-009-8384-7 4
[5] Dov M Gabbay (1987): The Declarative Past and Imperative Future: Executable Temporal Logic for Interactive Systems. In: Temporal Logic in Specification, Altrincham, UK, April 8-10, 1987, Proceedings
[6] Klaus Havelund et al (2020): First-order temporal logic monitoring with BDDs. Formal Methods Syst. Des. 56(1), pp. 1–21, doi:10.1007/S10703-018-00327-4
[7] Klaus Havelund & Grigore Rosu (26) 26: Efficient monitoring of safety properties. Int. J. Softw. Tools Technol. Transf. 6(2), pp. 158–173, doi:10.1007/S10009-003-0117-6
[8] Dogan Ulus (26) 4: Reelay: Online Temporal Logic Monitoring Framework. CoRR abs/2604.22384, doi:10.48550/ARXIV.2604.22384
[9] Dogan Ulus & Calin Belta (19): Reactive Control Meets Runtime Verification: A Case Study of Navigation. In: Runtime Verification - 19th International Conference, RV 2019, Porto, Portugal, October 8-11, 2019, Proceedings
[10] Moritz Werling et al (26) 4: Optimal trajectory generation for dynamic street scenarios in a Frenét Frame.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
The system can filter predicted trajectories according to requirements induced by observed history,
identifying admissible continuations that can support subsequent decision making.
This allows for safe selection of actions at current time points by only considering future behaviors consistent with past assurance obligations. -
A new architecture enables the use of shared high-performance monitoring infrastructure for both past- and future-time formulas, leveraging the symmetry where
a future-time formula can be transformed into a corresponding past-time formula rev(phifuture) by reversing the temporal direction and replacing futuretime operators with their past-time counterparts.
-
The system can provide feedback to guide or refine prediction mechanisms, as
Runtime verdicts for predicted behaviors can be used as feedback to guide or refine the prediction mechanism in subsequent control cycles,
creating a formal assurance layer that informs future predictions.
Abstract
Runtime assurance for autonomous systems increasingly requires reasoning not only about observed executions but also about anticipated future behaviors. Traditional runtime verification, however, primarily evaluates the execution observed so far and does not directly account for predicted continuations. We propose a formal framework for runtime assurance that combines monitoring of the observed execution with analysis of multiple predicted continuations. To support this integration, we introduce Split Linear Temporal Logic (SplitLTL), a linear-time temporal logic that assigns complementary roles to past and future temporal specifications within a single specification. The past component uses the observed history to determine the assurance requirements applicable at the current point of execution, while the future component evaluates predicted continuations against those requirements. The framework therefore filters predicted continuations according to the requirements induced by the observed history, identifying admissible continuations that can support subsequent decision making. We formally define the syntax and semantics of SplitLTL and present an online monitoring architecture for evaluating observed executions together with predicted continuations.
Sources
Related papers
- A Non-Dichotomy for CSPs of Stable omega-Categorical Structures
- A Deeper Look at Depth: Stable Generation Accounting for Quantifier Reasoning
- Formalizing Hyperspaces and Operations on Subsets of Polish Spaces over Abstract Exact Real Numbers
- A Diagrammatic Basis for Computer Programming
- Interpolation via Generalized Splitting
- Staying Productive Under the Palm Trees: On Graded Coeffect Typing in the Tropical Semiring