Home » Publication » 23003

Dettaglio pubblicazione


Hierarchical Cost-Parity Games (01a Articolo in rivista)

Bozzelli Laura, Murano Aniello, Perelli Giuseppe, Sorrentino Loredana

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.
© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma