Formats of Winning Strategies for Six Types of Pushdown Games

Details Formats of Winning Strategies for Six Types of Pushdown Games Formats of Winning Strategies for Six Types of Pushdown Games

2010-06-08

arxiv.org/abs/1006.1415v1

EPTCS 25, 2010, pp. 132-145

Computer Science

Computer Science and Game Theory

Scientific paper

10.4204/EPTCS.25.14

The solution of parity games over pushdown graphs (Walukiewicz '96) was the first step towards an effective theory of infinite-state games. It was shown that winning strategies for pushdown games can be implemented again as pushdown automata. We continue this study and investigate the connection between game presentations and winning strategies in altogether six cases of game arenas, among them realtime pushdown systems, visibly pushdown systems, and counter systems. In four cases we show by a uniform proof method that we obtain strategies implementable by the same type of pushdown machine as given in the game arena. We prove that for the two remaining cases this correspondence fails. In the conclusion we address the question of an abstract criterion that explains the results.

Affiliated with

Also associated with

No associations

Rating

Formats of Winning Strategies for Six Types of Pushdown Games 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 Formats of Winning Strategies for Six Types of Pushdown Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Formats of Winning Strategies for Six Types of Pushdown Games will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-29353