Abstract
We address the problem of finding an infinite run with the
optimal cost-time ratio in a one-clock priced timed automaton and pro-
vide an algorithmic solution. Through refinements of the quotient graph
obtained by strong time-abstracting bisimulation partitioning, we con-
struct a graph with time and costs as weights and prove that the min-
imum ratio properties remain unaltered, allowing algorithms for finite
weighted graphs to be applied. The resulting algorithm has an overall
time complexity of O((|Q| · (|T | + |Q|))6 ), |Q| being the number of lo-
cations and |T | the number of transitions of the one-clock priced timed
automaton.
optimal cost-time ratio in a one-clock priced timed automaton and pro-
vide an algorithmic solution. Through refinements of the quotient graph
obtained by strong time-abstracting bisimulation partitioning, we con-
struct a graph with time and costs as weights and prove that the min-
imum ratio properties remain unaltered, allowing algorithms for finite
weighted graphs to be applied. The resulting algorithm has an overall
time complexity of O((|Q| · (|T | + |Q|))6 ), |Q| being the number of lo-
cations and |T | the number of transitions of the one-clock priced timed
automaton.
Originalsprog | Engelsk |
---|---|
Publikationsdato | 2011 |
Antal sider | 9 |
Status | Udgivet - 2011 |
Begivenhed | Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science - Lednice, Tjekkiet Varighed: 14 okt. 2011 → 16 okt. 2011 |
Konference
Konference | Annual Doctoral Workshop on Mathematical and Engineering Methods in Computer Science |
---|---|
Land/Område | Tjekkiet |
By | Lednice |
Periode | 14/10/2011 → 16/10/2011 |