As cheap as possible : efficient cost-optimal reachability for priced timed automata

K.G. Larsen, G. Behrmann, E. Brinksma, A. Fehnker, T. Hune, P. Pettersson, J.M.T. Romijn

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

    113 Citations (Scopus)
    1 Downloads (Pure)


    In this paper we present an algorithm for efficiently computing optimal cost of reaching a goal state in the model of Linearly Priced Timed Automata (LPTA). The central contribution of this paper is a priced extension of so-called zones. This, together with a notion of facets of a zone, allows the entire machinery for symbolic reachability for timed automata in terms of zones to be lifted to cost-optimal reachability using priced zones. We report on experiments with a cost-optimizing extension of Uppaal on a number of examples.
    Original languageEnglish
    Title of host publicationComputer aided verification : proceedings 13th international conference, CAV 2001, Paris, july 18-22, 2001
    EditorsG. Berry, H. Comon, A. Finkel
    ISBN (Print)3-540-42345-1
    Publication statusPublished - 2001

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'As cheap as possible : efficient cost-optimal reachability for priced timed automata'. Together they form a unique fingerprint.

    Cite this