Two-Player Reachability-Price Games on Single-Clock Timed Automata

Details Two-Player Reachability-Price Games on Single-Clock Timed Automata Two-Player Reachability-Price Games on Single-Clock Timed Automata

2011-07-06

arxiv.org/abs/1107.1199v1

EPTCS 57, 2011, pp. 31-46

Computer Science

Computer Science and Game Theory

In Proceedings QAPL 2011, arXiv:1107.0746

Scientific paper

10.4204/EPTCS.57.3

We study two player reachability-price games on single-clock timed automata. The problem is as follows: given a state of the automaton, determine whether the first player can guarantee reaching one of the designated goal locations. If a goal location can be reached then we also want to compute the optimum price of doing so. Our contribution is twofold. First, we develop a theory of cost functions, which provide a comprehensive methodology for the analysis of this problem. This theory allows us to establish our second contribution, an EXPTIME algorithm for computing the optimum reachability price, which improves the existing 3EXPTIME upper bound.

Affiliated with

Also associated with

No associations

Rating

Two-Player Reachability-Price Games on Single-Clock Timed Automata 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 Two-Player Reachability-Price Games on Single-Clock Timed Automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Two-Player Reachability-Price Games on Single-Clock Timed Automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-678822