Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Berwanger, Dietmar; Doyen, Laurent http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-17427
URL:

;

On the Power of Imperfect Information

pdf-format:


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 =		{http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2008.1742},
  annote =	{Keywords: Infinite games, imperfect information}
}

Keywords: Infinite games, imperfect information
Seminar: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Issue date: 2008
Date of publication: 2008


DROPS-Home | Fulltext Search | Imprint Published by LZI