The ComBack method: extending hash compaction with backtracking

M. Westergaard, L.M. Kristensen, G.S. Brodal, L. Arge

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

    11 Citations (Scopus)

    Abstract

    This paper presents the ComBack method for explicit state space exploration. The ComBack method extends the well-known hash compaction method such that full coverage of the state space is guaranteed. Each encountered state is mapped into a compressed state descriptor (hash value) as in hash compaction. The method additionally stores for each state an integer representing the identity of the state and a backedge to a predecessor state. This allows hash collisions to be resolved on-the-fly during state space exploration using backtracking to reconstruct the full state descriptors when required for comparison with newly encountered states. A prototype implementation of the ComBack method is used to evaluate the method on several example systems and compare its performance to related methods. The results show a reduction in memory usage at an acceptable cost in exploration time.
    Original languageEnglish
    Title of host publicationProceedings of the 28th International Conference on Petri Nets and Other Models of Concurrency (ICATPN 2007), 25-29 June 2007, Siedcle, Poland
    EditorsA. Yakovlev, J. Kleijn
    Place of PublicationBerlin
    PublisherSpringer
    Pages445-464
    ISBN (Print)978-3-540-73093-4
    DOIs
    Publication statusPublished - 2007

    Publication series

    NameLecture Notes in Computer Science
    Volume4546
    ISSN (Print)0302-9743

    Fingerprint

    Dive into the research topics of 'The ComBack method: extending hash compaction with backtracking'. Together they form a unique fingerprint.

    Cite this