A Faster Algorithm for Solving One-Clock Priced Timed Games

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

One-clock priced timed games is a class of two-player, zero-sum, continuous-time games that was defined and thoroughly studied in previous works. We show that one-clock priced timed games can be solved in time m 12 n n O(1), where n is the number of states and m is the number of actions. The best previously known time bound for solving one-clock priced timed games was 2O(n2+m) , due to Rutkowski. For our improvement, we introduce and study a new algorithm for solving one-clock priced timed games, based on the sweep-line technique from computational geometry and the strategy iteration paradigm from the algorithmic theory of Markov decision processes. As a corollary, we also improve the analysis of previous algorithms due to Bouyer, Cassez, Fleury, and Larsen; and Alur, Bernadsky, and Madhusudan.
Original languageEnglish
Title of host publicationCONCUR 2013 – Concurrency Theory : 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings
EditorsPedro R. D*Argenio, Hernán Melgratti
Number of pages15
PublisherSpringer VS
Publication year2013
Pages531-545
ISBN (print)978-3-642-40183-1
ISBN (Electronic)978-3-642-40184-8
DOIs
Publication statusPublished - 2013
EventInternational Conference on Currency Theory - Buenos Aires, Argentina
Duration: 27 Aug 201330 Aug 2013
Conference number: 24

Conference

ConferenceInternational Conference on Currency Theory
Nummer24
LandArgentina
ByBuenos Aires
Periode27/08/201330/08/2013
SeriesLecture Notes in Computer Science
Volume8052
ISSN0302-9743

See relations at Aarhus University Citationformats

ID: 55794294