Technical Reports

A List by Author: Jana Tùmová

e-mail:

xtumova(a)fi.muni.cz

Quantitative Model Checking of Systems with Degradation (Full Paper).

by Jiøí Barnat, Ivana Èerná, Jana Tùmová, June 2009, 35 pages.

FIMU-RS-2009-04. Available as Postscript, PDF.

Abstract:

In this paper we describe a rather specialized quality of a system -- the degradation. We demonstrate systems that naturally incorporate degradation phenomenon and we show how these systems can be verified by adapting the standard automatabased approach to LTL model checking. We introduce Büchi Automata with Degradation Constraints (BADCs) to specify the desired properties of systems with degradation and we describe how these can be used for verification. A major obstacle in the verification process is that the synchronous product of the system and the Büchi automaton may be infinite, which we deal with by introducing a normal form of the Büchi automata and normalizing procedure. We also show that the newly introduced formalism can be used to distinguish MDPs indistinguishable by any LTL, PCTL or even PCTL* formula.

Distributed Qualitative LTL Model Checking of Markov Decision Processes

by Jiøí Barnat, Lubo¹ Brim, Ivana Èerná, Milan Èe¹ka, Jana Tùmová, September 2006, 19 pages.

FIMU-RS-2006-04. Available as Postscript, PDF.

Abstract:

Probabilistic processes are used to model concurrent programs that exhibit uncertainty. The state explosion problem for probabilistic systems is more critical than in the non-probabilistic case. In the paper we propose a cluster-based algorithm for qualitative LTL model checking of finite state Markov decision processes. We use the automata approach which reduces the model checking problem to the question of existence of an accepting end component. The algorithm uses repeated reachability which systematically eliminates states that cannot belong to any accepting end component. A distinguished feature of the distributed algorithm is that its complexity meets the complexity of the best known sequential algorithm.