Imperial College London
Portrait Picture

ProfessorMichaelHuth

Faculty of Engineering, Department of Computing

Head of the Department of Computing
 
 
 
//

Contact

 

m.huth Website

 
 
//

Location

 

Huxley 566Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@techreport{Huth:2012:10.25561/95101,
author = {Huth, MR and Kuo, JH-P and Piterman, N},
booktitle = {Departmental Technical Report: 12/1},
doi = {10.25561/95101},
publisher = {Department of Computing, Imperial College London},
title = {The rabin index of parity games},
url = {http://dx.doi.org/10.25561/95101},
year = {2012}
}
Download

RIS format (EndNote, RefMan)

TY  - RPRT
AB  - We study the descriptive complexity of parity games by taking intoaccount the coloring of their game graphs whilst ignoring their owner-ship structure. Di erent colorings of the same graph are identi ed ifthey determine the same winning regions and strategies, for all ownershipstructures of nodes. The Rabin index of a parity game is the minimum ofthe maximal color taken over all equivalent coloring functions. We showthat deciding whether the Rabin index is at least k is in P for k = 1but NP-hard for all  xed k   2. We present an EXPTIME algorithmthat computes the Rabin index by simplifying its input coloring function.When replacing simple cycle with cycle detection in that algorithm, itsoutput over-approximates the Rabin index in polynomial time. Experi-mental results show that this approximation yields good values in practice.
AU  - Huth,MR
AU  - Kuo,JH-P
AU  - Piterman,N
DO  - 10.25561/95101
PB  - Department of Computing, Imperial College London
PY  - 2012///
TI  - The rabin index of parity games
T1  - Departmental Technical Report: 12/1
UR  - http://dx.doi.org/10.25561/95101
UR  - http://hdl.handle.net/10044/1/95101
ER  -
Download