Graph Subsumption in Abstract State Space Exploration

Eduardo Zambon, Arend Rensink

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

    73 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

    Publication series

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

    Keywords

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

    Cite this

    Zambon, E., & Rensink, A. (2012). Graph Subsumption in Abstract State Space Exploration. In A. Wijs, D. Bosnacki, & S. Edelkamp (Eds.), Proceedings of First Workshop on Graph Inspection and Traversal Engineering (GRAPHite 2012) (pp. 35-49). (Electronic Proceedings in Theoretical Computer Science; Vol. 99). Open Publishing Association. https://doi.org/10.4204/EPTCS.99.6