2026-07-23T20:44:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7917 2024-03-06T10:41:34Z ddc:004 open_access

Hierarchical Cost-Parity Games Bozzelli, Laura Murano, Aniello Perelli, Giuseppe Sorrentino, Loredana Parity Games Cost-Parity Games Hierarchical Systems System Verification 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laura Bozzelli and Aniello Murano and Giuseppe Perelli and Loredana Sorrentino 2017 Is Part Of LIPIcs, Volume 90, 24th International Symposium on Temporal Representation and Reasoning (TIME 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.TIME.2017.6 urn:nbn:de:0030-drops-79175 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.6 eng https://creativecommons.org/licenses/by/3.0/legalcode