Model-Guided Synthesis for LTL over Finite Traces
Satisfiability and synthesis are two fundamental problems for Linear Temporal Logic, both of which can be solved on the automaton constructed from the input formula. In general, satisfiability is easier than synthesis in both theory and practice, as satisfiability needs only to find a satisfying trace, while synthesis has to find a winning strategy. This paper presents a novel technique called MoGuS, which improves the run-time synthesis of LTLf, a variant of LTL interpreted over finite traces, by repeatedly invoking an LTLf satisfiability checker to guide its search for a winning strategy. Such checkers have not been used before in the context of LTLf synthesis. MoGuS computes a satisfying trace of the input formula, and then uses the formula-progression technique to compute the states on the fly in the automaton run. It then checks whether there exists a winning strategy from each of the states. If not, the current state is identified as a failure state, through which can never produce a winning strategy. Then the checking rolls back to its predecessor state and the checking repeats again. MoGuS returns ‘Realizable’ if the initial state turns out to be winning, and `Unrealizable’ otherwise. We conducted an extensive experimental evaluation of MoGuS by comparing it to different state-of-the-art LTLf synthesis algorithms on a large set of benchmarks. The results show that MoGuS has the most stable and the best overall performance on the tested benchmarks.
Mon 15 JanDisplayed time zone: London change
14:00 - 15:30 | Session 3: Security and Privacy, Model Checking and SynthesisVMCAI at Marconi Room Chair(s): Caterina Urban Inria & École Normale Supérieure | Université PSL | ||
14:00 20mTalk | Automatic and Incremental Repair for Speculative Information Leaks VMCAI Joachim Bard CISPA Helmholtz Center for Information Security, Swen Jacobs CISPA, Yakir Vizel Technion—Israel Institute of Technology | ||
14:20 20mTalk | Sound Abstract Nonexploitability Analysis VMCAI Pre-print | ||
14:40 20mTalk | Solving Two-Player Games under Progress Assumptions VMCAI Anne-Kathrin Schmuck MPI-SWS, K. S. Thejaswini The University of Warwick, Irmak Saglam Max Planck Institute for Software Systems (MPI-SWS), Satya Prakash Nayak Max Planck Institute for Software Systems (MPI-SWS) Pre-print | ||
15:00 20mTalk | Model-Guided Synthesis for LTL over Finite Traces VMCAI Shengping Xiao East China Normal University, Yongkang Li East China Normal University, Xinyue Huang East China Normal University, Yicong Xu East China Normal University, Jianwen Li East China Normal University, China, Geguang Pu East China Normal University, Ofer Strichman Technion, Moshe Vardi Rice University | ||
15:20 10mTalk | Generic Model Checking for Modal Fixpoint Logics in COOL-MC VMCAI Daniel Hausmann University of Gothenburg, Merlin Humml Friedrich-Alexander Universität Erlangen-Nürnberg, Simon Prucker Friedrich-Alexander Universität Erlangen-Nürnberg, Lutz Schröder University of Erlangen-Nuremberg, Aaron Strahlberger Friedrich-Alexander-Universität Erlangen-Nürnberg Pre-print |