Solution of Large Markov Models Using Lumping Techniques and Symbolic Data Structures

In particular, we have developed the fastest known CTMC lumping algorithm with the running time of O (m log n), where n and m are the number of states and non-zero entries of the generator matrix of the CTMC, respectively. We have also combined the use of symbolic data structures with state-lumping techniques to develop an efficient symbolic state-space exploration algorithm for state-sharing composed models that exploits lumpings that are due to equally behaving components. Finally, we have developed a new compositional algorithm that lumps CTMCs represented as MDs. Unlike other compositional lumping algorithms, our algorithm does not require any knowledge of the modeling formalisms from which the MDs were generated. Our approach relies on local conditions, i.e., conditions on individual nodes of the MD.

Name thesis:degree_name

Ph.D.

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Computer Science

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2015

Author dc:creator

• Derisavi, Salem

Contributors dc:contributor

• Sanders, William H.

• Computer Science

Language dc:language

eng

Identifier

(MiAaPQ)AAI3198968

OAI identifier oai:identifier

oai:www.ideals.illinois.edu:2142/81681