Staying alive as cheaply as possible

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

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

    44 Citations (Scopus)


    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
    Number of pages16
    ISBN (Print)3-540-21259-0
    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

    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349


    Workshop7th International Workshop on Hybrid Systems: Computation and Control, HSCC 2004
    Abbreviated titleHSCC
    CountryUnited States


    • METIS-221490

    Cite this