A Faster Algorithm for Solving One-Clock Priced Timed Games

Thomas Dueholm Hansen; Rasmus Ibsen-Jensen; Peter Bro Miltersen

doi:10.1007/978-3-642-40184-8_37

A Faster Algorithm for Solving One-Clock Priced Timed Games

Thomas Dueholm Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen

Institut for Datalogi

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

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 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.

Originalsprog	Engelsk
Titel	CONCUR 2013 – Concurrency Theory : 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings
Redaktører	Pedro R. D*Argenio, Hernán Melgratti
Antal sider	15
Forlag	Springer VS
Publikationsdato	2013
Sider	531-545
ISBN (Trykt)	978-3-642-40183-1
ISBN (Elektronisk)	978-3-642-40184-8
DOI	https://doi.org/10.1007/978-3-642-40184-8_37
Status	Udgivet - 2013
Begivenhed	International Conference on Currency Theory - Buenos Aires, Argentina Varighed: 27 aug. 2013 → 30 aug. 2013 Konferencens nummer: 24

Konference

Konference	International Conference on Currency Theory
Nummer	24
Land/Område	Argentina
By	Buenos Aires
Periode	27/08/2013 → 30/08/2013

Navn	Lecture Notes in Computer Science
Vol/bind	8052
ISSN	0302-9743

Adgang til dokumentet

10.1007/978-3-642-40184-8_37

http://link.springer.com/chapter/10.1007%2F978-3-642-40184-8_37

Citationsformater

Hansen, T. D., Ibsen-Jensen, R., & Miltersen, P. B. (2013). A Faster Algorithm for Solving One-Clock Priced Timed Games. I P. R. D*Argenio, & H. Melgratti (red.), CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings (s. 531-545). Springer VS. https://doi.org/10.1007/978-3-642-40184-8_37

Hansen, Thomas Dueholm ; Ibsen-Jensen, Rasmus ; Miltersen, Peter Bro. / A Faster Algorithm for Solving One-Clock Priced Timed Games. CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. red. / Pedro R. D*Argenio ; Hernán Melgratti. Springer VS, 2013. s. 531-545 (Lecture Notes in Computer Science, Bind 8052).

@inproceedings{ab83b7f5599d4d9da15fb3f69da27f0e,

title = "A Faster Algorithm for Solving One-Clock Priced Timed Games",

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 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.",

author = "Hansen, {Thomas Dueholm} and Rasmus Ibsen-Jensen and Miltersen, {Peter Bro}",

year = "2013",

doi = "10.1007/978-3-642-40184-8_37",

language = "English",

isbn = "978-3-642-40183-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer VS",

pages = "531--545",

editor = "D*Argenio, {Pedro R.} and Hern{\'a}n Melgratti",

booktitle = "CONCUR 2013 – Concurrency Theory",

note = "International Conference on Currency Theory ; Conference date: 27-08-2013 Through 30-08-2013",

}

Hansen, TD, Ibsen-Jensen, R & Miltersen, PB 2013, A Faster Algorithm for Solving One-Clock Priced Timed Games. i PR D*Argenio & H Melgratti (red), CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. Springer VS, Lecture Notes in Computer Science, bind 8052, s. 531-545, International Conference on Currency Theory, Buenos Aires, Argentina, 27/08/2013. https://doi.org/10.1007/978-3-642-40184-8_37

A Faster Algorithm for Solving One-Clock Priced Timed Games. / Hansen, Thomas Dueholm; Ibsen-Jensen, Rasmus; Miltersen, Peter Bro.
CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. red. / Pedro R. D*Argenio; Hernán Melgratti. Springer VS, 2013. s. 531-545 (Lecture Notes in Computer Science, Bind 8052).

Publikation: Bidrag til bog/antologi/rapport/proceeding › Konferencebidrag i proceedings › Forskning › peer review

TY - GEN

T1 - A Faster Algorithm for Solving One-Clock Priced Timed Games

AU - Hansen, Thomas Dueholm

AU - Ibsen-Jensen, Rasmus

AU - Miltersen, Peter Bro

N1 - Conference code: 24

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-642-40184-8_37

DO - 10.1007/978-3-642-40184-8_37

M3 - Article in proceedings

SN - 978-3-642-40183-1

T3 - Lecture Notes in Computer Science

SP - 531

EP - 545

BT - CONCUR 2013 – Concurrency Theory

A2 - DArgenio, Pedro R.

A2 - Melgratti, Hernán

PB - Springer VS

T2 - International Conference on Currency Theory

Y2 - 27 August 2013 through 30 August 2013

ER -

Hansen TD, Ibsen-Jensen R, Miltersen PB. A Faster Algorithm for Solving One-Clock Priced Timed Games. I D*Argenio PR, Melgratti H, red., CONCUR 2013 – Concurrency Theory: 24th International Conference, CONCUR 2013, Buenos Aires, Argentina, August 27-30, 2013. Proceedings. Springer VS. 2013. s. 531-545. (Lecture Notes in Computer Science, Bind 8052). doi: 10.1007/978-3-642-40184-8_37