Staying alive as cheaply as possible

P. Bouyer, Hendrik Brinksma, K.G. Larsen

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

43 Citations (Scopus)

Abstract

This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules.
Original languageUndefined
Title of host publicationHybrid systems: computation and control
EditorsR Alur, G.J. Pappas
Place of PublicationBerlin
PublisherSpringer
Pages203-218
Number of pages16
ISBN (Print)3-540-21259-0
DOIs
Publication statusPublished - 25 Mar 2004
Event7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004 - Philadelphia, United States
Duration: 25 Mar 200427 Mar 2004
Conference number: 7

Publication series

Name
NumberXII
Volume2993
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004
Abbreviated titleHSCC
CountryUnited States
CityPhiladelphia
Period25/03/0427/03/04

Keywords

  • METIS-221490

Cite this

Bouyer, P., Brinksma, H., & Larsen, K. G. (2004). Staying alive as cheaply as possible. In R. Alur, & G. J. Pappas (Eds.), Hybrid systems: computation and control (pp. 203-218). Berlin: Springer. https://doi.org/10.1007/b96398
Bouyer, P. ; Brinksma, Hendrik ; Larsen, K.G. / Staying alive as cheaply as possible. Hybrid systems: computation and control. editor / R Alur ; G.J. Pappas. Berlin : Springer, 2004. pp. 203-218
@inproceedings{30690633723b4d2bbe8722768b0e8290,
title = "Staying alive as cheaply as possible",
abstract = "This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules.",
keywords = "METIS-221490",
author = "P. Bouyer and Hendrik Brinksma and K.G. Larsen",
note = "DOI: 10.1007/b96398",
year = "2004",
month = "3",
day = "25",
doi = "10.1007/b96398",
language = "Undefined",
isbn = "3-540-21259-0",
publisher = "Springer",
number = "XII",
pages = "203--218",
editor = "R Alur and G.J. Pappas",
booktitle = "Hybrid systems: computation and control",

}

Bouyer, P, Brinksma, H & Larsen, KG 2004, Staying alive as cheaply as possible. in R Alur & GJ Pappas (eds), Hybrid systems: computation and control. Springer, Berlin, pp. 203-218, 7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004, Philadelphia, United States, 25/03/04. https://doi.org/10.1007/b96398

Staying alive as cheaply as possible. / Bouyer, P.; Brinksma, Hendrik; Larsen, K.G.

Hybrid systems: computation and control. ed. / R Alur; G.J. Pappas. Berlin : Springer, 2004. p. 203-218.

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

TY - GEN

T1 - Staying alive as cheaply as possible

AU - Bouyer, P.

AU - Brinksma, Hendrik

AU - Larsen, K.G.

N1 - DOI: 10.1007/b96398

PY - 2004/3/25

Y1 - 2004/3/25

N2 - This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules.

AB - This paper is concerned with the derivation of infinite schedules for timed automata that are in some sense optimal. To cover a wide class of optimality criteria we start out by introducing an extension of the (priced) timed automata model that includes both costs and rewards as separate modelling features. A precise definition is then given of what constitutes optimal infinite behaviours for this class of models. We subsequently show that the derivation of optimal non-terminating schedules for such double-priced timed automata is computable. This is done by a reduction of the problem to the determination of optimal mean-cycles in finite graphs with weighted edges. This reduction is obtained by introducing the so-called corner-point abstraction, a powerful abstraction technique of which we show that it preserves optimal schedules.

KW - METIS-221490

U2 - 10.1007/b96398

DO - 10.1007/b96398

M3 - Conference contribution

SN - 3-540-21259-0

SP - 203

EP - 218

BT - Hybrid systems: computation and control

A2 - Alur, R

A2 - Pappas, G.J.

PB - Springer

CY - Berlin

ER -

Bouyer P, Brinksma H, Larsen KG. Staying alive as cheaply as possible. In Alur R, Pappas GJ, editors, Hybrid systems: computation and control. Berlin: Springer. 2004. p. 203-218 https://doi.org/10.1007/b96398