Discount-Optimal Infinite Runs in Priced Timed Automata

Uli Fahrenberg, Kim Guldstrand Larsen

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

13 Citationer (Scopus)

Abstrakt

We introduce a new discounting semantics for priced timed automata. Discounting provides a way to model optimal-cost problems for infinite traces and has applications in optimal scheduling and other areas. In the discounting semantics, prices decrease exponentially, so that the contribution of a certain part of the behaviour to the overall cost depends on how far into the future this part takes place. We consider the optimal infinite run problem under this semantics: Given a priced timed automaton, find an infinite path with minimal discounted price. We show that this problem is computable, by a reduction to a similar problem on finite weighted graphs. The proof relies on a new theorem on minimization of monotonous functions defined on infinite-dimensional zones, which is of interest in itself.
OriginalsprogEngelsk
TidsskriftElectronic Notes in Theoretical Computer Science
Vol/bind239
Sider (fra-til)179-191
ISSN1571-0661
DOI
StatusUdgivet - 2009
BegivenhedThe 8th, 9th, and 10th International Workshops on Verification of Infinite-State Systems (INFINITY 2006, 2007, 2008)-- INFINITY 08 - Toronto, Canada
Varighed: 23 aug. 200823 aug. 2008
Konferencens nummer: 8-9-10

Konference

KonferenceThe 8th, 9th, and 10th International Workshops on Verification of Infinite-State Systems (INFINITY 2006, 2007, 2008)-- INFINITY 08
Nummer8-9-10
LandCanada
ByToronto
Periode23/08/200823/08/2008

Fingeraftryk Dyk ned i forskningsemnerne om 'Discount-Optimal Infinite Runs in Priced Timed Automata'. Sammen danner de et unikt fingeraftryk.

Citationsformater