Name
Abstract | ||
|---|---|---|
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 12nnO(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 $2^{O(n^2+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. |
Year | DOI | Venue |
|---|---|---|
2013 | 10.1007/978-3-642-40184-8_37 | international conference on concurrency theory |
Keywords | DocType | Volume |
computational geometry,markov decision process,strategy iteration paradigm,sweep-line technique,continuous-time game,algorithmic theory,time m,new algorithm,previous work,previous algorithm,faster algorithm | Conference | abs/1201.3498 |
Citations | PageRank | References |
6 | 0.49 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Thomas Dueholm Hansen | 1 | 161 | 13.77 |
| Rasmus Ibsen-Jensen | 2 | 69 | 12.65 |
| Peter Bro Miltersen | 3 | 1146 | 94.49 |