Better abstractions for timed automata

Abstract

We consider the reachability problem for timed automata. A standard solution to this problem involves computing a search tree whose nodes are abstractions of zones. These abstractions preserve underlying simulation relations on the state space of the automaton. For both effectiveness and efficiency reasons, they are parametrized by the maximal lower and upper bounds (LU-bounds) occurring in the guards of the automaton. We consider the aLU abstraction defined by Behrmann et al. Since this abstraction can potentially yield non-convex sets, it has not been used in implementations. We prove that aLU abstraction is the biggest abstraction with respect to LU-bounds that is sound and complete for reachability. We also provide an efficient technique to use the aLU abstraction to solve the reachability problem.

Extended version of LICS 2012 paper (conference paper till v6). in Information and Computation, available online 27 July 2016

References in corpus (2)

• Using non-convex approximations for efficient analysis of timed automata
• Symbolic Optimal Reachability in Weighted Timed Automata

Cited by in corpus (6)

• Zone-based verification of timed automata: extrapolations, simulations and what next?
• Zone extrapolations in parametric timed automata
• Reachability relations of timed pushdown automata
• Efficient Convex Zone Merging in Parametric Timed Automata
• Determinisability of register and timed automata
• Automated synthesis of local time requirement for service composition