Memory Reduction via Delayed Simulation
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 regula...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2011-02-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1102.4120v1 |
| _version_ | 1811250092675432448 |
|---|---|
| author | Michael Holtmann Marcus Gelderie |
| author_facet | Michael Holtmann Marcus Gelderie |
| author_sort | Michael Holtmann |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-12T15:57:53Z |
| format | Article |
| id | doaj.art-10e1b8494ab04a849b02861e86ad864d |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-12T15:57:53Z |
| publishDate | 2011-02-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-10e1b8494ab04a849b02861e86ad864d2022-12-22T03:26:17ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802011-02-0150Proc. iWIGP 2011466010.4204/EPTCS.50.4Memory Reduction via Delayed SimulationMichael HoltmannMarcus GelderieWe 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.http://arxiv.org/pdf/1102.4120v1 |
| spellingShingle | Michael Holtmann Marcus Gelderie Memory Reduction via Delayed Simulation Electronic Proceedings in Theoretical Computer Science |
| title | Memory Reduction via Delayed Simulation |
| title_full | Memory Reduction via Delayed Simulation |
| title_fullStr | Memory Reduction via Delayed Simulation |
| title_full_unstemmed | Memory Reduction via Delayed Simulation |
| title_short | Memory Reduction via Delayed Simulation |
| title_sort | memory reduction via delayed simulation |
| url | http://arxiv.org/pdf/1102.4120v1 |
| work_keys_str_mv | AT michaelholtmann memoryreductionviadelayedsimulation AT marcusgelderie memoryreductionviadelayedsimulation |