TY - JOUR

T1 - On the random structure of behavioural transition systems

AU - Groote, J.F.

AU - van der Hofstad, R.W.

AU - Raffelsieper, M.

PY - 2016/10/15

Y1 - 2016/10/15

N2 - Numerous properties of random graphs are highly 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 practical experiments we show that our new probabilistic model is an improvement over the standard model in predicting properties of transition systems representing realistic systems.

AB - Numerous properties of random graphs are highly 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 practical experiments we show that our new probabilistic model is an improvement over the standard model in predicting properties of transition systems representing realistic systems.

KW - P-parallel random transition system

KW - Random graph

KW - State space size

UR - http://www.scopus.com/inward/record.url?scp=84960532336&partnerID=8YFLogxK

U2 - 10.1016/j.scico.2016.02.006

DO - 10.1016/j.scico.2016.02.006

M3 - Article

AN - SCOPUS:84960532336

SN - 0167-6423

VL - 128

SP - 51

EP - 67

JO - Science of Computer Programming

JF - Science of Computer Programming

ER -