Name
Abstract | ||
|---|---|---|
We study the cost-optimal reachability problem for weighted timed automata such that positive and negative costs are allowed on edges and locations. By optimality, we mean an infimum cost as well as a supremum cost. We show that this problem is PSpace-Complete. Our proof uses techniques of linear programming, and thus exploits an important property of optimal runs: their time-transitions use a time τ which is arbitrarily close to an integer. We then propose an extension of the region graph, the weighted discrete graph, whose structure gives light on the way to solve the cost-optimal reachability problem. We also give an application of the cost-optimal reachability problem in the context of timed games. |
Year | DOI | Venue |
|---|---|---|
2007 | https://doi.org/10.1007/s10703-007-0035-4 | Formal Methods in System Design |
Keywords | Field | DocType |
Weighted timed automaton,Cost-optimal reachability problem | Computer science,Automaton,Infimum and supremum,Theoretical computer science,Reachability problem | Journal |
Volume | Issue | ISSN |
31 | 2 | 0925-9856 |
Citations | PageRank | References |
40 | 1.37 | 18 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Patricia Bouyer | 1 | 435 | 29.20 |
| Thomas Brihaye | 2 | 460 | 35.91 |
| Véronique Bruyère | 3 | 429 | 43.59 |
| Jean-François Raskin | 4 | 1735 | 100.15 |