Reasoning on LTL on Finite Traces: Insensitivity to Infiniteness

Giuseppe De Giacomo, Riccardo De Masellis, Marco MontaliAAAI 2014 · DOI

Introduction

Linear Temporal Logic (LTL) is a cornerstone of formal verification, traditionally used to specify properties of infinite executions. However, many modern domains—such as AI planning (PDDL 3.0), business process management (DECLARE), and runtime monitoring—deal exclusively with finite sequences of events, or traces. This has led to the rise of $LTL_f$, a variant of LTL interpreted over finite traces.

Historically, practitioners have bridged the gap between finite and infinite trace reasoning using a common "hack": padding a finite trace with a special "end" symbol that repeats infinitely. While this allows the use of mature LTL tools, it lacks a rigorous foundation and can lead to subtle errors. This paper formalizes the property of "insensitivity to infiniteness," identifying when this blurring is safe and introducing a direct method for $LTL_f$ reasoning.

The Insensitivity Property

The core contribution of this work is the formalization of "insensitivity to infiniteness." A formula is considered insensitive if its truth value on a finite trace is identical to its truth value on an infinite trace padded with a terminal symbol.

The authors define a mapping $f(\phi)$ that translates $LTL_f$ formulas into standard LTL by introducing a fresh proposition end. Crucially, they provide a necessary and sufficient condition (Theorem 4) that allows standard LTL reasoners, such as NuSMV, to automatically verify if a formula possesses this property. This theoretical breakthrough explains why many industry "hacks" worked in practice: the specific formulas being used were, by chance, insensitive.

Empirical Validation: The DECLARE Patterns

To test their theory, the authors evaluated established specification pattern catalogs, most notably the DECLARE templates used in business process modeling.

Table 1: DECLARE patterns and their insensitivity to infiniteness. Note that only "Neg. Chain Succession" is sensitive to the finite/infinite distinction.

As shown in the table above, nearly all common DECLARE patterns are insensitive to infiniteness. The notable exception is "Negation Chain Succession" ($\square(a \equiv \circ \neg b)$). On a finite trace, this formula implies that a certain event cannot be the final one in a sequence—a nuance lost when the trace is interpreted as infinite. This finding provides a formal "green light" for using LTL tools on most DECLARE models while highlighting specific pitfalls.

Direct NFA Construction

Beyond formalizing the "hack," the paper introduces the $LTL_f2NFA$ algorithm. Traditional approaches often convert $LTL_f$ to a complex Büchi automaton (designed for infinite words) and then attempt to "fix" it into a Non-deterministic Finite Automaton (NFA).

Figure 1: Comparison between a complex Büchi automaton (a) and a direct NFA representation (b).

The $LTL_f2NFA$ algorithm bypasses this detour. It uses an auxiliary function $\delta$ to build an NFA directly from the formula's structure in a forward-moving fashion. This approach simplifies implementation and maintains optimal PSPACE-complete complexity, making it ideal for runtime monitoring and plan verification.

Conclusion

This research provides the mathematical foundation needed to safely apply LTL reasoning to finite-trace domains. By identifying the exact conditions for "insensitivity to infiniteness" and providing a direct $LTL_f2NFA$ algorithm, the authors bridge the gap between theoretical LTL and practical finite-trace applications. Future work aims to extend these results to Linear Dynamic Logic ($LDL_f$) and refine runtime monitoring implementations.

Summary updated

BibTeX
@inproceedings{giacomo2014reasoning,
  author = {Giuseppe De Giacomo and Riccardo De Masellis and Marco Montali},
  title = {{Reasoning on LTL on Finite Traces: Insensitivity to Infiniteness}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2014},
  doi = {10.1609/aaai.v28i1.8872},
}
Figure