Tableaux for Realizability of Safety Specifications

Abstract

We introduce a tableau decision method for deciding realizability of specifications expressed in a safety fragment of LTL that includes bounded future temporal operators. Tableau decision procedures for temporal and modal logics have been thoroughly studied for satisfiability and for translating temporal formulae into equivalent Büchi automata, and also for model checking, where a specification and system are provided. However, to the best of our knowledge no tableau method has been studied for the reactive synthesis problem. Reactive synthesis starts from a specification where propositional variables are split into those controlled by the environment and those controlled by the system, and consists on automatically producing a system that guarantees the specification for all environments. Realizability is the decision problem of whether there is one such system. In this paper, we present a method to decide realizability of safety specifi- cations, from which we can also extract (i.e., synthesize) a correct system (in case the specification is realizable). The main novelty of a tableau method is that it can be easily extended to handle richer domains (inte- gers, etc) and bounds in the temporal operators in ways that automata approaches for synthesis cannot.