Quantitative Games on Probabilistic Timed Automata

Details Quantitative Games on Probabilistic Timed Automata Quantitative Games on Probabilistic Timed Automata

2010-01-12

arxiv.org/abs/1001.1933v2

Computer Science

Computer Science and Game Theory

Scientific paper

Two-player zero-sum games are a well-established model for synthesising controllers that optimise some performance criterion. In such games one player represents the controller, while the other describes the (adversarial) environment, and controller synthesis corresponds to computing the optimal strategies of the controller for a given criterion. Asarin and Maler initiated the study of quantitative games on (non-probabilistic) timed automata by synthesising controllers which optimise the time to reach a final state. The correctness and termination of their approach was dependent on exploiting the properties of a special class of functions, called simple functions, that can be finitely represented. In this paper we consider quantitative games over probabilistic timed automata. Since the concept of simple functions is not sufficient to solve games in this setting, we generalise simple functions to so-called quasi-simple functions. Then, using this class of functions, we demonstrate that the problem of solving games with either expected reachability-time or expected discounted-time criteria on probabilistic timed automata are in NEXPTIME $\cap$ co-NEXPTIME.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-459529