Optimal reachability for weighted timed games

Rajeev Alur, Mikhail Bernadsky, P. Madhusudan

Research output: Chapter in Book/Report/Conference proceedingChapter

Abstract

Weighted timed automata are timed automata annotated with costs on locations and transitions. The optimal game-reachability problem for these automata is to find the best-cost strategy of supplying the inputs so as to ensure reachability of a target set within a specified number of iterations. The only known complexity bound for this problem is a doubly-exponential upper bound. We establish a singly-exponential upper bound and show that there exist automata with exponentially many states in a single region with pair-wise distinct optimal strategies.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsJosep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella
PublisherSpringer-Verlag Berlin Heidelberg
Pages122-133
Number of pages12
ISBN (Print)3540228497
DOIs
StatePublished - 2004

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3142
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Optimal reachability for weighted timed games'. Together they form a unique fingerprint.

  • Cite this

    Alur, R., Bernadsky, M., & Madhusudan, P. (2004). Optimal reachability for weighted timed games. In J. Díaz, J. Karhumäki, A. Lepistö, & D. Sannella (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 122-133). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3142). Springer-Verlag Berlin Heidelberg. https://doi.org/10.1007/978-3-540-27836-8_13