Automated generation of partial Markov chain from high level descriptions. (July 2015)

• Record Type: Journal Article
• Authors: Brameret, P.-A.; Rauzy, A.; Roussel, J.-M.
• Is Part Of: Reliability engineering & system safety. Volume 139(2015:Jul.)
• Page Start: 179
• Page End: 187
• Publication Date: 2015-07
• Subjects: Model Based Safety Assessment -- Markov chains -- State space build -- AltaRica; Reliability (Engineering) -- Periodicals; System safety -- Periodicals; Industrial safety -- Periodicals; Fiabilité -- Périodiques; Sécurité des systèmes -- Périodiques; Sécurité du travail -- Périodiques; 620.00452
• DOI: 10.1016/j.ress.2015.02.009
• Languages: English
• ISSNs: 0951-8320

Abstract

Abstract: We propose an algorithm to generate partial Markov chains from high level implicit descriptions, namely AltaRica models. This algorithm relies on two components. First, a variation on Dijkstra׳s algorithm to compute shortest paths in a graph. Second, the definition of a notion of distance to select which states must be kept and which can be safely discarded. The proposed method solves two problems at once. First, it avoids a manual construction of Markov chains, which is both tedious and error prone. Second, up the price of acceptable approximations, it makes it possible to push back dramatically the exponential blow-up of the size of the resulting chains. We report experimental results that show the efficiency of the proposed approach. Abstract : Highlights: We generate Markov chains from a higher level safety modeling language (AltaRica). We use a variation on Dijkstra׳s algorithm to generate partial Markov chains. Hence we solve two problems: the first problem is the tedious manual construction of Markov chains. The second problem is the blow-up of the size of the chains, at the cost of decent approximations. The experimental results highlight the efficiency of the method.