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,

Simão Melo de Sousa

LIACC, University of Beira Interior, Covilhã, Portugal,
April 2012


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.