Many problems in formal methods can be formalized as two-player games. For several applications, program synthesis for example, we are interested not just in the determining which player wins the game, but in computing a winning strategy for that player. This paper studies the strategy synthesis problem for games defined within the theory of linear rational arithmetic. Two types of games are considered. A satisfiability game is described by a quantified formula, and is played by two players that take turns instantiating quantifiers. The objective of each player is to prove (or disprove) satisfiability of the formula. A reachability game is described by a pair of formulas defining the legal moves of each player, and is played by two players that take turns choosing positions – rational vectors of some fixed dimension. The objective of each player is to reach a position where the opposing player has no legal moves (or to play the game forever). We give a complete algorithm for synthesizing winning strategies for satisfiability games and a sound (but necessarily incomplete) algorithm for synthesizing winning strategies for reachability games.
Fri 12 JanDisplayed time zone: Tijuana, Baja California change
15:50 - 17:05 | SynthesisResearch Papers at Bunker Hill Chair(s): Nadia Polikarpova University of California, San Diego | ||
15:50 25mTalk | Strategy Synthesis for Linear Arithmetic Games Research Papers | ||
16:15 25mTalk | Bonsai: Synthesis-Based Reasoning for Type Systems Research Papers | ||
16:40 25mTalk | Program Synthesis using Abstraction Refinement Research Papers |