Zone-Based Reachability Analysis of Dense-Timed Pushdown Automata
Kristiina Ausmees · KTH Publication Database DiVA (KTH Royal Institute of Technology) · 2012
Proving that programs behave correctly is a matter of both great theoretical interest as well as practical use. One way to do this is by analyzing a model of the system in question in order to determine if it meets a given specification. Real-time recursive systems can be modeled by dense-timed pushdown automata, a model which combines the behaviours of classical timed automata and pushdown automata. The problem of reachability has been proven to be decidable for this model. The algorithm that solves this problem relies on constructing a classical pushdown automaton that mimics the behaviour of a given timed pushdown automaton by means of an abstraction that uses regions as a symbolic representation of states. The drawback of this approach is that the untimed automaton produced generally contains a very large number of states. This report proposes a method of generalizing this abstraction by using zones instead of regions, in order to minimize the number of states in the untimed automaton.