Uniform Random Sampling of Traces in Very Large Models

Authors

Alain Denise, Marie-Claude Gaudel, Sandrine-Dominique Gouraud, Richard Lassaigne, Sylvain Peyronnet

Where

Proceedings of the 1st international workshop on Random Testing 2006 (RT06)

Type

inproceedings

Projects

APMC

Date

2006-05-30

Abstract

This paper presents some first results on how to perform uniform random walks (where every trace has the same probability to occur) in very large models. The models considered here are described in a succinct way as a set of communicating reactive modules. The method relies upon techniques for counting and drawing uniformly at random words in regular languages. Each module is considered as an automaton defining such a language. It is shown how it is possible to combine local uniform drawings of traces, and to obtain some global uniform random sampling, without construction of the global model.

Bibtex (lrde.bib)

@InProceedings{	  denise.06.rt,
  author	= {Alain Denise and Marie-Claude Gaudel and
		  Sandrine-Dominique Gouraud and Richard Lassaigne and
		  Sylvain Peyronnet},
  title		= {Uniform Random Sampling of Traces in Very Large Models},
  booktitle	= {Proceedings of the 1st international workshop on Random
		  Testing 2006 (RT06)},
  year		= 2006,
  series	= {ACM digital library},
  pages		= {10--19},
  abstract	= {This paper presents some first results on how to perform
		  uniform random walks (where every trace has the same
		  probability to occur) in very large models. The models
		  considered here are described in a succinct way as a set of
		  communicating reactive modules. The method relies upon
		  techniques for counting and drawing uniformly at random
		  words in regular languages. Each module is considered as an
		  automaton defining such a language. It is shown how it is
		  possible to combine local uniform drawings of traces, and
		  to obtain some global uniform random sampling, without
		  construction of the global model.}
}