Fair testing and stubborn sets

Antti Valmari, Walter Vogler

    Tutkimustuotos: KonferenssiartikkeliScientificvertaisarvioitu

    13 Sitaatiot (Scopus)
    27 Lataukset (Pure)

    Abstrakti

    Partial-order methods alleviate state explosion by considering only a subset of transitions in each constructed state. The choice of the subset depends on the properties that the method promises to preserve. Many methods have been developed ranging from deadlockpreserving to CTL ∗-and divergence-sensitive branching bisimilarity preserving. The less the method preserves, the smaller state spaces it constructs. Fair testing equivalence unifies deadlocks with livelocks that cannot be exited, and ignores the other livelocks. It is the weakest congruence that preserves whether the ability to make progress can be lost. We prove that a method that was designed for trace equivalence also preserves fair testing equivalence. We describe a fast algorithm for computing high-quality subsets of transitions for the method, and demonstrate its effectiveness on a protocol with a connection and data transfer phase. This is the first practical partial-order method that deals with a practical fairness assumption.

    AlkuperäiskieliEnglanti
    OtsikkoModel Checking Software
    Alaotsikko23rd International Symposium, SPIN 2016, Co-located with ETAPS 2016, Eindhoven, The Netherlands, April 7-8, 2016, Proceedings
    KustantajaSpringer Verlag
    Sivut225-243
    Sivumäärä19
    ISBN (painettu)9783319325811
    DOI - pysyväislinkit
    TilaJulkaistu - 2016
    OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisussa
    TapahtumaINTERNATIONAL WORKSHOP ON MODEL CHECKING OF SOFTWARE -
    Kesto: 1 tammik. 1900 → …

    Julkaisusarja

    NimiLecture Notes in Computer Science
    Vuosikerta9641
    ISSN (painettu)0302-9743
    ISSN (elektroninen)1611-3349

    Conference

    ConferenceINTERNATIONAL WORKSHOP ON MODEL CHECKING OF SOFTWARE
    Ajanjakso1/01/00 → …

    Julkaisufoorumi-taso

    • Jufo-taso 1

    !!ASJC Scopus subject areas

    • Yleinen tietojenkäsittelytiede
    • Theoretical Computer Science

    Sormenjälki

    Sukella tutkimusaiheisiin 'Fair testing and stubborn sets'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

    Siteeraa tätä