文章基本信息

标题：Hierarchical Cost-Parity Games
本地全文：下载
作者：Laura Bozzelli ; Aniello Murano ; Giuseppe Perelli 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：90
页码：6:1-6:17
DOI：10.4230/LIPIcs.TIME.2017.6
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Parity Games; Cost-Parity Games; Hierarchical Systems; System Verification