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 |
Place of Publication | Berlin, Heidelberg |
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 |
Externally published | Yes |
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 |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference
Conference | 4th International Workshop on Hybrid Systems: Computation and Control 2001 |
---|---|
Abbreviated title | HSCC 2001 |
Country/Territory | Italy |
City | Rome |
Period | 28/03/01 → 30/03/01 |
Keywords
- n/a OA procedure