zbMATH — the first resource for mathematics

Combining symbolic representations for solving timed games. (English) Zbl 1290.68072
Chatterjee, Krishnendu (ed.) et al., Formal modeling and analysis of timed systems. 8th international conference, FORMATS 2010, Klosterneuburg, Austria, September 8–10, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15296-2/pbk). Lecture Notes in Computer Science 6246, 107-121 (2010).
Summary: We present a general approach to combine symbolic state space representations for the discrete and continuous parts in the synthesis of winning strategies for timed reachability games. The combination is based on abstraction refinement where discrete symbolic techniques are used to produce a sequence of abstract timed game automata. After each refinement step, the resulting abstraction is used for computing an under- and an over-approximation of the timed winning states. The key idea is to identify large relevant and irrelevant parts of the precise weakest winning strategy already on coarse, and therefore simple, abstractions. If neither the existence nor nonexistence of a winning strategy can be established in the approximations, we use them to guide the refinement process. Based on a prototype that combines binary decision diagrams and difference bound matrices, we experimentally evaluate the technique on standard benchmarks from timed controller synthesis. The results clearly demonstrate the potential of the new approach concerning running time and memory consumption compared to the classical on-the-fly algorithm implemented in Uppaal-Tiga.
For the entire collection see [Zbl 1195.68001].
Reviewer: Reviewer (Berlin)
68Q45 Formal languages and automata
91A05 2-person games
91A80 Applications of game theory
Full Text: DOI