Journal article

Expected reachability-time games

Abstract:: Probabilistic timed automata are a suitable formalism to model systems with real-time, nondeterministic and probabilistic behaviour. We study two-player zero-sum games on such automata where the objective of the game is specified as the expected time to reach a target. The two players—called player Min and player Max—compete by proposing timed moves simultaneously and the move with a shorter delay is performed. The first player attempts to minimise the given objective while the second tries to maximise the objective. We observe that these games are not determined, and study decision problems related to computing the upper and lower values, showing that the problems are decidable and lie in the complexity class NEXPTIME ∩ co-NEXPTIME

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Forejt, V., Kwiatkowska, M., Norman, G., & Trivedi, A. (2016). Expected reachability-time games. Theoretical Computer Science, 631, 139–160.

MLA Style

Forejt, V, et al. “Expected Reachability-Time Games.” Theoretical Computer Science, vol. 631, 2016, pp. 139–60.

Chicago Style

Forejt, V, M Kwiatkowska, G Norman, and A Trivedi. 2016. “Expected Reachability-Time Games.” Theoretical Computer Science 631: 139–60.
Print

Access Document

Files:: Expected reachability-time games.pdf

(Preview, Version of record, pdf, 710.3KB, Terms of use)

Publisher copy:: 10.1016/j.tcs.2016.04.021

Authors

+ Forejt, V More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Kwiatkowska, M More by this author

Institution:: University of Oxford
Division:: MPLS
Department:: Computer Science
Role:: Author

+ Norman, G More by this author

Role:: Author

+ Trivedi, A More by this author

Role:: Author

+ Engineering and Physical Sciences Research Council More from this funder

Grant:: EP/M023656/1

+ European Research Council More from this funder

Grant:: Advanced Grant VERIWARE

Publisher:: Elsevier
Journal:: Theoretical Computer Science More from this journal
Volume:: 631
Pages:: 139–160
Publication date:: 2016-01-01
Acceptance date:: 2016-04-15
DOI:: 10.1016/j.tcs.2016.04.021
ISSN:: 0304-3975

Keywords:: two-player games

controller synthesis

competitive optimisation

probabilistic timed automata
Pubs id:: pubs:615402
UUID:: uuid:0c887132-2027-4d95-ad0c-2a29acf5c9ab
Local pid:: pubs:615402
Source identifiers:: 615402
Deposit date:: 2016-04-15
ARK identifier:: ark:/29072/ora_0c88713220274d95ad0c2a29acf5c9ab

Terms of use

Copyright holder:: Forejt et al
Copyright date:: 2016
Notes:: Copyright © 2016 The Authors. Published by Elsevier B.V. Under a Creative Commons license.

Licence:: CC Attribution (CC BY)

Views and Downloads

About views and downloads

If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP