TL;DR
This paper summarizes the Reactive Synthesis Competition (SYNTCOMP) from 2018 to 2021, detailing its evaluation setup, new benchmarks, and participating tools. It analyzes the performance of these tools, highlighting trends in reactive synthesis capabilities and identifying key strategies that lead to success.
What Problem Does This Paper Address?
Reactive systems are crucial in many applications, but automatically generating them from formal specifications (reactive synthesis) is a complex challenge. The SYNTCOMP competition aims to drive progress in this field by fostering the development of robust, scalable, and user-friendly synthesis tools. This paper addresses the need to track and analyze the advancements in reactive synthesis tools and techniques over a four-year period, providing insights into the state-of-the-art and identifying promising research directions.
Methods
The paper details the SYNTCOMP evaluation scheme, which involves participants submitting tools to solve realizability and synthesis problems for various specification formats (safety, parity, and LTL). Tools are ranked based on the number of correctly solved problems within a time limit, and for synthesis, also on the quality of the generated solution (measured by the size of the resulting circuit). The competition utilizes a standardized benchmark library and an online platform (StarExec) for execution. The paper also categorizes the participating tools based on their underlying synthesis approaches, primarily distinguishing between "bounded synthesis" and the "Owl-Pig" approach.
Datasets
The paper discusses the SYNTCOMP library, which is continuously expanded with benchmarks from participant research, literature, and automatic generation. New benchmark classes were added to the library between 2018 and 2021, including:
- LTL benchmarks: Temporal Stream Logic (TSL) benchmarks and LTL specifications encoded in the Temporal Logic Synthesis Format (TLSF) were used, with parameterized families for scalability testing.
- Safety benchmarks: Random benchmarks were systematically generated using extended AIGER format.
- Parity benchmarks: LTL specifications were translated into deterministic parity automata, and combinatorially hard benchmarks were generated using the PGSolver parity-game suite.
Key Insights and Ideas
- Dominance of Owl-Pig in LTL: Tools employing the "Owl-Pig" approach (which translates LTL to deterministic parity automata and then solves parity games) have consistently dominated the LTL tracks, with Strix and Ltlsynt being top performers.
- Importance of LTL Rewriting and Decomposition: Techniques like LTL specification rewriting, decomposition, and on-the-fly automaton construction appear to be critical for achieving high performance in LTL synthesis.
- Parity Games Need More Challenging Benchmarks: The parity game tracks require more interesting and challenging benchmarks to effectively differentiate tools and drive progress.
- Symbolic Algorithms Excel for Practical Parity Games: For parity games derived from practical examples, purely symbolic algorithms perform very well.
- Bounded Synthesis vs. Owl-Pig Trade-offs: Bounded synthesis tools tend to handle longer LTL formulas, while Owl-Pig solvers are more affected by the complexity of the automaton construction.
- Tool Evolution and Transfer: Successful techniques can be transferred between tools within the same class, as seen with BoSy adopting Party/Kid's approach.
Key Results
- Performance Improvement: The competition has seen a measurable improvement in the performance of top solvers across tracks, with more tools solving more benchmarks each year.
- Benchmark Growth: The SYNTCOMP benchmark library has grown significantly, with over 900 LTL benchmarks in 2021.
- LTL Track Dominance: Strix consistently ranked first in the LTL track from 2018 to 2021, demonstrating strong performance in both realizability and synthesis.
- Parity Track Insights: Knor-BDD, a configuration of Knor, significantly outperformed other tools in the parity track by switching to a symbolic representation of the game, solving almost all benchmarks.
- Scalability Testing: Parameterized LTL benchmark families were used to test tool scalability, revealing that while Strix is generally strong, other tools can be more efficient for specific types of specifications (e.g., mux and shift).
Limitations and Future Work
- Safety Track Stagnation: The safety track has seen minimal participation and updates in recent years, suggesting a need for renewed focus or new benchmark classes.
- Parity Benchmark Needs: The parity game tracks require more challenging benchmarks to better distinguish tool capabilities.
- Future SYNTCOMP Editions: Future editions will aim to replicate the success of the parity game track and update competition rules to maintain interest. This includes making all submitted benchmarks publicly available under a CC-BY license.
- Parallel vs. Sequential Execution: Future editions will differentiate between parallel and sequential execution by having separate rankings based on wall-clock time and user-CPU time, respectively.
- Platform Continuity: SYNTCOMP will continue to use StarExec for hosting, with potential re-evaluation of alternative frameworks in the future.
Summary updated