License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2008.1742
URN: urn:nbn:de:0030-drops-17427
Go to the corresponding LIPIcs Volume Portal

Berwanger, Dietmar ; Doyen, Laurent

On the Power of Imperfect Information

08004.BerwangerDietmar.1742.pdf (0.4 MB)


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

BibTeX - Entry

  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 =		{},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI