On the random structure of behavioural transition systems

J.F. Groote; R.W. van der Hofstad; M. Raffelsieper

On the random structure of behavioural transition systems

J.F. Groote, R.W. van der Hofstad, M. Raffelsieper

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

86 Downloads (Pure)

Abstract

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

Original language	English
Title of host publication	14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings)
Editors	M. Huisman, J.C. Pol, van de
Publisher	CTIT
Pages	141-156
Publication status	Published - 2014
Event	14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014) - University of Twente, Enschede, Netherlands Duration: 24 Sep 2014 → 26 Sep 2014 Conference number: 14

Publication series

Name	CTIT Workshop Proceedings Series
Volume	WP 14-01
ISSN (Print)	1574-0846

Conference

Conference	14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014)
Abbreviated title	AVoCS 2014
Country/Territory	Netherlands
City	Enschede
Period	24/09/14 → 26/09/14
Other	14th International Workshop on Automated Verification of Critical Systems

Access to Document

publishers versionFinal published version, 300 KB

Cite this

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 (Eds.), 14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings) (pp. 141-156). (CTIT Workshop Proceedings Series; Vol. WP 14-01). CTIT.

@inproceedings{3518a6ccf3e447ada7a7c9ab42b320b1,

title = "On the random structure of behavioural transition systems",

abstract = "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{\"o}s-R{\'e}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 {\textquoteleft}real{\textquoteright} 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",

author = "J.F. Groote and {van der Hofstad}, R.W. and M. Raffelsieper",

year = "2014",

language = "English",

series = "CTIT Workshop Proceedings Series",

publisher = "CTIT",

pages = "141--156",

editor = "M. Huisman and {Pol, van de}, J.C.",

booktitle = "14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings)",

note = "14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014), AVoCS 2014 ; Conference date: 24-09-2014 Through 26-09-2014",

}

Groote, JF , van der Hofstad, RW & Raffelsieper, M 2014, On the random structure of behavioural transition systems. in M Huisman & JC Pol, van de (eds), 14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings). CTIT Workshop Proceedings Series, vol. WP 14-01, CTIT, pp. 141-156, 14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014), Enschede, Netherlands, 24/09/14.

On the random structure of behavioural transition systems. / Groote, J.F.; van der Hofstad, R.W.; Raffelsieper, M.

14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings). ed. / M. Huisman; J.C. Pol, van de. CTIT, 2014. p. 141-156 (CTIT Workshop Proceedings Series; Vol. WP 14-01).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the random structure of behavioural transition systems

AU - Groote, J.F.

AU - van der Hofstad, R.W.

AU - Raffelsieper, M.

N1 - Conference code: 14

PY - 2014

Y1 - 2014

N2 - 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

AB - 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

M3 - Conference contribution

T3 - CTIT Workshop Proceedings Series

SP - 141

EP - 156

BT - 14th International Workshop on Automated Verification of Critical Systems (AVOCS14, Enschede, The Netherlands, September 24-26, 2014. Pre-proceedings)

A2 - Huisman, M.

A2 - Pol, van de, J.C.

PB - CTIT

T2 - 14th International Workshop on Automated Verification of Critical Systems (AVoCS 2014)

Y2 - 24 September 2014 through 26 September 2014

ER -

On the random structure of behavioural transition systems

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this