Sigref - A Symbolic Bisimulation Tool Box

Ralf Wimmer, Marc Herbstritt, Holger Hermanns, Kelley Strampp, Bernd Becker

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    41 Citations (Scopus)
    59 Downloads (Pure)

    Abstract

    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.
    Original languageEnglish
    Title of host publicationAutomated Technology for Verification and Analysis
    Subtitle of host publication4th International Symposium, ATVA 2006, Beijing, China, October 23-26, 2006. Proceedings
    EditorsSusanne Graf, Wenhui Zhang
    PublisherSpringer
    Pages477-492
    Number of pages16
    ISBN (Electronic)978-3-540-47238-4
    ISBN (Print)978-3-540-47237-7
    DOIs
    Publication statusPublished - 2006
    Event4th International Symposium on Automated Technology for Verification and Analysis, ATVA 2006 - Beijing, China
    Duration: 23 Oct 200626 Oct 2006
    Conference number: 4

    Publication series

    NameLecture notes in Computer Science
    PublisherSpringer Verlag
    Volume4218
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Other

    Other4th International Symposium on Automated Technology for Verification and Analysis, ATVA 2006
    Abbreviated titleATVA
    CountryChina
    CityBeijing
    Period23/10/0626/10/06

    Keywords

    • IR-66950
    • EWI-9273
    • METIS-238781

    Fingerprint Dive into the research topics of 'Sigref - A Symbolic Bisimulation Tool Box'. Together they form a unique fingerprint.

  • Cite this

    Wimmer, R., Herbstritt, M., Hermanns, H., Strampp, K., & Becker, B. (2006). Sigref - A Symbolic Bisimulation Tool Box. In S. Graf, & W. Zhang (Eds.), Automated Technology for Verification and Analysis: 4th International Symposium, ATVA 2006, Beijing, China, October 23-26, 2006. Proceedings (pp. 477-492). (Lecture notes in Computer Science; Vol. 4218). Springer. https://doi.org/10.1007/11901914_35