Minimum-Cost Reachability for Priced Timed Automata
Gerd Behrmann
January 2001 |

## Abstract:
This paper introduces the model of linearly priced timed
automata as an extension of timed automata, with prices on both transitions
and locations. For this model we consider the minimum-cost reachability
problem: i.e. given a linearly priced timed automaton and a target state,
determine the minimum cost of executions from the initial state to the target
state. This problem generalizes the minimum-time reachability problem for
ordinary timed automata. We prove decidability of this problem by offering an
algorithmic solution, which is based on a combination of branch-and-bound
techniques and a new notion of priced regions. The latter allows symbolic
representation and manipulation of reachable states together with the cost of
reaching them
Available as |

Last modified: 2003-06-08 by webmaster.