In this paper we advance the state of the art on the subject of bisimulations for logics of strategies. Bisimulations are a key notion to study the expressive power of a modal language, as well as for applications to system verification. In this contribution we present novel notions of bisimulation for several significant fragments of Strategy Logic (SL), and prove that they preserve the interpretation of formulas in the corresponding fragments. In selected cases we are able to prove that such bisimulations enjoy the Hennessy-Milner property. Finally, we make use of bisimulations to study the expressiveness of the various fragment of SL, including the complexity of their model checking problems.

Bisimulations for Logics of Strategies: A Study in Expressiveness and Verification / Belardinelli, Francesco; Dima, Catalin; Murano, Aniello. - (2018), pp. 425-434. (Intervento presentato al convegno Proceedingsof the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2018 tenutosi a Tempe, Arizona, nel 30 October - 2 November 2018.).

Bisimulations for Logics of Strategies: A Study in Expressiveness and Verification

Aniello Murano
Membro del Collaboration Group
2018

Abstract

In this paper we advance the state of the art on the subject of bisimulations for logics of strategies. Bisimulations are a key notion to study the expressive power of a modal language, as well as for applications to system verification. In this contribution we present novel notions of bisimulation for several significant fragments of Strategy Logic (SL), and prove that they preserve the interpretation of formulas in the corresponding fragments. In selected cases we are able to prove that such bisimulations enjoy the Hennessy-Milner property. Finally, we make use of bisimulations to study the expressiveness of the various fragment of SL, including the complexity of their model checking problems.
2018
978-157735803-9
Bisimulations for Logics of Strategies: A Study in Expressiveness and Verification / Belardinelli, Francesco; Dima, Catalin; Murano, Aniello. - (2018), pp. 425-434. (Intervento presentato al convegno Proceedingsof the Sixteenth International Conference on Principles of Knowledge Representation and Reasoning, KR 2018 tenutosi a Tempe, Arizona, nel 30 October - 2 November 2018.).
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11588/843906
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 7
social impact