Bachelor Thesis BCLR-2017-12

BibliographyBeeh, Tobias: Transformations between Markov Chains and Stochastic Regular Expressions.
University of Stuttgart, Faculty of Computer Science, Electrical Engineering, and Information Technology, Bachelor Thesis (2017).
59 pages, english.
CR-SchemaG.3 (Probability and Statistics)
Abstract

Stochastic processes need to be modelled in many cases, e.g. for reliability analysis, for artificial intelligence and in genetic programming. Mostly markov models are used for this, but there are other approaches as well, like stochastic languages. To provide more flexibility in working with stochastic models, this paper discusses possibilities to transform these into each other. The transformation between so called Stochastic Regular Expressions and Discrete Time Markov Chains can be done similar to algorithms used for formal, non-stochastic languages. This paper describes this transformation in detail. Furthermore, possibilities to apply delta changes on the transformation to run consecutive transformations faster are discussed. A proof-of-concept implementation for this algorithm is provided and both explained and evaluated in this paper. It turns out that the implementation of the transformation from Discrete Time Markov Chains to Stochastic Regular Expressions is very time- and memory consuming and produces large results in its current state, while the other direction works pretty well. Furthermore, the application of delta changes yields to significant performance improvements for large models.

Full text and
other links
PDF (406482 Bytes)
Access to students' publications restricted to the faculty due to current privacy regulations
Department(s)University of Stuttgart, Institute of Software Technology, Software Reliability and Security
Superviser(s)van Hoorn, Dr. André; Getir, Sinem
Entry dateSeptember 27, 2018
   Publ. Computer Science