×

SIGREF – a symbolic bisimulation tool box. (English) Zbl 1161.68631

Graf, Susanne (ed.) et al., Automated technology for verification and analysis. 4th international symposium, ATVA 2006, Beijing, China, October 23–26, 2006. Proceedings. Berlin: Springer (ISBN 978-3-540-47237-7/pbk). Lecture Notes in Computer Science 4218, 477-492 (2006).
Summary: We present a uniform signature-based approach to compute the most popular bisimulations. Our approach is implemented symbolically using BDDs, which enables the handling of very large transition systems. Signatures for the bisimulations are built up from a few generic building blocks, which naturally correspond to efficient BDD operations. Thus, the definition of an appropriate signature is the key for a rapid development of algorithms for other types of bisimulation.
We provide experimental evidence of the viability of this approach by presenting computational results for many bisimulations on real-world instances. The experiments show cases where our framework can handle state spaces efficiently that are far too large to handle for any tool that requires an explicit state space description.
For the entire collection see [Zbl 1137.68008].

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

SIGREF; CADP; CUDD
PDFBibTeX XMLCite
Full Text: DOI Link