Abstract
We present a polynomial-time reduction
from parity games with imperfect information to safety games with imperfect information.
Similar reductions for games with perfect information typically
increase the game size exponentially. Our construction
avoids such a blow-up by using imperfect information to realise
succinct counters which cover a range exponentially larger than their size.
In particular, the reduction shows that the problem of
solving imperfect-information games with safety conditions is
\EXPTIME-complete.
BibTeX - Entry
@InProceedings{berwanger_et_al:LIPIcs:2008:1742,
author = {Dietmar Berwanger and Laurent Doyen},
title = {{On the Power of Imperfect Information}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
pages = {73--82},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-08-8},
ISSN = {1868-8969},
year = {2008},
volume = {2},
editor = {Ramesh Hariharan and Madhavan Mukund and V Vinay},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2008/1742},
URN = {urn:nbn:de:0030-drops-17427},
doi = {10.4230/LIPIcs.FSTTCS.2008.1742},
annote = {Keywords: Infinite games, imperfect information}
}
|
Keywords: |
|
Infinite games, imperfect information |
|
Collection: |
|
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science |
|
Issue Date: |
|
2008 |
|
Date of publication: |
|
05.12.2008 |
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)