### 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.

Original language | English |
---|---|

Title of host publication | Hybrid Systems: Computation and Control |

Subtitle of host publication | 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings |

Editors | Maria Domenica Di Benedetto, Alberto L. Sangiovanni-Vincentelli |

Publisher | Springer |

Pages | 147-161 |

Number of pages | 15 |

ISBN (Electronic) | 978-3-540-45351-2 |

ISBN (Print) | 978-3-540-41866-5 |

DOIs | |

Publication status | Published - 2001 |

Event | 4th International Workshop on Hybrid Systems: Computation and Control 2001 - Rome, Italy Duration: 28 Mar 2001 → 30 Mar 2001 Conference number: 4 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 2034 |

### Conference

Conference | 4th International Workshop on Hybrid Systems: Computation and Control 2001 |
---|---|

Abbreviated title | HSCC 2001 |

Country | Italy |

City | Rome |

Period | 28/03/01 → 30/03/01 |

## Fingerprint Dive into the research topics of 'Minimum-Cost Reachability for Priced Timed Automata'. Together they form a unique fingerprint.

## Cite this

Behrmann, G., Fehnker, A., Hune, T., Larsen, K. G., Pettersson, P., Romijn, J., & Vaandrager, F. W. (2001). Minimum-Cost Reachability for Priced Timed Automata. In M. D. D. Benedetto, & A. L. Sangiovanni-Vincentelli (Eds.),

*Hybrid Systems: Computation and Control: 4th International Workshop, HSCC 2001 Rome, Italy, March 28–30, 2001 Proceedings*(pp. 147-161). (Lecture Notes in Computer Science; Vol. 2034). Springer. https://doi.org/10.1007/3-540-45351-2_15