Timed pushdown automata and branching vector addition systems
Lorenzo Clemente, Sławomir Lasota, Ranko Lazić, Filip Mazowiecki · 2017
We prove that non-emptiness of timed register pushdown automata is decidable in doubly exponential time. This is a very expressive class of automata, whose transitions may involve state and top-of-stack clocks with unbounded differences. It strictly subsumes pushdown timed automata of Bouajjani et al., dense-timed pushdown automata of Abdulla et al., and orbit-finite timed register pushdown automata of Clemente and Lasota. Along the way, we prove two further decidability results of independent interest: for non-emptiness of least solutions to systems of equations over sets of integers with addition, union and intersections with ℕ and -ℕ, and for reachability in one-dimensional branching vector addition systems with states and subtraction, both in exponential time.