Staying Alive as Cheaply as Possible

Patricia Bouyer, Ed Brinksma, Kim Guldstrand Larsen

Research output: Contribution to journalJournal articleResearch

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 nonterminating 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 languageEnglish
JournalSpecial issue of Formal Methods in System Design from HSCC 2004
Volume2993
Publication statusPublished - 2005

Fingerprint

Dive into the research topics of 'Staying Alive as Cheaply as Possible'. Together they form a unique fingerprint.

Cite this