@inproceedings{6a16c50b1b6d4959b46f423ad402c004,

title = "Minimum-cost reachability for priced timed automata",

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.",

keywords = "Timed Automata, Verification, Data Structures, Algorithms, Optimization",

author = "Gerd Behrmann and Ansgar Fehnker and Thomas Hune and Kim Larsen and Paul Pettersson and Judi Romijn and Frits Vaandrager",

year = "2001",

doi = "10.1007/3-540-45351-2_15",

language = "English",

isbn = "3540418660",

series = "Lecture Notes in Computer Science",

publisher = "Springer, Springer Nature",

pages = "147--161",

editor = "{Di Benedetto}, {Maria Domenica} and Alberto Sangiovanni-Vincentelli",

booktitle = "Hybrid Systems: Computation and Control",

address = "United States",

note = "4th Workshop on Hybrid Systems: Computation and Control, HSCC 2001 ; Conference date: 28-03-2001 Through 30-03-2001",

}