Reachability-time games on timed automata - (Extended abstract)
Jurdzinski, Marcin and Trivedi, Ashutosh (2007) Reachability-time games on timed automata - (Extended abstract). In: 34th International Colloquium on Automata, Languages and Programming, Wroclaw, POLAND, JUL 09-13, 2007. Published in: Automata, Languages and Programming, Proceedings, 4596 pp. 838-849.Full text not available from this repository.
In a reachability-time game, players Min and Max choose moves so that the time to reach a final state in a timed automaton is minimised or maximised, respectively. Asarin and Maler showed decidability of reachability-time games on strongly non-Zeno timed automata using a value iteration algorithm. This paper complements their work by providing a strategy improvement algorithm for the problem. It also generalizes their decidability result because the proposed strategy improvement algorithm solves reachability-time games on all timed automata. The exact computational complexity of solving reachability-time games is also established: the problem is EXPTIME-complete for timed automata with at least two clocks.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Series Name:||LECTURE NOTES IN COMPUTER SCIENCE|
|Journal or Publication Title:||Automata, Languages and Programming, Proceedings|
|Editor:||Arge, L and Cachin, C and Jurdzinski, T and Tarlecki, A|
|Number of Pages:||12|
|Page Range:||pp. 838-849|
|Title of Event:||34th International Colloquium on Automata, Languages and Programming|
|Location of Event:||Wroclaw, POLAND|
|Date(s) of Event:||JUL 09-13, 2007|
Actions (login required)