Memory Reduction via Delayed Simulation

Marcus Gelderie
(RWTH Aachen University)
Michael Holtmann
(RWTH Aachen University)

We address a central (and classical) issue in the theory of infinite games: the reduction of the memory size that is needed to implement winning strategies in regular infinite games (i.e., controllers that ensure correct behavior against actions of the environment, when the specification is a regular omega-language). We propose an approach which attacks this problem before the construction of a strategy, by first reducing the game graph that is obtained from the specification. For the cases of specifications represented by "request-response"-requirements and general "fairness" conditions, we show that an exponential gain in the size of memory is possible.

In Johannes Reich and Bernd Finkbeiner: Proceedings International Workshop on Interactions, Games and Protocols (iWIGP 2011), Saarbrücken, Germany, 27th March 2011, Electronic Proceedings in Theoretical Computer Science 50, pp. 46–60.
Published: 18th February 2011.

ArXived at: http://dx.doi.org/10.4204/EPTCS.50.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org