Current browse context:
cs.LO
Change to browse by:
References & Citations
Computer Science > Logic in Computer Science
Title: Complete Game Logic with Sabotage
(Submitted on 15 Apr 2024)
Abstract: We introduce Sabotage Game Logic ($\mathsf{GL_s}$), a simple and natural extension of Parikh's Game Logic with a single additional primitive, which allows players to lay traps for the opponent to avoid. $\mathsf{GL_s}$ can be used to model infinite sabotage games, in which players can change the rules during game play. In contrast to Game Logic, which is strictly less expressive, GLs is exactly as expressive as the modal $\mu$-calculus. This reveals a close connection between the entangled nested recursion inherent in modal fixpoint logics and adversarial dynamic rule changes characteristic for sabotage games. Additionally we present a natural Hilbert-style proof calculus for $\mathsf{GL_s}$ and prove completeness. The completeness of an extension of Parikh's calculus for Game Logic follows.
Link back to: arXiv, form interface, contact.