Technical Reports

The report FIMU-RS-2005-03

On-the-fly State Space Reductions

by Radek Pelánek, February 2005, 22 pages.

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


We present an overview of equivalences of finite state structures and discuss methods for computing reduced structures on-the-fly. We evaluate merits of these reductions on a large set of model checking case studies. It turns out that the achieved reduction can be significant, but that it is not so ``drastic" as sometimes claimed in the literature. We also propose some new reduction methods.

Responsible contact: unix(atsign)fi(dot)muni(dot)cz