The reactive synthesis competition (syntcomp): 2018–2021
We report on the last four editions of the reactive synthesis competition (SYNTCOMP 2018–
2021). We briefly describe the evaluation scheme and the experimental setup of …
2021). We briefly describe the evaluation scheme and the experimental setup of …
Guessing winning policies in LTL synthesis by semantic learning
We provide a learning-based technique for guessing a winning strategy in a parity game
originating from an LTL synthesis problem. A cheaply obtained guess can be useful in …
originating from an LTL synthesis problem. A cheaply obtained guess can be useful in …
On Alternating-Time Temporal Logic, Hyperproperties, and Strategy Sharing
R Beutner, B Finkbeiner - Proceedings of the AAAI Conference on …, 2024 - ojs.aaai.org
Alternating-time temporal logic (ATL*) is a well-established framework for formal reasoning
about multi-agent systems. However, while ATL* can reason about the strategic ability of …
about multi-agent systems. However, while ATL* can reason about the strategic ability of …
A recursive approach to solving parity games in quasipolynomial time
Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest
among the many existing parity game algorithms. However, its complexity is exponential …
among the many existing parity game algorithms. However, its complexity is exponential …
Reactive synthesis from LTL specification with Spot
T Michaud, M Colange - Proceedings of the 7th Workshop on Synthesis …, 2018 - hal.science
We present\textttltlsynt, a new tool for reactive synthesis from LTL specifications. It relies on
the efficiency of Spot to translate the input LTL specification to a deterministic parity …
the efficiency of Spot to translate the input LTL specification to a deterministic parity …
Parity games: Zielonka's algorithm in quasi-polynomial time
P Parys - arXiv preprint arXiv:1904.12446, 2019 - arxiv.org
Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time
algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial …
algorithm solving parity games. After this breakthrough result, a few other quasi-polynomial …
Rabin games and colourful universal trees
We provide an algorithm to solve Rabin and Streett games over graphs with n vertices, m
edges, and k colours that runs in O~ mn (k!) 1+ o (1) time and O (nk log k log n) space …
edges, and k colours that runs in O~ mn (k!) 1+ o (1) time and O (nk log k log n) space …
From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism
A Casares, T Colcombet, N Fijalkow… - …, 2024 - theoretics.episciences.org
We study transformations of automata and games using Muller conditions into equivalent
ones using parity or Rabin conditions. We present two transformations, one that turns a …
ones using parity or Rabin conditions. We present two transformations, one that turns a …
Knor: reactive synthesis using Oink
T van Dijk, F van Abbema, N Tomov - … on Tools and Algorithms for the …, 2024 - Springer
We present an innovative approach to the reactive synthesis of parity automaton
specifications, which plays a pivotal role in the synthesis of linear temporal logic. We find …
specifications, which plays a pivotal role in the synthesis of linear temporal logic. We find …
Attracting tangles to solve parity games
T van Dijk - … Aided Verification: 30th International Conference, CAV …, 2018 - Springer
Parity games have important practical applications in formal verification and synthesis,
especially to solve the model-checking problem of the modal mu-calculus. They are also …
especially to solve the model-checking problem of the modal mu-calculus. They are also …