On the random structure of behavioural transition systems

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

72 Downloads (Pure)

Samenvatting

Random graphs have the property that they are very predictable. Even by exploring a small part reliable observations are possible regarding their structure and size. An unfortunate observation is that standard models for random graphs, such as the Erdös-Rényi model, do not reflect the structure of the graphs that describe distributed systems and protocols. In this paper we propose to use the parallel composition of such random graphs to model ‘real’ state spaces. We show how we can use this structure to predict the size of state spaces, and we can use it to explain that software bugs are in practice far easier to find than predicted by the standard random graph models. By some practical experiments we show that our new random model is an improvement over the standard model in predicting properties of transition systems representing realistic systems. Keywords: Random graph, P-parallel random transition system, state space size
Originele taal-2Engels
Titel14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings)
RedacteurenM. Huisman, J.C. Pol, van de
UitgeverijCTIT
Pagina's141-156
StatusGepubliceerd - 2014
Evenement14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014) - University of Twente, Enschede, Nederland
Duur: 24 sep 201426 sep 2014
Congresnummer: 14

Publicatie series

NaamCTIT Workshop Proceedings Series
VolumeWP 14-01
ISSN van geprinte versie1574-0846

Congres

Congres14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014)
Verkorte titelAVoCS 2014
LandNederland
StadEnschede
Periode24/09/1426/09/14
Ander14th International Workshop on Automated Verification of Critical Systems

Vingerafdruk Duik in de onderzoeksthema's van 'On the random structure of behavioural transition systems'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Groote, J. F., van der Hofstad, R. W., & Raffelsieper, M. (2014). On the random structure of behavioural transition systems. In M. Huisman, & J. C. Pol, van de (editors), 14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings) (blz. 141-156). (CTIT Workshop Proceedings Series; Vol. WP 14-01). CTIT.