💻 computer science

A rewriting-logic-with-SMT-based formal analysis and parameter synthesis framework for parametric time Petri nets

Diese Arbeit stellt einen auf Umformungslogik und SMT-Lösung basierenden Rahmen vor, der eine vollständige formale Analyse und Parametersynthese für parametrische Zeit-Petri-Netze mit Inhibitorbögen ermöglicht und dabei in vielen Fällen die Leistungsfähigkeit des etablierten Tools Romeo übertrifft.

Ursprüngliche Autoren: Jaime Arias, Kyungmin Bae, Carlos Olarte, Peter Csaba Ölveczky, Laure Petrucci

Veröffentlicht 2026-04-08

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Jaime Arias, Kyungmin Bae, Carlos Olarte, Peter Csaba Ölveczky, Laure Petrucci

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Puzzle: Wenn Zeit und Unbekannte zusammenkommen

Stellen Sie sich vor, Sie planen eine große Party. Sie wissen, dass der Kuchen in 20 bis 30 Minuten fertig sein muss, dass die Musik um 20 Uhr starten soll und dass die Gäste zwischen 19 und 21 Uhr eintreffen. Das ist ein Zeit-System.

Aber was, wenn Sie die genauen Zahlen noch nicht kennen? Was, wenn Sie nur wissen: "Der Kuchen braucht zwischen $x$ und $y$ Minuten", wobei $x$ und $y$ noch unbekannte Parameter sind? Und was, wenn es eine Regel gibt: "Die Musik darf erst starten, wenn niemand im Raum ist" (das nennt man eine Inhibitor-Kante)?

Genau mit solchen unsicheren, zeitkritischen Systemen beschäftigt sich dieses Papier. Die Forscher haben ein neues Werkzeug entwickelt, um solche Systeme zu analysieren und herauszufinden: "Welche Werte für $x$ und $y$ sorgen dafür, dass die Party perfekt läuft, ohne Chaos?"

Die alten Werkzeuge vs. Die neue Methode

Bisher gab es ein sehr schnelles, aber spezialisiertes Werkzeug namens Roméo. Das ist wie ein hochspezialisierter Koch, der nur bestimmte Rezepte (bestimmte Arten von Zeit-Systemen) perfekt beherrscht. Aber Roméo hat Grenzen:

Er kann nicht gut mit komplexen Fragen umgehen (z. B. "Was passiert, wenn ich immer zuerst den Kuchen schneide, bevor die Musik läuft?").
Er kann keine neuen Rezepte erfinden (keine neuen Analysemethoden).
Manchmal sagt er "Vielleicht", wenn er sich nicht sicher ist.

Die Forscher in diesem Papier haben nun ein neues, extrem flexibles Werkzeug gebaut, das auf Maude und SMT (einem Art "Super-Logik-Computer") basiert.

Die Analogie: Der Baumeister und die magische Landkarte

Stellen Sie sich das Problem so vor:

Das System (Die Party): Das ist wie ein Petri-Netz. Stellen Sie sich ein Netz aus Glühbirnen (Orte) und Schaltern (Übergänge) vor. Wenn ein Schalter umgelegt wird, leuchten andere Glühbirnen auf oder aus. Aber jeder Schalter hat eine Zeitspanne, in der er umgelegt werden darf.
Die Parameter (Die Unbekannten): Die Zeitintervalle sind nicht fest, sondern wie geheime Zaubersprüche ( $\lambda$ ). Wir wollen herausfinden, welche Zauberwörter ( $\lambda = 5$ oder $\lambda = 10$ ) funktionieren.
Die alte Methode (Roméo): Roméo ist wie ein Detektiv, der jede einzelne Möglichkeit durchgeht. Aber wenn die Möglichkeiten unendlich sind (weil die Zeit fließt wie Wasser), wird er müde und gibt auf oder sagt "Vielleicht".
Die neue Methode (Maude mit SMT): Die Forscher haben einen magischen Baumeister (Maude) engagiert, der eine Landkarte der Möglichkeiten zeichnet.
- Statt jeden einzelnen Moment zu prüfen, zeichnet er Bereiche auf die Karte. "Wenn der Parameter zwischen 4 und 6 liegt, passiert hier Chaos."
- Der "Super-Logik-Computer" (SMT) hilft dem Baumeister, diese Bereiche zu berechnen, ohne jeden einzelnen Punkt abzulaufen.

Das große Problem: Die endlose Treppe

Ein Hauptproblem bei solchen Systemen ist, dass die "Landkarte" oft unendlich groß wird. Wenn Sie eine Treppe haben, die unendlich hoch ist, können Sie nie oben ankommen, wenn Sie Schritt für Schritt gehen.

Die Forscher haben eine geniale Lösung dafür gefunden: Das "Falten" (Folding).
Stellen Sie sich vor, Sie laufen durch einen Labyrinth. Wenn Sie in einen Raum kommen, den Sie schon einmal gesehen haben (oder der genau so aussieht wie ein Raum, den Sie schon gesehen haben), falten Sie die Landkarte. Sie sagen: "Okay, ich war hier schon. Ich muss nicht noch einmal den ganzen Weg gehen, um zu sehen, was passiert."

Der Clou: Die Forscher haben eine neue Art des "Faltens" entwickelt. Früher haben sie nur die Treppe in einem Ast des Labyrinths gefaltet. Jetzt falten sie die Treppe über das gesamte Labyrinth. Wenn Sie in einem anderen Ast des Labyrinths einen Raum betreten, der dem in Ast A gleicht, wissen Sie sofort: "Aha, das kennen wir schon!" Das spart enorm viel Zeit und Speicherplatz.

Was kann das neue Werkzeug, was das alte nicht kann?

Das neue System ist wie ein Schweizer Taschenmesser im Vergleich zu einem einfachen Messer (Roméo):

Parametrische Startpunkte: Roméo fragt: "Ist die Party sicher, wenn wir mit 5 Gästen starten?" Das neue Werkzeug fragt: "Wie viele Gäste dürfen wir maximal starten lassen, damit die Party sicher bleibt?" Es findet also auch die besten Startbedingungen.
Benutzer-Strategien: Sie können dem System sagen: "Wenn Schalter A und Schalter B gleichzeitig bereit sind, drücke immer zuerst A." Das neue Werkzeug simuliert genau das. Roméo müsste dafür das ganze System umgebaut werden.
Komplexe Fragen: Sie können Fragen stellen wie: "Ist es wahr, dass immer, wenn die Musik läuft, auch Licht an ist?" (Das nennt man "LTL-Model Checking"). Das neue Werkzeug kann das mit voller Logik prüfen.
Schneller als der Spezialist: Überraschenderweise war das neue, flexible Werkzeug in vielen Tests sogar schneller als der spezialisierte Roméo, besonders bei schwierigen Fällen, bei denen Roméo "aufgab" (Time-out).

Zusammenfassung in einem Satz

Die Forscher haben ein intelligentes, flexibles System entwickelt, das wie ein magischer Landkarten-Zeichner funktioniert: Es findet nicht nur heraus, ob ein zeitkritisches System funktioniert, sondern berechnet automatisch die perfekten Einstellungen (Parameter) dafür, und zwar schneller und genauer als die bisherigen Spezialisten, indem es unendliche Möglichkeiten clever "faltet" und zusammenfasst.

Das ist ein großer Schritt, um sicherzustellen, dass komplexe Systeme – von Robotern über Software bis hin zu biologischen Prozessen – genau so laufen, wie wir es uns wünschen, auch wenn wir nicht alle Zahlen im Voraus kennen.

1. Problemstellung

Die Arbeit adressiert die Herausforderungen bei der formalen Analyse und Parametersynthese von parametrischen Zeit-Petri-Netzen mit Inhibitor-Arcs (PITPNs).

Hintergrund: Zeit-Petri-Netze erweitern klassische Petri-Netze um Zeitintervalle für Transitionen. Bei PITPNs sind die Schranken dieser Intervalle nicht fest vorgegeben, sondern durch Parameter (z. B. $\lambda_1, \lambda_2$ ) definiert. Ziel ist es, Werte für diese Parameter zu finden, die bestimmte Systemeigenschaften erfüllen.
Limitierungen bestehender Tools: Der State-of-the-Art-Tool Roméo unterstützt zwar viele Analysemethoden (Erreichbarkeit, Lebendigkeit, zeitgebundene „Until"-Operatoren), hat jedoch signifikante Einschränkungen:
- Es unterstützt keine vollständigen (verschachtelten) temporalen Logikformeln (z. B. volles LTL).
- Es kann keine Synthese von parametrischen Initialmarkierungen durchführen.
- Die Analyse unter benutzerdefinierten Ausführungsstrategien (z. B. „wenn $t$ und $t'$ beide aktiv sind, feuere immer $t$ ") ist schwierig oder erfordert manuelle Modelländerungen.
- Es fehlt eine flexible Testumgebung für die schnelle Entwicklung neuer Analysealgorithmen.
Herausforderung bei Rewriting-Logik: Bisherige Ansätze mit Real-Time Maude für dichte Zeitsysteme leiden oft unter Unentscheidbarkeit oder Unvollständigkeit, wenn sie auf explizite Zustände und Zeit-Sampling angewendet werden (d. h. sie überspringen Zeitpunkte und sind daher in vielen Fällen unsound).

2. Methodik

Die Autoren entwickeln einen Framework, der Rewriting-Logik (implementiert in Maude) mit SMT-Solving (Satisfiability Modulo Theories) kombiniert, um eine sound und vollständige symbolische Analyse durchzuführen.

Semantik-Übergang:
1. Konkrete Semantik (R0, R1, R2): Zuerst wird eine „konkrete" Rewriting-Semantik für instanzierte PITPNs definiert. Diese verwendet Uhren (Clocks) statt abnehmender Zeitintervalle, um die Semantik aus [3] nachzubilden. Diese Modelle sind jedoch in Maude nicht direkt ausführbar, da der Zeitfortschritt ( $T$ ) eine Variable ist, die nicht gebunden wird.
2. Symbolische Semantik (RS1, RS2, RS3): Um das Problem zu lösen, wird eine symbolische Semantik entwickelt. Hier werden Zeitfortschritte und Parameter als SMT-Variablen behandelt. Zustände werden als beschränkte Terme (constrained terms) $\phi \parallel t$ dargestellt, wobei $t$ der Zustandszustand und $\phi$ eine SMT-Bedingung ist, die die möglichen Werte der Variablen einschränkt.
Symbolisches Folding (Zustandsreduktion):
- Ein Hauptproblem bei der symbolischen Suche ist die Terminierung. Selbst wenn der Zustandsklassengraph endlich ist, kann die symbolische Suche unendlich weiterlaufen, da neu erzeugte SMT-Variablen (z. B. für Uhrenwerte) dazu führen, dass logisch äquivalente Zustände syntaktisch unterschiedlich erscheinen.
- Neue Folding-Methode: Die Autoren entwickeln eine neue Subsumptions-Relation ( $\preceq$ ). Anstatt nur syntaktische Gleichheit zu prüfen, wird geprüft, ob ein Zustand $U$ $U$ durch einen bereits besuchten Zustand $V$ $V$ subsumiert wird. Dies geschieht durch:
  1. Abstraktion der Uhren- und Markierungswerte in frische Variablen.
  2. Eliminierung existentieller Quantoren (über die Zeitvariablen der Vergangenheit), um nur die aktuellen Parameter- und Uhrenwerte zu betrachten.
  3. Prüfung der logischen Implikation $\exists(U) \Rightarrow \exists(V)$ .
- Implementierung: Zwei Versionen werden implementiert:
  1. Eine Theorie-Transformation, die das Folding innerhalb eines Suchzweigs nutzt.
  2. Eine Meta-Level-Implementierung (BFS), die eine globale Menge besuchter Zustände über den gesamten Suchbaum hinweg verwaltet. Dies ermöglicht das Zusammenfassen äquivalenter Zustände aus verschiedenen Pfaden.
- Fourier-Motzkin-Elimination (FME): Um die Existenzquantoren zu eliminieren, wurde die FME-Prozedur als Gleichungstheorie in Maude implementiert. Dies macht den Ansatz unabhängig vom spezifischen SMT-Solver (im Gegensatz zur vorherigen Version, die nur Z3 nutzte).

3. Schlüsselbeiträge

Formale Korrektheit: Beweis der Bisimilarität zwischen der neuen Rewriting-Logik-Semantik und der „Standard"-Semantik von PITPNs.
Erweiterte Analysefähigkeiten: Das Framework unterstützt fast alle von Roméo unterstützten Analysen und geht darüber hinaus:
- Vollständiges LTL-Model Checking: Analyse verschachtelter temporaler Logikformeln.
- Synthese parametrischer Initialmarkierungen: Finden von Startzuständen (Anzahl der Token), die gewünschte Eigenschaften garantieren.
- Benutzerdefinierte Strategien: Analyse unter spezifischen Fire-Regeln (z. B. Priorisierung von Transitionen).
- Parametrische Zeitgrenzen: Synthese von Zeitgrenzen in temporalen Formeln.
Neues Folding-Verfahren: Ein sound und vollständiges Verfahren, das die Terminierung der Erreichbarkeitsanalyse garantiert, sobald der Zustandsklassengraph des PITPN endlich ist.
Flexibilität und Prototyping: Durch die Nutzung von Maudes Meta-Programmierungsfunktionen können neue Analysemethoden schnell entwickelt und getestet werden, ohne den Kern des Tools neu zu implementieren.

4. Ergebnisse und Benchmarking

Die Autoren verglichen ihr Framework mit Roméo (v3.9.4) und ihrer eigenen vorherigen Implementierung [35] an sechs PITPN-Beispielen (inkl. Producer-Consumer, Scheduling, Train-Systeme).

Performance:
- In vielen Fällen übertrifft das Maude-Framework (insbesondere mit dem SMT-Solver Yices2) Roméo in der Geschwindigkeit.
- Die Meta-Level-Folding-Implementierung löst Instanzen, bei denen Roméo in Endlosschleifen gerät (Timeout), weil Roméo unendliche Äste mit unbeschränkten Markierungen erkundet, während Maude durch das Folding terminiert.
- Die Verwendung von FME (statt Z3-spezifischer Quantorenelimination) führt zu einer signifikanten Leistungssteigerung gegenüber der Konferenzversion [35].
- Die Kombination mit Z3 und CVC4 ist langsamer als mit Yices2, aber dennoch funktionsfähig.
Ergebnisqualität:
- In einigen Fällen gab Roméo das Ergebnis „maybe" (Approximation) zurück oder fand keine Lösung, obwohl eine existierte. Maude fand in diesen Fällen gültige Lösungen, die durch Nachlaufen mit Roméo unter den von Maude gefundenen Constraints verifiziert wurden.
- Das Framework konnte erfolgreich Parameter für Initialmarkierungen synthetisieren, was Roméo nicht kann.

5. Bedeutung und Ausblick

Paradigmenwechsel: Die Arbeit zeigt, dass ein hochabstraktes „Interpreter"-Modell in Rewriting-Logik (mit Funktionen, Gleichungen und unbeschränkten Markierungen) durch symbolische Methoden und SMT in ein leistungsfähiges, soundes Analysewerkzeug für dichte Zeitsysteme umgewandelt werden kann.
Testumgebung: Das Framework dient als ideales „Testbett" für die schnelle Entwicklung und Evaluierung neuer Algorithmen für PITPNs, bevor diese in hochoptimierte C++-Tools wie Roméo integriert werden.
Zukunft: Als nächster Schritt planen die Autoren die Entwicklung eines vollständigen SMT-basierten Model Checkers für zeitliche LTL und CTL (um alle von Roméo unterstützten temporalen Operatoren abzudecken) sowie die Erweiterung der Strategie-Sprache.

Zusammenfassend bietet das Paper einen robusten, flexiblen und in vielen Fällen performanteren Ansatz zur formalen Analyse parametrischer Zeit-Petri-Netze, der die Lücken bestehender Tools schließt und neue Analysefähigkeiten eröffnet.