To compose, or not to compose, that is the question: an analysis of compositional state space generation

Sander de Putter, Anton Wijs

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

1 Citaat (Scopus)

Samenvatting

To combat state space explosion several compositional verification approaches have been proposed. One such approach is compositional aggregation, where a given system consisting of a number of parallel components is iteratively composed and minimised. Compositional aggregation has shown to perform better (in the size of the largest state space in memory at one time) than classical monolithic composition in a number of cases. However, there are also cases in which compositional aggregation performs much worse. It is unclear when one should apply compositional aggregation in favor of other techniques and how it is affected by action hiding and the scale of the model. This paper presents a descriptive analysis following the quantitiative experimental approach. The experiments were conducted in a controlled test bed setup in a computer laboratory environment. A total of eight scalable models with different network topologies considering a number of varying properties were investigated comprising 119 subjects. This makes it the most comprehensive study done so far on the topic. We investigate whether there is any systematic difference in the success of compositional aggregation based on the model, scaling, and action hiding. Our results indicate that both scaling up the model and hiding more behaviour has a positive influence on compositional aggregation.

Originele taal-2Engels
TitelFormal Methods - 22nd International Symposium, FM 2018, Held as Part of the Federated Logic Conference, FloC 2018, Proceedings
RedacteurenK. Havelund, J. Peleska, B. Roscoe , E. de Vink
Plaats van productieCham
UitgeverijSpringer
Pagina's485-504
Aantal pagina's20
ISBN van elektronische versie978-3-319-95582-7
ISBN van geprinte versie978-3-319-95581-0
DOI's
StatusGepubliceerd - 1 jan 2018
Evenement22nd International Symposium on Formal Methods, FM 2018 Held as Part of the Federated Logic Conference, FloC 2018 - Oxford, Verenigd Koninkrijk
Duur: 15 jul 201817 jul 2018

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume10951 LNCS
ISSN van geprinte versie0302-9743
ISSN van elektronische versie1611-3349

Congres

Congres22nd International Symposium on Formal Methods, FM 2018 Held as Part of the Federated Logic Conference, FloC 2018
Land/RegioVerenigd Koninkrijk
StadOxford
Periode15/07/1817/07/18

Vingerafdruk

Duik in de onderzoeksthema's van 'To compose, or not to compose, that is the question: an analysis of compositional state space generation'. Samen vormen ze een unieke vingerafdruk.

Citeer dit