### Abstract

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

### Cite this

*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

}

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

**Minimum-Cost Reachability for Priced Timed Automata.** / Behrmann, Gerd; Fehnker, Ansgar; Hune, Thomas; Larsen, Kim Guldstrand; Pettersson, Paul; Romijn, Judi; Vaandrager, Frits W.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Minimum-Cost Reachability for Priced Timed Automata

AU - Behrmann, Gerd

AU - Fehnker, Ansgar

AU - Hune, Thomas

AU - Larsen, Kim Guldstrand

AU - Pettersson, Paul

AU - Romijn, Judi

AU - Vaandrager, Frits W.

PY - 2001

Y1 - 2001

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

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

U2 - 10.1007/3-540-45351-2_15

DO - 10.1007/3-540-45351-2_15

M3 - Conference contribution

SN - 978-3-540-41866-5

T3 - Lecture Notes in Computer Science

SP - 147

EP - 161

BT - Hybrid Systems: Computation and Control

A2 - Benedetto, Maria Domenica Di

A2 - Sangiovanni-Vincentelli, Alberto L.

PB - Springer

ER -