by Peter Bezděk, Nikola Beneš, Vojtěch Havel, Jiří Barnat, Ivana Černá, A full version of the paper presented at conference ICTAC 2014. June 2014, 27 pages.
FIMU-RS-2014-04. Available as Postscript, PDF.
We introduce the Clock-Aware Linear Temporal Logic (CA-LTL) for expressing linear time properties of timed automata, and show how to apply the standard automata-based approach of Vardi and Wolper to check for the validity of a CA-LTL formula over the continuous-time semantics of a~timed automaton. Our model checking procedure employs zone-based abstraction and a new concept of the so called ultraregions. We also show that the Timed Büchi Automaton Emptiness problem is not the problem that the intended automata-based approach to CA-LTL model checking is reduced to. Finally, we give the necessary proofs of correctness, some hints for an efficient implementation, and preliminary experimental evaluation of our technique.
by Jiří Barnat, Petr Bauch, Luboš Brim, Milan Češka, July 2010, 24 pages.
FIMU-RS-2010-10. Available as Postscript, PDF.
The problem of decomposition of a directed graph into its strongly connected
by Jiří Barnat, Luboš Brim, Milan Češka, Tomáš Lamr, June 2009, 18 pages.
FIMU-RS-2009-05. Available as Postscript, PDF.
Recent technological developments made available various many-core hardware platforms. For example,
by Jiří Barnat, Ivana Černá, Jana Tůmová, June 2009, 35 pages.
FIMU-RS-2009-04. Available as Postscript, PDF.
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
by Jiří Barnat, Luboš Brim, Pavel Šimeček, January 2007, 20 pages.
FIMU-RS-2007-01. Available as Postscript, PDF.
We show how to adopt existing non-DFS-based algorithm OWCTY for accepting cycle detection to the I/O efficient setting and compare the I/O efficiency and practical performance of the adopted algorithm to the existing I/O efficient LTL model checking approach of Edelkamp et al. We show that while the new algorithm exhibits similar I/O complexity with respect to the size of the graph, it avoids the quadratic increase in the size of the graph of the approach of Edelkamp et al. Therefore, the absolute numbers of I/O operations are significantly smaller and the algorithm exhibits better practical performance.
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.
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.
by Jiří Barnat, Luboš Brim, Jakub Chaloupka, September 2004, 57 pages.
FIMU-RS-2004-07. Available as Postscript, PDF.
We propose a parallel distributed memory on-the-fly algorithm for enumerative LTL model checking. The algorithm is designed for network of workstations communicating via MPI. The detection of cycles (faulty runs) effectively employs the so called back-level edges. In particular, a parallel level synchronized breadth first search of the graph is performed to discover all back-level edges and for each level the back-level edges are checked in parallel by a nested search procedure to confirm or refute the presence of a cycle. Several optimizations of the basic algorithm are presented and advantages and drawbacks of their application to distributed LTL model checking are discussed. Experimental evaluation of the algorithm is presented.
by Jiří Barnat, Luboš Brim, Jitka Stříbrná, December 2000, 19 pages.
FIMU-RS-2000-10. Available as Postscript, PDF.
Distributed version of the SPIN model checker has not been extended to allow distributed model-checking of LTL formulas. This paper explores the possibility of performing nested depth first search algorithm in distributed SPIN. A distributed version of the algorithm is presented, and its complexity is discussed.