Discount-Optimal Infinite Runs in Priced Timed Automata

Uli Fahrenberg; Kim Guldstrand Larsen

doi:10.1016/j.entcs.2009.05.039

Discount-Optimal Infinite Runs in Priced Timed Automata

Uli Fahrenberg, Kim Guldstrand Larsen

Research output: Contribution to journal › Conference article in Journal › Research › peer-review

14 Citations (Scopus)

Abstract

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.

Original language	English
Journal	Electronic Notes in Theoretical Computer Science
Volume	239
Pages (from-to)	179-191
ISSN	1571-0661
DOIs	https://doi.org/10.1016/j.entcs.2009.05.039
Publication status	Published - 2009
Event	The 8th, 9th, and 10th International Workshops on Verification of Infinite-State Systems (INFINITY 2006, 2007, 2008)-- INFINITY 08 - Toronto, Canada Duration: 23 Aug 2008 → 23 Aug 2008 Conference number: 8-9-10

Conference

Conference	The 8th, 9th, and 10th International Workshops on Verification of Infinite-State Systems (INFINITY 2006, 2007, 2008)-- INFINITY 08
Number	8-9-10
Country/Territory	Canada
City	Toronto
Period	23/08/2008 → 23/08/2008

Access to Document

10.1016/j.entcs.2009.05.039

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

@inproceedings{2c14ec0423064bd08fd0186e960db7c4,

title = "Discount-Optimal Infinite Runs in Priced Timed Automata",

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

author = "Uli Fahrenberg and Larsen, {Kim Guldstrand}",

year = "2009",

doi = "10.1016/j.entcs.2009.05.039",

language = "English",

volume = "239",

pages = "179--191",

journal = "Electronic Notes in Theoretical Computer Science",

issn = "1571-0661",

publisher = "Elsevier",

note = "The 8th, 9th, and 10th International Workshops on Verification of Infinite-State Systems (INFINITY 2006, 2007, 2008)-- INFINITY 08 ; Conference date: 23-08-2008 Through 23-08-2008",

}

TY - GEN

T1 - Discount-Optimal Infinite Runs in Priced Timed Automata

AU - Fahrenberg, Uli

AU - Larsen, Kim Guldstrand

N1 - Conference code: 8-9-10

PY - 2009

Y1 - 2009

N2 - 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.

AB - 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.

U2 - 10.1016/j.entcs.2009.05.039

DO - 10.1016/j.entcs.2009.05.039

M3 - Conference article in Journal

SN - 1571-0661

VL - 239

SP - 179

EP - 191

JO - Electronic Notes in Theoretical Computer Science

JF - Electronic Notes in Theoretical Computer Science

T2 - The 8th, 9th, and 10th International Workshops on Verification of Infinite-State Systems (INFINITY 2006, 2007, 2008)-- INFINITY 08

Y2 - 23 August 2008 through 23 August 2008

ER -

Discount-Optimal Infinite Runs in Priced Timed Automata

Abstract

Conference

Access to Document

AUB Link

Fingerprint

Cite this