As Cheap as Possible:Efficient Cost-Optimal Reachability for Priced Timed Automata

K.G. Larsen, Gerd Behrmann, Ed Brinksma, Ansgar Fehnker, Thomas Hune, Paul Petterson, J.M.T. Romijn, Judi Romijn

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademicpeer-review

    92 Citations (Scopus)
    36 Downloads (Pure)

    Abstract

    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
    Subtitle of host publication13th International Conference, CAV 2001 Paris, France, July 18–22, 2001 Proceedings
    EditorsGérard Berry, Hubert Comon, Alain Finkel
    Place of PublicationHeidelberg
    PublisherSpringer
    Pages493-505
    Number of pages13
    Volume2102
    ISBN (Electronic)978-3-540-44585-2
    ISBN (Print)978-3-540-42345-4
    DOIs
    Publication statusPublished - 2001
    Event13th International Conference on Computer Aided Verification, CAV 2001 - Paris, France
    Duration: 18 Jul 200122 Jul 2001
    Conference number: 13

    Publication series

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

    Workshop

    Workshop13th International Conference on Computer Aided Verification, CAV 2001
    Abbreviated titleCAV
    CountryFrance
    CityParis
    Period18/07/0122/07/01

    Keywords

    • METIS-205778
    • EWI-6457
    • FMT-MC: MODEL CHECKING
    • FMT-TOOLS
    • FMT-RT: VERIFICATION OF REAL-TIME SYSTEMS
    • IR-63285
    • FMT-SEMANTICS

    Fingerprint 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

    Larsen, K. G., Behrmann, G., Brinksma, E., Fehnker, A., Hune, T., Petterson, P., ... Romijn, J. (2001). As Cheap as Possible:Efficient Cost-Optimal Reachability for Priced Timed Automata. In G. Berry, H. Comon, & A. Finkel (Eds.), Computer Aided Verification: 13th International Conference, CAV 2001 Paris, France, July 18–22, 2001 Proceedings (Vol. 2102, pp. 493-505). (Lecture Notes in Computer Science; No. 2102). Heidelberg: Springer. https://doi.org/10.1007/3-540-44585-4_47