|
Technical Report: DCC-2012-01
Learning generalized semi-Markov processes:
From stochastic discrete event systems to testing and verification
André de Matos Pedro, Maria João Frade
University of Minho, Braga, Portugal,
e-mail: pg15753@alunos.uminho.pt, mjf@di.uminho.pt
Simão Melo de Sousa
LIACC, University of Beira Interior, Covilhã, Portugal,
e-mail:desousa@ubi.pt
April 2012
Abstract
Discrete event systems (DES) are widely used to model a set of practical systems, such as: industrial systems, computer systems, and also traffic systems. This paper explores an extension of discrete event systems with an emphasis on stochastic processes, commonly called stochastic discrete event systems (SDES). There is a need to establish a stochastic abstraction and a model for SDES through a generalized semi-Markov processes (GSMP) and respectively a stochastic timed automaton. In this paper we propose a novel algorithm to learn GSMP from sample executions that can be used for quantitative analysis and verification in the context of model checking. We demonstrate that the proposed learning algorithm can correctly identify the GSMP given sufficient samples. This paper also presents a Matlab toolbox for our algorithm and a case study of the stochastic analysis for a multiprocessor system scheduler.
|