Cost-parity games are a fundamental tool in system design for the analysis of reactive and distributed systems that recently have received a lot of attention from the formal methods research community. They allow to reason about the time delay on the requests granted by systems, with a bounded consumption of resources, in their executions. In this paper, we contribute to research on cost-parity games by combining them with hierarchical systems, a successful method for the succinct representation of models. We show that determining the winner of a Hierarchical Cost-parity Game is PSPACE-complete, thus matching the complexity of the proper special case of Hierarchical Parity Games. This shows that reasoning about temporal delay can be addressed at a free cost in terms of complexity.

Hierarchical Cost-Parity Games / Bozzelli, Laura; Murano, Aniello; Perelli, Giuseppe; Sorrentino, Loredana. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 847:22(2020), pp. 147-174. [10.1016/j.tcs.2020.10.002]

Hierarchical Cost-Parity Games

Giuseppe Perelli
;
2020

Abstract

Cost-parity games are a fundamental tool in system design for the analysis of reactive and distributed systems that recently have received a lot of attention from the formal methods research community. They allow to reason about the time delay on the requests granted by systems, with a bounded consumption of resources, in their executions. In this paper, we contribute to research on cost-parity games by combining them with hierarchical systems, a successful method for the succinct representation of models. We show that determining the winner of a Hierarchical Cost-parity Game is PSPACE-complete, thus matching the complexity of the proper special case of Hierarchical Parity Games. This shows that reasoning about temporal delay can be addressed at a free cost in terms of complexity.
2020
Cost parity games; Formal Methods; Hierarchical Systems; Parity Games
01 Pubblicazione su rivista::01a Articolo in rivista
Hierarchical Cost-Parity Games / Bozzelli, Laura; Murano, Aniello; Perelli, Giuseppe; Sorrentino, Loredana. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 847:22(2020), pp. 147-174. [10.1016/j.tcs.2020.10.002]
File allegati a questo prodotto
File Dimensione Formato  
Bozzelli_Hierarchical_2020.pdf

solo gestori archivio

Tipologia: Versione editoriale (versione pubblicata con il layout dell'editore)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 818.98 kB
Formato Adobe PDF
818.98 kB Adobe PDF   Contatta l'autore
Bozzelli_preprint_Hierarchical_2020.pdf

accesso aperto

Note: https://doi.org/10.1016/j.tcs.2020.10.002
Tipologia: Documento in Pre-print (manoscritto inviato all'editore, precedente alla peer review)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 625.78 kB
Formato Adobe PDF
625.78 kB Adobe PDF

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/11573/1450621
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 0
social impact