Please use this identifier to cite or link to this item:
Title: The Rabin index of parity games
Authors: Huth, M
Kuo, JHP
Piterman, N
First Published: 17-Jul-2013
Publisher: Open Publishing Association
Citation: EPTCS 119, 2013, pp. 35-49, 2013
Abstract: We study the descriptive complexity of parity games by taking into account the coloring of their game graphs whilst ignoring their ownership structure. Colored game graphs are identified if they determine the same winning regions and strategies, for all ownership structures of nodes. The Rabin index of a parity game is the minimum of the maximal color taken over all equivalent coloring functions. We show that deciding whether the Rabin index is at least k is in PTIME for k=1 but NP-hard for all fixed k > 1. We present an EXPTIME algorithm that computes the Rabin index by simplifying its input coloring function. When replacing simple cycle with cycle detection in that algorithm, its output over-approximates the Rabin index in polynomial time. Experimental results show that this approximation yields good values in practice.
DOI Link: 10.4204/EPTCS.119.6
Version: Publisher Version
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © M. Huth, J. H. Kuo & N. Piterman. This work is licensed under the Creative Commons Attribution License ( ), which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Description: In Proceedings GandALF 2013, arXiv:1307.4162
Appears in Collections:Published Articles, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
1307.4466v1.pdfPost-review (final submitted)224.71 kBAdobe PDFView/Open
GANDALF2013.6.pdfPublished (publisher PDF)224.71 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.