Staying alive as cheaply as possible

Patricia Bouyer; Ed Brinksma; Kim G. Larsen

doi:10.1007/978-3-540-24743-2_14

Staying alive as cheaply as possible

Patricia Bouyer
, Ed Brinksma
, Kim G. Larsen

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

56 Citations (Scopus)

13 Downloads (Pure)

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 language	English
Title of host publication	Hybrid Systems: Computation and Control
Subtitle of host publication	7th International Workshop, HSCC 2004, Philadelphia, PA, USA, March 25-27, 2004, Proceedings
Editors	Rajeev Alur, George J. Pappas
Place of Publication	Berlin, Heidelberg
Publisher	Springer
Pages	203-218
Number of pages	16
ISBN (Electronic)	978-3-540-24743-2
ISBN (Print)	978-3-540-21259-1
DOIs	https://doi.org/10.1007/978-3-540-24743-2_14
Publication status	Published - 25 Mar 2004
Event	7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004 - Philadelphia, United States Duration: 25 Mar 2004 → 27 Mar 2004 Conference number: 7

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	2993
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Workshop

Workshop	7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004
Abbreviated title	HSCC
Country/Territory	United States
City	Philadelphia
Period	25/03/04 → 27/03/04

Keywords

n/a OA procedure

Access to Document

10.1007/978-3-540-24743-2_14

Cite this

Bouyer, P., Brinksma, E., & Larsen, K. G. (2004). Staying alive as cheaply as possible. In R. Alur, & G. J. Pappas (Eds.), Hybrid Systems: Computation and Control: 7th International Workshop, HSCC 2004, Philadelphia, PA, USA, March 25-27, 2004, Proceedings (pp. 203-218). (Lecture Notes in Computer Science; Vol. 2993). Springer. https://doi.org/10.1007/978-3-540-24743-2_14

@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 = "n/a OA procedure",

author = "Patricia Bouyer and Ed Brinksma and Larsen, \{Kim G.\}",

year = "2004",

month = mar,

day = "25",

doi = "10.1007/978-3-540-24743-2\_14",

language = "English",

isbn = "978-3-540-21259-1",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "203--218",

editor = "Rajeev Alur and Pappas, \{George J.\}",

booktitle = "Hybrid Systems: Computation and Control",

address = "Germany",

note = "7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004, HSCC ; Conference date: 25-03-2004 Through 27-03-2004",

}

Bouyer, P, Brinksma, E & Larsen, KG 2004, Staying alive as cheaply as possible. in R Alur & GJ Pappas (eds), Hybrid Systems: Computation and Control: 7th International Workshop, HSCC 2004, Philadelphia, PA, USA, March 25-27, 2004, Proceedings. Lecture Notes in Computer Science, vol. 2993, Springer, Berlin, Heidelberg, pp. 203-218, 7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004, Philadelphia, Pennsylvania, United States, 25/03/04. https://doi.org/10.1007/978-3-540-24743-2_14

Staying alive as cheaply as possible. / Bouyer, Patricia; Brinksma, Ed; Larsen, Kim G.
Hybrid Systems: Computation and Control: 7th International Workshop, HSCC 2004, Philadelphia, PA, USA, March 25-27, 2004, Proceedings. ed. / Rajeev Alur; George J. Pappas. Berlin, Heidelberg: Springer, 2004. p. 203-218 (Lecture Notes in Computer Science; Vol. 2993).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Staying alive as cheaply as possible

AU - Bouyer, Patricia

AU - Brinksma, Ed

AU - Larsen, Kim G.

N1 - Conference code: 7

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 - n/a OA procedure

U2 - 10.1007/978-3-540-24743-2_14

DO - 10.1007/978-3-540-24743-2_14

M3 - Conference contribution

SN - 978-3-540-21259-1

T3 - Lecture Notes in Computer Science

SP - 203

EP - 218

BT - Hybrid Systems: Computation and Control

A2 - Alur, Rajeev

A2 - Pappas, George J.

PB - Springer

CY - Berlin, Heidelberg

T2 - 7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004

Y2 - 25 March 2004 through 27 March 2004

ER -

Staying alive as cheaply as possible

Abstract

Publication series

Workshop

Keywords

Access to Document

Fingerprint

Cite this