Technical Reports

A List by Author: Pavel ©imeèek

e-mail:

xsimece1(a)fi.muni.cz

Estimating State Space Parameters

by Radek Pelánek, Pavel ©imeèek, January 2008, 21 pages.

FIMU-RS-2008-01. Available as Postscript, PDF.

Abstract:

We introduce the problem of estimation of state space parameters, argue that it is an interesting and practically relevant problem, and study several simple estimation techniques. Particularly, we focus on estimation of the number of reachable states. We study techniques based on sampling of the state space and techniques that employ data mining techniques (classification trees, neural networks) over parameters of breadth-first search. We show that even through the studied techniques are not able to produce exact estimates, it is possible to obtain useful information about a state space by sampling and to use this information to automate the verification process.

LTL model checking with I/O-Efficient Accepting Cycle Detection

by Jiøí Barnat, Lubo¹ Brim, Pavel ©imeèek, January 2007, 20 pages.

FIMU-RS-2007-01. Available as Postscript, PDF.

Abstract:

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.