Abstract
Although it is widely accepted that every system should be robust, in the sense that "small" violations of environment assumptions should lead to "small" violations of system guarantees, it is less clear how to make this intuitive notion of robustness mathematically precise. In this paper, we address this problem by developing a robust version of Linear Temporal Logic (LTL), which we call robust LTL and denote by rLTL. Formulas in rLTL are syntactically identical to LTL formulas but are endowed with a many-valued semantics that encodes robustness. In particular, the semantics of the rLTL formula $\varphi \Rightarrow \psi$ is such that a "small" violation of the environment assumption $\varphi$ is guaranteed to only produce a "small" violation of the system guarantee $\psi$. In addition to introducing rLTL, we study the verification and synthesis problems for this logic: similarly to LTL, we show that both problems are decidable, that the verification problem can be solved in time exponential in the number of subformulas of the rLTL formula at hand, and that the synthesis problem can be solved in doubly exponential time.
Introduction
In the design of reactive systems, such as autonomous vehicles or industrial robots, formal verification typically relies on Linear Temporal Logic (LTL). Specifications are often written as implications: $\phi \Rightarrow \psi$, meaning "if the environment satisfies assumption $\phi$, the system must satisfy guarantee $\psi$." However, standard LTL uses a binary (Boolean) semantics. If the environment violates $\phi$ even slightly—perhaps due to a single sensor error—the implication becomes vacuously true, and the system is no longer bound by any safety constraints.
This "all-or-nothing" approach lacks the robustness required for real-world applications. This paper introduces Robust Linear Temporal Logic (rLTL), a framework that mathematically formalizes "graceful degradation." In rLTL, a small violation of an assumption is guaranteed to lead to only a small violation of the system's requirements.
Methodology: Many-Valued Semantics and da Costa Algebras
The core innovation of rLTL lies in its semantics. While the syntax remains identical to LTL, the truth values are expanded from a binary set {0, 1} to a five-valued domain. These five values represent the canonical ways a temporal property can be satisfied or violated over an infinite timeline:
- The property holds at every time instant.
- The property is violated only finitely many times.
- The property holds infinitely often and is violated infinitely often.
- The property holds at least once (but only finitely many times).
- The property never holds.
To manage these values, the authors utilize da Costa algebras. This algebraic framework allows for a specific type of negation where the Law of Excluded Middle ($\phi \vee \neg \phi$) is preserved, but the Law of Non-Contradiction is weakened. This is essential for a logic that must distinguish between "shades of false."
As illustrated in Figure 1, the "desired negation" in rLTL differs significantly from intuitionistic negation. In a robust setting, we want the negation of a partially true statement to behave in a way that preserves the logical structure needed for implication-based specifications.
Automata-Theoretic Approach
For practical application, rLTL formulas are translated into Generalized Büchi Automata. The authors introduce specific expansion rules for robust operators (e.g., $\dot{\Box}$ for "robust always") to ensure that the translation remains computationally feasible.
Key Results
The paper demonstrates that robustness does not come at the cost of theoretical complexity:
- Decidability: Both verification (model checking) and synthesis problems for rLTL are proven to be decidable.
- Complexity: The verification problem is solvable in exponential time relative to the formula size, and the synthesis problem is solvable in doubly exponential time. These bounds match those of standard LTL.
- Automata Size: An rLTL formula $\phi$ can be converted into an automaton with $O(|cl(\phi)| \cdot 5^{|cl(\phi)|})$ states, mirroring the $O(k \cdot 2^k)$ construction for LTL, but with a base of 5 instead of 2.
Conclusion and Future Work
rLTL provides a mathematically rigorous way to specify and verify robust systems without increasing the fundamental complexity of the logic. By moving to a five-valued semantics, it bridges the gap between binary formal methods and the practical need for graceful degradation in cyber-physical systems.
Future research directions include investigating the tightness of the established complexity bounds and exploring "Super-LTL" frameworks that combine robustness (handling assumption violations) with quality (measuring how well guarantees are met) using more general structures like Heyting algebras.
Summary updated