Technical Reports

A List by Author: Jiří Šimša


Under-Approximation Generation using Partial Order Reduction

by Luboš Brim, Ivana Černá, Pavel Moravec, Jiří Šimša, A full version of the paper submitted to conference CAV05 February 2005, 21 pages.

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


We propose a new on-the-fly approach which combines partial order reduction with the under-approximation technique for falsification and verification of LTL-X properties. It uses sensitivity relation and modified ample conditions to generate a reduced state space that is not fully stutter equivalent to the original one and it checks the desired property using representatives. Widening of under-approximations is fully automatic and does not rely on any supporting mechanisms like theorem-provers or SAT solvers.

VCD: A Visual Formalism for Specification of Heterogeneous Software Architectures

by David Šafránek, Jiří Šimša, A full version of SOFSEM 2005 paper. December 2004, 25 pages.

FIMU-RS-2004-11. Available as Postscript, PDF.


A visual formalism called Visual Coordination Diagrams (VCD) for high-level design of heterogeneous systems is presented in this paper. The language is based on a state-transition operational semantics, which allows application of formal methods to software design. Formal definition of VCD is included in the paper. Moreover, an example of use of the language is also given.

Accepting Predecessors are Better than Back Edges in Distributed LTL Model Checking

by Luboš Brim, Ivana Černá, Pavel Moravec, Jiří Šimša, A full version of the paper accepted to the conference FMCAD 2004. November 2004, 22 pages.

FIMU-RS-2004-09. Available as Postscript, PDF.


We present a new distributed-memory algorithm for enumerative LTL model-checking that is designed to be run on a cluster of workstations communicating via MPI. The detection of accepting cycles is based on computing maximal accepting predecessors and the subsequent decomposition of the graph into independent predecessor subgraphs induced by maximal accepting predecessors. Several optimizations of the basic algorithm are presented and the influence of the ordering on the algorithm performance is discussed. Experimental implementation of the algorithm shows promising results.

Responsible contact:

Please install a newer browser for this site to function properly.

More information