State Space Reduction of Linear Processes using Control Flow Reconstruction

    Research output: Book/ReportReportAcademic

    13 Citations (Scopus)
    58 Downloads (Pure)

    Abstract

    We present a new method for fighting the state space explosion of process algebraic specifications, by performing static analysis on an intermediate format: linear process equations (LPEs). Our method consists of two steps: (1) we reconstruct the LPE's control flow, detecting control flow parameters that were introduced by linearisation as well as those already encoded in the original specification; (2) we reset parameters found to be irrelevant based on data flow analysis techniques similar to traditional liveness analysis, modified to take into account the parallel nature of the specifications. Our transformation is correct with respect to strong bisimilarity, and never increases the state space. Case studies show that impressive reductions occur in practice, which could not be obtained automatically without reconstructing the control flow.
    Original languageUndefined
    Place of PublicationEnschede
    PublisherCentre for Telematics and Information Technology (CTIT)
    Number of pages25
    Publication statusPublished - 23 Jun 2009

    Publication series

    NameCTIT Technical Report Series
    PublisherUniversity of Twente, Centre for Telematics and Information Technology (CTIT)
    No.TR-CTIT-09-24
    ISSN (Print)1381-3625

    Keywords

    • State space reduction
    • EWI-15471
    • Dead variable analysis
    • IR-67478
    • Control flow reconstruction
    • Process Algebra
    • METIS-263893

    Cite this

    van de Pol, J. C., & Timmer, M. (2009). State Space Reduction of Linear Processes using Control Flow Reconstruction. (CTIT Technical Report Series; No. TR-CTIT-09-24). Enschede: Centre for Telematics and Information Technology (CTIT).