The Temporal Logic Synthesis Format TLSF v1.2

Swen Jacobs, Guillermo A. Pérez, Philipp Schlehuber-Caissier

Abstract

This paper presents TLSF v1.2, an extension of the Temporal Logic Synthesis Format designed to support Linear Temporal Logic over finite traces ($LTL_f$). By introducing new operators like "strong next" and defining semantics for finite-trace synthesis, TLSF v1.2 provides a standardized framework for specifying tasks that terminate, bridging a critical gap in formal methods tooling and enabling the automatic generation of controllers for finite-horizon tasks.

1. Introduction

In formal methods, synthesis is the process of automatically generating a correct-by-construction system, such as a controller, from a logical specification. Traditionally, this field has focused on infinite-horizon tasks—systems that run indefinitely, such as operating system kernels. These are typically described using standard Linear Temporal Logic (LTL).

However, many real-world applications are inherently finite. A robot might need to navigate to a room and stop, or a software script might process a file and exit. While $LTL_f$ (LTL on finite traces) exists to describe these scenarios, there was no standardized, high-level format to exchange these problems between different synthesis tools and competitions. TLSF v1.2 fills this gap by extending the existing TLSF standard to include finite-trace semantics and the specific operators required to handle them.

2. Syntax and Semantics Extensions

The authors extend the existing TLSF (v1.1) framework in several key ways to accommodate finite-trace logic. A primary addition is the strong next operator ($X[!]$). In finite-trace logic, the standard "next" operator ($X$) is often interpreted as "weak next," which is true if no next state exists. The "strong next" operator specifically requires that a next state must exist, which is crucial for defining when a process is allowed to end.

Extracted table from page 8 of The Temporal Logic Synthesis Format TLSF v1.2

Beyond syntax, the format introduces new semantic options. The INFO section of a TLSF file can now specify Finite variants for both Mealy and Moore machines (e.g., SEMANTICS: Mealy, Finite). To handle the synthesis of finite tasks, the authors define a special output proposition called seqdone. This "terminating signal" ($ts$) is used by the synthesized controller to explicitly indicate that the task is finished and the word is terminal.

3. Key Insights

  • The Asymmetry of "Next": A critical insight in finite-trace logic is the ambiguity of the "next" operator. TLSF v1.2 clarifies this by treating the standard X as weak and X[!] as strong, essential for defining process termination.
  • Realizability vs. Termination: For a finite specification to be "realizable," there must exist a controller that guarantees it will eventually reach a state where it can pull the terminating signal ($ts$) while satisfying the logic.
  • Unified Framework: By adding finite semantics to a format that already handles standard LTL and "Strict" (GR(1)-style) implication, TLSF v1.2 becomes a comprehensive resource for synthesis researchers, regardless of whether they work on infinite or finite horizons.

4. Results and Impact

The paper provides a complete grammar and inductive semantics for $LTL_f$ within the TLSF ecosystem. To support the community, the authors updated SyFCo (the Synthesis Format Conversion tool) to support these new features, allowing users to convert TLSF v1.2 specifications into formats compatible with other popular logic tools like Spot. Specifically, SyFCo now supports outputting to ltlxba-fin, a format tailored for finite-trace automata. Consequently, the format has been adopted for the $LTL_f$ track in the Synthesis Competition (SYNTCOMP), providing a common language for the community.

5. Conclusion

While TLSF v1.2 standardizes the format, the computational complexity of synthesis for $LTL_f$ remains a challenge distinct from standard LTL. The success of the format depends on its continued adoption by the wider formal methods community and the update of synthesis engines to parse the new v1.2 constructs. Future work may include adding higher-level constructs, such as complex data types or functions, to the "Full Format" to further improve human readability.

Summary updated

BibTeX
@misc{jacobs2023temporal,
  author = {Swen Jacobs and Guillermo A. Pérez and Philipp Schlehuber-Caissier},
  title = {{The Temporal Logic Synthesis Format TLSF v1.2}},
  year = {2023},
  eprint = {2303.03839},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2303.03839},
}
Figure