💻 computer science

The Temporal Logic Synthesis Format TLSF v1.2

This paper presents version 1.2 of the Temporal Logic Synthesis Format (TLSF), an extension of standard LTL that incorporates high-level constructs like sets and functions, parameterized problem families, and new operators with LTLf semantics for finite executions.

Original authors: Swen Jacobs, Guillermo A. Perez, Philipp Schlehuber-Caissier

Published 2026-04-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Swen Jacobs, Guillermo A. Perez, Philipp Schlehuber-Caissier

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a master architect trying to design a robot that can solve a specific puzzle. You need to give the robot a set of instructions: "Here is what the world might do (inputs), and here is what you must do in response (outputs) to win."

For a long time, the language we used to write these instructions (called TLSF) was like a very strict, basic programming language. It could handle simple "if-then" rules and standard time-based logic (like "eventually, the light must turn green").

This paper introduces TLSF v1.2, a major upgrade to that language. Think of it as upgrading from a sketchpad to a full-blown CAD software with 3D modeling, variables, and smart templates.

Here is the breakdown of the new features using everyday analogies:

1. The "Finite" Twist: The Short Story vs. The Infinite Novel

The Old Way: Previously, the instructions assumed the robot would run forever, like a novel that never ends. The logic checked if the robot could eventually do the right thing, even if it took a million years.

The New Way (LTLf): TLSF v1.2 introduces Finite Semantics. Now, you can tell the robot: "This task has a deadline. Once you finish the job, you can stop."

The Analogy: Imagine a game of "Red Light, Green Light." In the old version, the game never ended; you just had to keep moving forever. In the new version, the game ends when you cross the finish line. The robot needs a special "I'm done!" signal (called the Alive Signal) to tell the world, "I have successfully finished the task."
The "Strong Next" Operator: The paper adds a new tool called X[!]. In the old language, "Next" meant "look at the next step." In the new language, X[!] means "Look at the next step, but only if there is one." If you are at the very last step of the story, X[!] fails (because there is no next step), whereas the old "Next" would just say "Okay, I'm at the end, so I'm safe."

2. The "Global" Section: The Master Blueprint

The Old Way: If you wanted to build a robot for a factory with 10 machines, you had to write the instructions 10 times, changing the numbers manually. It was repetitive and prone to typos.

The New Way (Global Section): Now, you can define Parameters and Functions at the top of your document.

The Analogy: Think of this like a cookie cutter. Instead of baking 100 individual cookies by hand, you define a "Cookie Size" variable. If you change the size from "Small" to "Large" in the Global section, every cookie in your recipe automatically updates.
Functions: You can also write "macros" (shortcuts). For example, you can define a function called SafeZone(x, y) that automatically expands into a complex set of rules. You just call SafeZone later, and the computer fills in the details.

3. Buses and Enums: Organizing the Toolbox

The Old Way: You had to name every single wire individually: wire1, wire2, wire3... up to wire100.

The New Way (Buses): You can now group wires into Buses.

The Analogy: Instead of naming 8 individual light switches, you just say "The Kitchen Light Panel." You can then refer to specific switches as KitchenPanel[0], KitchenPanel[1], etc.
Enums (Enumerations): You can give names to specific patterns. Instead of saying "If the lights are 1-0-1," you can define a pattern called RIGHT_TURN. Now your code just says If (Lights == RIGHT_TURN). It's like using a nickname for a complex outfit instead of describing every stitch.

4. The "Big Operators": The Assembly Line

The Old Way: If you wanted to say "All 100 sensors must be on," you had to write Sensor1 && Sensor2 && Sensor3 ... && Sensor100. That's a huge, messy sentence.

The New Way: You can use Big Operators (like Sigma $\Sigma$ or Product $\Pi$ ).

The Analogy: Instead of writing a grocery list item by item, you write "Buy all items in the 'Fruit' basket." The computer automatically expands that into the full list. This makes the instructions much shorter and easier to read.

5. The "Alive" Signal: The Finish Line Flag

One of the most critical changes is how the robot knows when to stop.

In the new format, the robot has a special output flag called Alive.
The Analogy: Imagine a runner in a race. In the old system, the runner just kept running forever. In the new system, the runner carries a flag. When they cross the finish line, they raise the flag. The system checks: "Did the runner raise the flag before the race ended?" If yes, the task is a success. If the runner stops without raising the flag, they failed.

Why Does This Matter?

This update allows engineers to design families of problems rather than single, static problems.

Before: "Design a traffic light for this specific intersection."
Now: "Design a traffic light system where you can plug in any number of lanes, and it will automatically generate the correct rules for that size."

It makes the process of creating "synthesis" (automatically building a robot that follows rules) faster, less error-prone, and capable of handling more complex, real-world scenarios where tasks have a clear beginning and end.

Based on the provided document, here is a detailed technical summary of the paper "The Temporal Logic Synthesis Format TLSF v1.2".

1. Problem Statement

The paper addresses the need for a more expressive and flexible specification format for Temporal Logic Synthesis. While the existing TLSF v1.1 format supports standard Linear Temporal Logic (LTL) with high-level constructs (sets, functions, parameters), it lacks native support for LTL over finite words (LTLf).

LTLf is crucial for synthesizing controllers that operate on finite executions (terminating systems), where the system must explicitly signal when a task is complete. The previous format did not adequately support the specific semantics required for finite traces, particularly the distinction between weak and strong "next" operators and the handling of termination signals. Furthermore, there was a need to unify the specification of parameterized families of problems with these finite-word semantics.

2. Methodology

The authors propose TLSF v1.2, an extension of the existing TLSF format. The methodology involves:

Syntax Extension: Introducing new operators and modifying the grammar to support LTLf. Specifically, the addition of the strong next operator ( $X[!]$ ) and redefining the standard next operator ( $X$ ) as the weak next in the context of finite words.
Semantic Formalization: Defining the semantics of LTLf over finite words, distinguishing between terminating and non-terminating controllers.
- Terminating Controllers: These determine the length of the execution. They use a special output proposition called the alive signal (denoted as as) to indicate whether the system is still running or has terminated.
- Machine Models: The format supports both Mealy (output depends on state and input) and Moore (output depends only on state) machines, adapted for termination.
Format Unification: Integrating these new semantics into the existing TLSF structure, which includes:
- INFO Section: Meta-data and declaration of semantics (Standard, Strict, or Finite) and targets (Mealy/Moore).
- GLOBAL Section: Optional section for defining parameters, enumerations, and functions to allow parameterized specifications.
- MAIN Section: Partitioning of inputs/outputs and specification of assumptions/guarantees using extended expressions (buses, sets, functions).
Tooling Updates: Updating the SyFCo (Synthesis Format Conversion) tool to support the new format and generate output compatible with the Spot tool (specifically the ltlxba-fin format).

3. Key Contributions

A. LTLf Semantics and Operators

The paper formally defines LTLf semantics over finite words $\alpha = a_0...a_{n-1}$ . Key distinctions include:

Strong Next ( $X[!]$ ): Requires the existence of a next position ( $i+1 < n$ ) and that the property holds there. If evaluated at the last position, it is false.
Weak Next ( $X$ ): Defined as $\neg X[!]\neg \phi$ . It is true at the last position of a word (vacuously true if no next state exists).
Termination Signal: Introduction of the alive signal. A word satisfies a formula if the controller produces a sequence where alive is true until the final step, where it becomes false (signaling termination).

B. Extended Format Features

TLSF v1.2 retains and enhances the high-level constructs of v1.1:

Parameterization: Specifications can define families of problems using numerical parameters (e.g., array sizes).
Buses and Enumerations: Support for signal buses (arrays of signals) and enumeration types to constrain signal valuations.
Functions and Pattern Matching: Recursive functions can be defined in a GLOBAL section. A novel pattern matching feature allows functions to inspect the structure of LTL formulas (e.g., distinguishing between $U$ and $R$ operators) to generate specific logic.
Big Operators: Syntax for parameterized conjunctions ( $\bigwedge$ ), disjunctions ( $\bigvee$ ), sums, and products over sets or ranges.

C. Semantic Variants

The format explicitly supports three semantic interpretations for synthesis:

Standard: Standard LTL semantics (infinite words).
Strict: Uses strict implication (common in GR(1) synthesis), ensuring guarantees hold as long as assumptions hold.
Finite: Interprets the formula over finite words (LTLf), utilizing the alive signal and the specific next-operator semantics.

D. Tool Support

The authors updated the SyFCo tool to parse TLSF v1.2 and convert specifications into formats compatible with LTLf synthesis tools (like Spot), facilitating the practical application of the new standard.

4. Results and Examples

The paper provides theoretical definitions and illustrative examples to validate the format:

Terminating Mealy Machines: Figure 1 demonstrates a Mealy machine satisfying $G(i_1 \leftrightarrow o_1) \land (o_2 \lor X[!]true)$ . The machine explicitly terminates when the condition is met.
Terminating Moore Machines: Figure 2 shows a Moore machine satisfying a modified formula. The paper notes that some formulas realizable in Mealy semantics are not realizable in Moore semantics due to the dependency of output on current input.
Syntax Examples: The paper details how to use the new syntax, such as X[!] for strong next, F[2:3] for bounded eventually, and pattern matching in function definitions (e.g., f ~ a U _ : a).

5. Significance

Standardization: TLSF v1.2 establishes a unified standard for specifying synthesis problems involving both infinite and finite executions, bridging the gap between traditional LTL synthesis and LTLf synthesis.
Expressiveness: By integrating parameterization, sets, and functions with LTLf, it allows researchers to define complex, scalable synthesis benchmarks (families of problems) that were previously difficult to express concisely.
Practical Utility: The explicit handling of termination via the alive signal and the support for both Mealy and Moore models provide a rigorous foundation for synthesizing controllers for real-world systems that have a defined end-state (e.g., transaction processing, protocol completion).
Community Impact: The update to SyFCo and the compatibility with the Spot tool ensure that the format is immediately usable by the formal methods community for competitions (like SYNTCOMP) and research.

In summary, TLSF v1.2 is a significant evolution of the synthesis specification format, enabling the rigorous definition and automated synthesis of controllers for finite-word systems while maintaining the high-level abstraction capabilities of its predecessor.