Graph Subsumption in Abstract State Space Exploration

Eduardo Zambon, Arend Rensink

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

    83 Downloads (Pure)

    Abstract

    In this paper we present the extension of an existing method for abstract graph-based state space exploration, called neighbourhood abstraction, with a reduction technique based on subsumption. Basically, one abstract state subsumes another when it covers more concrete states; in such a case, the subsumed state need not be included in the state space, thus giving a reduction. We explain the theory and especially also report on a number of experiments, which show that subsumption indeed drastically reduces both the state space and the resources (time and memory) needed to compute it.
    Original languageUndefined
    Title of host publicationProceedings of First Workshop on Graph Inspection and Traversal Engineering (GRAPHite 2012)
    EditorsA. Wijs, D. Bosnacki, S. Edelkamp
    PublisherOpen Publishing Association
    Pages35-49
    Number of pages15
    DOIs
    Publication statusPublished - Apr 2012
    EventFirst Workshop on Graph Inspection and Traversal Engineering, GRAPHite 2012 - Tallinn, Estonia
    Duration: 1 Apr 20121 Apr 2012

    Publication series

    NameElectronic Proceedings in Theoretical Computer Science
    PublisherOpen Publishing Association
    Volume99
    ISSN (Print)2075-2180
    ISSN (Electronic)2075-2180

    Workshop

    WorkshopFirst Workshop on Graph Inspection and Traversal Engineering, GRAPHite 2012
    Period1/04/121/04/12
    Other1 April 2012

    Keywords

    • EWI-22467
    • Graph Transformation
    • GROOVE
    • METIS-289768
    • IR-82192
    • Abstract State Space Exploration
    • Symmetry Reduction

    Cite this