Modal logics of sabotage revisited

Abstract : Sabotage modal logic was proposed in 2003 as a format for analyzing games that modify graphs they are played on. We investigate some model-theoretic and proof-theoretic aspects of sabotage modal logic, which has come to be viewed as an early dynamic logic of graph change. Our first result is a characterization theorem for sabotage modal logic as a fragment of first-order logic which is invariant with respect to a natural notion of 'sabotage bisimulation'. Next, we offer a sound and complete tableau method and its associated labeled sequent calculus for analyzing reasoning in sabotage modal logic. Finally, we identify and briefly explore a number of open research problems concerning sabotage modal logic that illuminate its complexity, placing it within the current landscape of modal logics that analyze model update, and, returning to the original motivation of sabotage, fixed-point logics for network games.
Type de document :
Article dans une revue
Journal of Logic and Computation, Oxford University Press (OUP), 2018, 28 (2), pp.269 - 303. 〈10.1093/logcom/exx034〉
Liste complète des métadonnées

Littérature citée [9 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01827076
Contributeur : Guillaume Aucher <>
Soumis le : dimanche 1 juillet 2018 - 14:30:06
Dernière modification le : vendredi 16 novembre 2018 - 01:26:03
Document(s) archivé(s) le : lundi 1 octobre 2018 - 03:35:11

Fichier

RevisedProof.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Guillaume Aucher, Johan Van Benthem, Davide Grossi. Modal logics of sabotage revisited. Journal of Logic and Computation, Oxford University Press (OUP), 2018, 28 (2), pp.269 - 303. 〈10.1093/logcom/exx034〉. 〈hal-01827076〉

Partager

Métriques

Consultations de la notice

312

Téléchargements de fichiers

41