💻 computer science

The Temporal Logic Synthesis Format TLSF v1.2

Dit paper presenteert een extensie van het Temporal Logic Synthesis Format (TLSF) die, naast standaard LTL, ook hoog-niveau constructies zoals verzamelingen en functies ondersteunt en een nieuwe semantiek voor LTL op eindige uitvoeringen introduceert.

Oorspronkelijke auteurs: Swen Jacobs, Guillermo A. Perez, Philipp Schlehuber-Caissier

Gepubliceerd 2026-04-15

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Swen Jacobs, Guillermo A. Perez, Philipp Schlehuber-Caissier

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

🏗️ De Bouwplaat voor Slimme Robots: TLSF v1.2

Stel je voor dat je een architect bent die een zeer slimme robot ontwerpt. Deze robot moet taken uitvoeren in een onvoorspelbare wereld (bijvoorbeeld een zelfrijdende auto in het verkeer of een robot in een fabriek).

Om deze robot te programmeren, heb je een taal nodig om precies te zeggen wat hij moet doen. In de wereld van de informatica heet deze taal TLSF (Temporal Logic Synthesis Format). Dit paper introduceert versie 1.2 van die taal. Het is alsof je een oude, simpele bouwplaat hebt en je krijgt nu een uitgebreide set met nieuwe stukjes, grotere lego-blokken en een nieuwe manier om de regels te stellen.

Hier zijn de belangrijkste verbeteringen, uitgelegd met analogieën:

1. Van Simpel naar Compleet: De "Bussen" en "Lijsten"

In de oude versie (v1.1) kon je alleen praten over één enkele knop of lampje (bijvoorbeeld: "Lampje A moet aan").
In v1.2 kun je nu praten over groepen van signalen, zoals een bus (een kabel met 8 draden) of een lijst.

De Analogie: Vroeger kon je alleen zeggen: "De rode knop moet indrukken." Nu kun je zeggen: "De hele rij van 8 knoppen moet in een specifiek patroon oplichten, zoals een verkeerslicht dat groen, geel en rood is."
Waarom? Dit maakt het veel makkelijker om complexe systemen te beschrijven zonder duizenden regels te hoeven schrijven.

2. De Nieuwe "Stopknop": LTLf (Leven op een Eindeloze Lijn vs. Een Film)

Dit is de grootste vernieuwing. De oude taal ging uit van een wereld die nooit stopt (oneindig). Maar wat als je robot een taak heeft die eindigt? Bijvoorbeeld: "Verzamel alle dozen en stop dan."
TLSF v1.2 introduceert LTLf (LTL op finite of eindige woorden).

De Analogie:
- Oud (LTL): De robot moet eeuwig doorgaan met ademen. Als hij stopt, is er een probleem.
- Nieuw (LTLf): De robot mag een taak uitvoeren en daarna stoppen.
De "Levende Signaal" (Alive Signal): Om te weten wanneer de robot stopt, hebben we een speciale knop nodig, de Alive-knop.
- Als de knop aan staat, zegt de robot: "Ik werk nog!"
- Als de knop uit gaat, zegt de robot: "Taak voltooid, ik stop nu."
- De taal heeft nu een nieuwe operator X[!] (Sterke Volgende). Dit betekent: "Er moet echt een volgende stap zijn." Als de robot stopt, is deze operator niet waar. Dit helpt de computer om precies te weten wanneer de "film" ophoudt.

3. De "Magische Magere" (Parameters en Functies)

Vroeger moest je voor elke variant van een probleem een nieuwe specificatie schrijven.
In v1.2 kun je nu parameters en functies gebruiken.

De Analogie:
- Oud: Je schrijft een bouwplaat voor een huis met 3 kamers. Dan schrijf je een nieuwe voor een huis met 4 kamers.
- Nieuw: Je schrijft één bouwplaat met een variabele: "Huis met N kamers". Je kunt N invullen met 3, 10 of 100.
Functies: Je kunt ook "recepten" maken. Bijvoorbeeld: "Als de formule een 'totdat'-regel bevat, doe dan X; anders doe Y." Dit maakt de taal heel flexibel voor grote, complexe systemen.

4. De Regels van het Spel: Mealy vs. Moore

De paper legt uit hoe de robot zijn beslissingen neemt. Er zijn twee soorten robots:

Mealy: De robot kijkt naar de huidige situatie én de input om zijn beslissing te nemen. (Bijvoorbeeld: Een deur die opent zodra je op de knop drukt).
Moore: De robot kijkt alleen naar zijn eigen toestand. (Bijvoorbeeld: Een deur die opent, maar pas na een seconde nadat je op de knop hebt gedrukt, omdat hij eerst in een andere "stand" moet gaan).
De nieuwe versie maakt het makkelijker om te kiezen welke robot je wilt bouwen, afhankelijk van hoe snel je reactie moet zijn.

5. De "Grote Operators" (Samenvatten)

Stel je voor dat je moet zeggen: "Alle knoppen van 1 tot 100 moeten aan."
In de oude taal was dat een lange lijst. In v1.2 kun je grote operators gebruiken (zoals een som-teken $\Sigma$ of een product-teken $\Pi$ ).

De Analogie: In plaats van "1+2+3+4+5..." te schrijven, schrijf je gewoon "Som van 1 tot 5". Dit maakt de specificaties veel leesbaarder voor mensen.

🎯 Waarom is dit belangrijk?

Dit paper is niet zomaar een update; het is een upgrade van de gereedschapskist voor ingenieurs die slimme systemen bouwen.

Efficiëntie: Je kunt complexere systemen beschrijven met minder regels.
Realisme: Je kunt nu systemen beschrijven die een taak uitvoeren en dan stoppen (zoals een robot die een pakket bezorgt), in plaats van alleen systemen die eeuwig doorgaan.
Flexibiliteit: Je kunt één beschrijving gebruiken voor honderden verschillende varianten van een probleem.

Kortom: TLSF v1.2 maakt het voor computers makkelijker om te begrijpen wat we van hen willen, en voor mensen makkelijker om die instructies te geven. Het is de brug tussen een wazige droom ("Maak een slimme robot") en een exacte bouwinstructie die een computer kan vertalen naar werkende software.

Titel: The Temporal Logic Synthesis Format TLSF v1.2

Auteurs: Swen Jacobs, Guillermo A. Pérez, Philipp Schlehuber-Caissier
Context: Uitbreiding van het bestaande TLSF v1.1 formaat voor synthese van controllers, met name gericht op eindige uitvoeringen (LTLf).

1. Het Probleem

Het bestaande Temporal Logic Synthesis Format (TLSF) v1.1 is ontworpen voor het specificeren van synthese-problemen gebaseerd op standaard LTL (Linear Temporal Logic) over oneindige woorden. Echter, er is een groeiende behoefte aan specificaties die eindige uitvoeringen (finite executions) modelleren, wat relevant is voor taken die een duidelijk eindpunt hebben (bijvoorbeeld een robot die een taak voltooit en stopt).

De uitdagingen waren:

Het ontbreken van een gestandaardiseerd formaat voor LTLf (LTL over eindige woorden).
De noodzaak om hoge-niveau constructies (zoals verzamelingen, functies en parameters) te ondersteunen om families van problemen compact te specificeren, in plaats van elke instantie handmatig te coderen.
Het definiëren van een duidelijke semantiek voor terminerende controllers, die kunnen aangeven wanneer een taak voltooid is.

2. Methodologie

De auteurs presenteren TLSF v1.2, een uitgebreide specificatieformaat dat de volgende methodologische stappen doorloopt:

Semantische Uitbreiding: De basis van het formaat blijft LTL, maar introduceert een nieuwe operator X[!] (sterke volgende) en definieert de semantiek van de standaard X (zwakke volgende) anders voor eindige woorden.
Structuur van het Formaat: Het formaat behoudt de bekende structuur van TLSF v1.1 (INFO en MAIN secties) maar voegt een optionele GLOBAL sectie toe voor parameters, definities en functies.
Expressiviteit:
- Parameters: Numerieke waarden kunnen worden gedefinieerd om families van problemen te genereren.
- Bussen (Buses): Signalen kunnen worden gegroepeerd in bussen (arrays) met een specifieke breedte.
- Enumeraties: Gebruik van enumeraties om signalen te groeperen en te beperken tot specifieke waarden.
- Functies: Recursieve functies kunnen worden gedefinieerd om complexe formules te genereren op basis van parameters.
- Grote Operatoren: Notatie voor sommen, producten en verenigingen over verzamelingen (bijv. &&[i IN S]).
Terminatie en Alive-signaal: Voor LTLf wordt een speciaal output-signaal AliveSig geïntroduceerd. Een controller "stopt" wanneer dit signaal actief is. Dit maakt onderscheid tussen terminerende en niet-terminerende controllers mogelijk.

3. Belangrijkste Bijdragen

A. Formele Definitie van LTLf in TLSF

Het paper definieert de syntaxis en semantiek van LTLf binnen TLSF.

Semantiek over eindige woorden: Een formule $\phi$ is waar op een eindige woord $\alpha$ van lengte $n$ als $\alpha, 0 \models \phi$ .
Operatoren:
- X[!] (Sterke volgende): Vereist dat er een volgende positie bestaat ( $i+1 < n$ ) en dat $\phi$ daar geldt.
- X (Zwakke volgende): In LTLf is dit gedefinieerd als $\neg X[!]\neg \phi$ . Dit betekent dat X waar is op het laatste element van een woord (als er geen volgende staat, is de "volgende" toestand vacu waar voor de negatie).
Terminatie: Een controller is een eindige automaat (Mealy of Moore) die een woord produceert totdat het AliveSig-signaal wordt gezet. De taal van de machine bestaat uit de kortste sequenties die aan de formule voldoen.

B. Uitgebreide Syntax en Semantiek

Drie Types Semantiek: Het formaat ondersteunt nu:
1. Standaard: LTL over oneindige woorden.
2. Strict: Implicatie die strikt is (gebruikt in GR(1) synthese).
3. Finite: LTLf over eindige woorden (de nieuwe toevoeging).
Doelmodellen: Ondersteuning voor zowel Mealy-machines (uitvoer hangt af van toestand en input) als Moore-machines (uitvoer hangt alleen af van toestand).
Global Sectie: Hiermee kunnen auteurs parameters (bijv. $N=10$ ) en functies definiëren die later in de MAIN-sectie worden gebruikt, wat leidt tot zeer compacte specificaties voor grote families van problemen.

C. Tooling Updates

De auteurs hebben de SyFCo (Synthesis Format Conversion Tool) bijgewerkt om TLSF v1.2 bestanden te converteren naar het formaat ltlxba-fin, compatibel met tools zoals Spot, die LTLf kunnen verwerken.

4. Resultaten en Voorbeelden

Het paper illustreert de kracht van het formaat met voorbeelden:

Terminerende Mealy Machines: Een voorbeeld met de formule $G(i_1 \leftrightarrow o_1) \land (o_2 \lor X[!]true)$ toont hoe een machine kan stoppen zodra $o_2$ waar is, terwijl de relatie tussen $i_1$ en $o_1$ behouden blijft.
Moore Machines: Het toont aan dat sommige formules die in Mealy-semantiek realiseerbaar zijn, dat niet zijn in Moore-semantiek (vanwege de vertraging in uitvoer), en hoe het formaat dit onderscheid maakt.
Functie-gebaseerde specificatie: Het voorbeeld van een functie fun(f) die een LTL-formule als input neemt en deze transformeert (bijv. als f een U-operator bevat, haalt de functie het linkerdeel eruit), demonstreert de kracht van de nieuwe syntaxis voor generatieve specificaties.

5. Betekenis en Impact

Standaardisatie: TLSF v1.2 biedt een uniforme manier om synthese-problemen voor eindige woorden te specificeren, wat essentieel is voor vergelijkingen in competities zoals SYNTCOMP.
Flexibiliteit: Door de ondersteuning voor parameters, bussen en functies kunnen onderzoekers complexe, parameteriseerbare families van problemen specificeren zonder duizenden regels code te schrijven.
Praktische Toepasbaarheid: De introductie van terminerende semantiek en het AliveSig-signaal maakt het formaat direct toepasbaar op real-world scenario's waar taken een eindpunt hebben, in plaats van alleen oneindige systemen.
Tooling: De integratie met bestaande tools (via SyFCo en Spot) zorgt ervoor dat de specificaties direct kunnen worden gebruikt voor synthese en verificatie.

Conclusie:
TLSF v1.2 is een significante evolutie van het bestaande formaat die de brug slaat tussen theoretische LTLf-semantiek en praktische synthese-eisen. Het maakt het mogelijk om zowel de complexiteit van de logica (eindige woorden, sterke next) als de complexiteit van de probleemstructuur (parameters, verzamelingen) op een gestandaardiseerde en leesbare manier te specificeren.