On-the-fly State Space Reductions

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

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

Abstract:

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.