Bisimulation Algorithms for StochasticProcess Algebras and their BDD-based Implementation

Joost P. Katoen (Editor), H. Hermanns, M. Siegle

    Research output: Contribution to conferencePaperAcademicpeer-review

    Abstract

    Stochastic process algebras have been introduced in order to enable compositional performance analysis. The size of the state space is a limiting factor, especially if the system consists of many cooperating components. To fight state space explosion, various proposals for compositional aggregation have been made. They rely on minimisation with respect to a congruence relation. This paper addresses the computational complexity of minimisation algorithms and explains how efficient, BDD-based data structures can be employed for this purpose.
    Original languageUndefined
    Pages144-264
    Number of pages121
    Publication statusPublished - 1999
    EventFormal Methods for Real-Time and Probabilistic Systems: 5th International AMAST Workshop, ARTS'99 - Bamberg, Germany
    Duration: 1 May 19991 May 1999

    Workshop

    WorkshopFormal Methods for Real-Time and Probabilistic Systems: 5th International AMAST Workshop, ARTS'99
    Period1/05/991/05/99
    OtherMay 1999

    Keywords

    • FMT-PA: PROCESS ALGEBRAS
    • FMT-PM: PROBABILISTIC METHODS
    • IR-63312
    • FMT-BDD: BINARY DECISION DIAGRAMS
    • FMT-FMPA: FORMAL METHODS FOR PERFORMANCE ANALYSIS
    • EWI-6504

    Cite this