Pattern-Based Graph Abstraction

Arend Rensink, Eduardo Zambon

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

10 Citations (Scopus)
17 Downloads (Pure)

Abstract

We present a new abstraction technique for the exploration of graph transformation systems with infinite state spaces. This technique is based on patterns, simple graphs describing structures of interest that should be preserved by the abstraction. Patterns are collected into pattern graphs, layered graphs that capture the hierarchical composition of smaller patterns into larger ones. Pattern graphs are then abstracted to a finite universe of pattern shapes by collapsing equivalent patterns. This paper shows how the application of production rules can be lifted to pattern shapes, resulting in an over-approximation of the original system behaviour and thus enabling verification on the abstract level.
Original languageUndefined
Title of host publicationInternational Conference on Graph Transformation (ICGT 2012)
EditorsH Ehrig, G. Engels, H.J. Kreowski, G. Rozenberg
Place of PublicationBerlin
PublisherSpringer
Pages66-80
Number of pages15
ISBN (Print)978-3-642-33653-9
DOIs
Publication statusPublished - Sep 2012

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Verlag
Volume7562
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Keywords

  • IR-82080
  • METIS-289725
  • Abstract Interpretation
  • State Space Exploration
  • Graph Transformation
  • EWI-22348
  • Abstraction

Cite this

Rensink, A., & Zambon, E. (2012). Pattern-Based Graph Abstraction. In H. Ehrig, G. Engels, H. J. Kreowski, & G. Rozenberg (Eds.), International Conference on Graph Transformation (ICGT 2012) (pp. 66-80). (Lecture Notes in Computer Science; Vol. 7562). Berlin: Springer. https://doi.org/10.1007/978-3-642-33654-6_5
Rensink, Arend ; Zambon, Eduardo. / Pattern-Based Graph Abstraction. International Conference on Graph Transformation (ICGT 2012). editor / H Ehrig ; G. Engels ; H.J. Kreowski ; G. Rozenberg. Berlin : Springer, 2012. pp. 66-80 (Lecture Notes in Computer Science).
@inproceedings{bdfe3d8c8c62434c9e9edcd281da73d9,
title = "Pattern-Based Graph Abstraction",
abstract = "We present a new abstraction technique for the exploration of graph transformation systems with infinite state spaces. This technique is based on patterns, simple graphs describing structures of interest that should be preserved by the abstraction. Patterns are collected into pattern graphs, layered graphs that capture the hierarchical composition of smaller patterns into larger ones. Pattern graphs are then abstracted to a finite universe of pattern shapes by collapsing equivalent patterns. This paper shows how the application of production rules can be lifted to pattern shapes, resulting in an over-approximation of the original system behaviour and thus enabling verification on the abstract level.",
keywords = "IR-82080, METIS-289725, Abstract Interpretation, State Space Exploration, Graph Transformation, EWI-22348, Abstraction",
author = "Arend Rensink and Eduardo Zambon",
note = "Winner of the EATCS Award for Best Paper of ICGT 2012",
year = "2012",
month = "9",
doi = "10.1007/978-3-642-33654-6_5",
language = "Undefined",
isbn = "978-3-642-33653-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "66--80",
editor = "H Ehrig and G. Engels and H.J. Kreowski and G. Rozenberg",
booktitle = "International Conference on Graph Transformation (ICGT 2012)",

}

Rensink, A & Zambon, E 2012, Pattern-Based Graph Abstraction. in H Ehrig, G Engels, HJ Kreowski & G Rozenberg (eds), International Conference on Graph Transformation (ICGT 2012). Lecture Notes in Computer Science, vol. 7562, Springer, Berlin, pp. 66-80. https://doi.org/10.1007/978-3-642-33654-6_5

Pattern-Based Graph Abstraction. / Rensink, Arend; Zambon, Eduardo.

International Conference on Graph Transformation (ICGT 2012). ed. / H Ehrig; G. Engels; H.J. Kreowski; G. Rozenberg. Berlin : Springer, 2012. p. 66-80 (Lecture Notes in Computer Science; Vol. 7562).

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

TY - GEN

T1 - Pattern-Based Graph Abstraction

AU - Rensink, Arend

AU - Zambon, Eduardo

N1 - Winner of the EATCS Award for Best Paper of ICGT 2012

PY - 2012/9

Y1 - 2012/9

N2 - We present a new abstraction technique for the exploration of graph transformation systems with infinite state spaces. This technique is based on patterns, simple graphs describing structures of interest that should be preserved by the abstraction. Patterns are collected into pattern graphs, layered graphs that capture the hierarchical composition of smaller patterns into larger ones. Pattern graphs are then abstracted to a finite universe of pattern shapes by collapsing equivalent patterns. This paper shows how the application of production rules can be lifted to pattern shapes, resulting in an over-approximation of the original system behaviour and thus enabling verification on the abstract level.

AB - We present a new abstraction technique for the exploration of graph transformation systems with infinite state spaces. This technique is based on patterns, simple graphs describing structures of interest that should be preserved by the abstraction. Patterns are collected into pattern graphs, layered graphs that capture the hierarchical composition of smaller patterns into larger ones. Pattern graphs are then abstracted to a finite universe of pattern shapes by collapsing equivalent patterns. This paper shows how the application of production rules can be lifted to pattern shapes, resulting in an over-approximation of the original system behaviour and thus enabling verification on the abstract level.

KW - IR-82080

KW - METIS-289725

KW - Abstract Interpretation

KW - State Space Exploration

KW - Graph Transformation

KW - EWI-22348

KW - Abstraction

U2 - 10.1007/978-3-642-33654-6_5

DO - 10.1007/978-3-642-33654-6_5

M3 - Conference contribution

SN - 978-3-642-33653-9

T3 - Lecture Notes in Computer Science

SP - 66

EP - 80

BT - International Conference on Graph Transformation (ICGT 2012)

A2 - Ehrig, H

A2 - Engels, G.

A2 - Kreowski, H.J.

A2 - Rozenberg, G.

PB - Springer

CY - Berlin

ER -

Rensink A, Zambon E. Pattern-Based Graph Abstraction. In Ehrig H, Engels G, Kreowski HJ, Rozenberg G, editors, International Conference on Graph Transformation (ICGT 2012). Berlin: Springer. 2012. p. 66-80. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-33654-6_5