Computing Optimal Reachability Costs in Priced Dense-Timed Pushdown Automata

Abstract. We study priced dense-timed pushdown automata that are a generalization of the classic model of pushdown automata, in the sense that they operate on real-valued clocks, and that the stack symbols have real-valued ages. Furthermore, the model allows a cost function that assigns transition costs to transitions and storage costs to stack symbols. We show that the optimal cost, i.e., the infimum of the costs of the set of runs reaching a given control state, is computable.