Reachability-Time Games on Timed Automata
From MaRDI portal
Abstract: 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.
Recommendations
Cited in
(44)- On subgame perfect equilibria in turn-based reachability timed games
- A game approach to determinize timed automata
- A turn-based approach for qualitative time concurrent games
- Expected reachability-time games
- A faster algorithm for solving one-clock priced timed games
- Optimal reachability in divergent weighted timed games
- Average-time games
- On time with minimal expected cost!
- Efficient On-the-Fly Algorithms for Partially Observable Timed Games
- Concavely-Priced Timed Automata
- Average-Price and Reachability-Price Games on Hybrid Automata with Strong Resets
- Stochastic Real-Time Games with Qualitative Timed Automata Objectives
- Computing equilibria in two-player timed games via turn-based finite games
- Combining symbolic representations for solving timed games
- Expected reachability-time games
- Reachability in Stochastic Timed Games
- Automata-theoretic decision of timed games
- Synthesis of memory-efficient, clock-memory free, and non-Zeno safety controllers for timed systems
- A survey of timed automata for the development of real-time systems
- Stochastic timed games revisited
- scientific article; zbMATH DE number 6862072 (Why is no real title available?)
- scientific article; zbMATH DE number 2086509 (Why is no real title available?)
- Robust reachability in timed automata and games: a game-based approach
- Two-player reachability-price games on single-clock timed automata
- Improved undecidability results for reachability games on recursive timed automata
- Symbolic Approximation of Weighted Timed Games
- Determinisability of register and timed automata
- A menagerie of timed automata
- Admissible strategies in timed games
- Minimum-Time Reachability in Timed Games
- On Reachability Games of Ordinal Length
- Timed Basic Parallel Processes
- Timed Parity Games: Complexity and Robustness
- CONCUR 2005 – Concurrency Theory
- Formal Modeling and Analysis of Timed Systems
- Timed Parity Games: Complexity and Robustness
- Optimal controller synthesis for timed systems
- Parity games on temporal graphs
- Timed games and deterministic separability
- Playing stochastically in weighted timed games to emulate memory
- Decidability of one-clock weighted timed games with arbitrary weights
- Synthesis of robust optimal real-time systems
- Playing stochastically in weighted timed games to emulate memory
- Temporal explorability games
This page was built for publication: Reachability-Time Games on Timed Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5428863)
