LIPIcs.FSTTCS.2008.1742.pdf
- Filesize: 416 kB
- 10 pages
Document
On the Power of Imperfect Information
Authors
-
Part of:
Volume:
IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2008)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license
- Publication Date: 2008-12-05
Cite AsGet BibTex
Dietmar Berwanger and Laurent Doyen. On the Power of Imperfect Information. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 2, pp. 73-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1742
https://doi.org/10.4230/LIPIcs.FSTTCS.2008.1742
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.
Keywords
- Infinite games
- imperfect information
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads