Multi-core emptiness checking of timed Büchi automata using inclusion abstraction

Alfons Laarman, Mads Chr. Olesen, Andreas Engelbredt Dalsgaard, Kim Gulstrand Larsen, Jaco van de Pol

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

    25 Citations (Scopus)
    15 Downloads (Pure)

    Abstract

    This paper contributes to the multi-core model checking of timed automata (TA) with respect to liveness properties, by investigating checking of TA Büchi emptiness under the very coarse inclusion abstraction or zone subsumption, an open problem in this field. We show that in general Büchi emptiness is not preserved under this abstraction. However, we prove that some other structural properties are preserved. Solving the problem partly, we propose a variation of the classic nested depth-first search (NDFS) algorithm that takes advantage of these properties thereby exploiting inclusion abstraction. In addition, we extend the multi-core CNDFS algorithm with subsumption, providing the first parallel LTL model checking algorithm for timed automata. We prove both algorithms correct and show that other, more aggressive variations are incorrect. The algorithms are implemented in LTSmin, and experimental evaluations show the effectiveness and scalability of both contributions: subsumption halves the number of states in the real-world FDDI and CSMA case studies, and the multi-core algorithm yields speedups of up to 40 on a 48 cores.
    Original languageEnglish
    Title of host publicationComputer Aided Verification
    Subtitle of host publication25th International Conference, CAV 2013, Saint Petersburg, Russia, July 13-19, 2013. Proceedings
    EditorsNatasha Sharygina, Helmut Veith
    Place of PublicationBerlin, Heidelberg
    PublisherSpringer
    Pages968-983
    Number of pages18
    ISBN (Electronic)978-3-642-39799-8
    ISBN (Print)978-3-642-39798-1
    DOIs
    Publication statusPublished - 13 Jul 2013
    Event25th International Conference on Computer Aided Verification, CAV 2013 - Saint Petersburg, Russian Federation
    Duration: 13 Jul 201319 Jul 2013
    Conference number: 25

    Publication series

    NameLecture Notes in Computer Science
    PublisherSpringer
    Volume8044
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    Conference25th International Conference on Computer Aided Verification, CAV 2013
    Abbreviated titleCAV
    Country/TerritoryRussian Federation
    CitySaint Petersburg
    Period13/07/1319/07/13

    Keywords

    • FMT-MC: MODEL CHECKING
    • Subsumption
    • Inclusion abstraction
    • Timed automata
    • UPPAAL
    • Opaal
    • Parallel
    • LTL
    • LTSMIN
    • LU abstraction
    • liveness
    • Model checking
    • Multi-core
    • NDFS
    • Büchi emptiness
    • CNDFS
    • n/a OA procedure

    Fingerprint

    Dive into the research topics of 'Multi-core emptiness checking of timed Büchi automata using inclusion abstraction'. Together they form a unique fingerprint.

    Cite this