Hansen, Thomas Dueholm2; Ibsen-Jensen, Rasmus2; Miltersen, Peter Bro2
Pedro R. D*Argenio, Hernán Melgratti
1 Department of Computer Science, Science and Technology, Aarhus University2 Department of Computer Science, Science and Technology, Aarhus University
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.
Lecture Notes in Computer Science: 24th International Conference, Concur 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings, 2013, p. 531-545
Main Research Area:
Lecture Notes in Computer Science
International Conference on Currency TheoryInternational Conference on Concurrency Theory, 2013