## Abstract

Many problems in formal methods can be formalized as two-player games. For several applications-program synthesis, for example-in addition to determining which player wins the game, we are interested 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, described by a quantified formula, 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, described by a pair of formulas defining the legal moves of each player, 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.

Original language | English (US) |
---|---|

Article number | 61 |

Journal | Proceedings of the ACM on Programming Languages |

Volume | 2 |

Issue number | POPL |

DOIs | |

State | Published - Jan 2018 |

## All Science Journal Classification (ASJC) codes

- Software
- Safety, Risk, Reliability and Quality

## Keywords

- Functional synthesis
- Logical games
- Reactive synthesis