Memory Reduction via Delayed Simulation

Details Memory Reduction via Delayed Simulation Memory Reduction via Delayed Simulation

2011-02-21

arxiv.org/abs/1102.4120v1

EPTCS 50, 2011, pp. 46-60

Computer Science

Computer Science and Game Theory

In Proceedings iWIGP 2011, arXiv:1102.3741

Scientific paper

10.4204/EPTCS.50.4

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.

Affiliated with

Also associated with

No associations

Rating

Memory Reduction via Delayed Simulation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Memory Reduction via Delayed Simulation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory Reduction via Delayed Simulation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-519861