Constructive Game Logic
Authors:
- Rose BohrerRBRose Bohrer
- André PlatzerAPAndré Platzer
- Brandon BohrerBBBrandon Bohrer
Open Access
- 18 April 2020
- book chapter
- Published by Springer Nature
- Vol. 12075, 84-111
Abstract
Game Logic is an excellent setting to study proofs-about-programs via the interpretation of those proofs as programs, because constructive proofs for games correspond to effective winning strategies to follow in response to the opponent’s actions. We thus develop Constructive Game Logic, which extends Parikh’s Game Logic (GL) with constructivity and with first-order programs à la Pratt’s first-order dynamic logic (DL). Our major contributions include: 1. a novel realizability semantics capturing the adversarial dynamics of games, 2. a natural deduction calculus and operational semantics describing the computational meaning of strategies via proof-terms, and 3. theoretical results including soundness of the proof calculus w.r.t. realizability semantics, progress and preservation of the operational semantics of proofs, and Existential Properties on support of the extraction of computational artifacts from game proofs. Together, these results provide the most general account of a Curry-Howard interpretation for any program logic to date, and the first at all for Game Logic.Keywords
All Related Versions
This publication has 42 references indexed in Scilit:
- Toward a Theory of Play: A Logical Perspective on Games and InteractionGames, 2011
- Towards intuitionistic dynamic logicLogic and Logical Philosophy, 2007
- Tableaux for constructive concurrent dynamic logicAnnals of Pure and Applied Logic, 2005
- Alternating-time temporal logicJournal of the ACM, 2002
- Realizability: a historical essayMathematical Structures in Computer Science, 2002
- A Modal Logic for Coalitional Power in GamesJournal of Logic and Computation, 2002
- Games in Dynamic‐Epistemic LogicBulletin of Economic Research, 2001
- Concurrent dynamic logicJournal of the ACM, 1987
- An axiomatic basis for computer programmingCommunications of the ACM, 1969
- Definability and decision problems in arithmeticThe Journal of Symbolic Logic, 1949