Substitution and Flip BDDs

Rune Møller Jensen, Henrik Reif Andersen

    Publikation: Bog / Antologi / Rapport / Ph.D.-afhandlingRapportForskning

    Abstract

    This report introduces two novel approaches for representing transition functions of finite transition systems encoded as Binary Decision Diagrams (BDDs). The first approach is substitution BDDs where each transition is represented by a corresponding substitution on state variables. The second is flip BDDs where each transition is defined by the set of state variables with flipped value. We show that substitution BDDs can be used to find and propagate write conflicts in synchronous and asynchronous compositions. Furthermore, our experimental evaluation suggest that the complexity of image computations based on flip BDDs may compare positively to the usual relational product computation.
    OriginalsprogEngelsk
    ForlagIT University of Copenhagen
    UdgaveTR-2003-41
    Antal sider24
    ISBN (Trykt) 8779490557
    StatusUdgivet - 2003
    NavnIT University Technical Report Series
    NummerTR-2003-41
    ISSN1600-6100

    Emneord

    • finite transition systems
    • Binary Decision Diagrams
    • substitution BDDs
    • flip BDDs
    • image computation

    Fingeraftryk

    Dyk ned i forskningsemnerne om 'Substitution and Flip BDDs'. Sammen danner de et unikt fingeraftryk.

    Citationsformater