A Modal-Logic Based Graph Abstraction

J. Bauer, I.B. Boneva, M.E. Kurban, Arend Rensink

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

13 Citations (Scopus)

Abstract

Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract graphs. In this work, we present a new framework of abstractions unifying and generalising existing takes on abstract graph transformation. The precision of the abstraction can be adjusted according to the properties to be verified facilitating abstraction refinement. We present a modal logic defined on graphs, which is preserved and reflected by our abstractions. Finally, we demonstrate the usability of the framework by verifying a graph transformation model of a firewall.
Original languageUndefined
Title of host publicationInternational Conference on Graph Transformations (ICGT)
EditorsH Ehrig, R. Heckel, G. Rozenberg, G. Taentzer
Place of PublicationBerlin
PublisherSpringer
Pages321-335
Number of pages15
ISBN (Print)978-3-540-87404-1
DOIs
Publication statusPublished - 2008

Publication series

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

Keywords

  • IR-62461
  • METIS-251183
  • EWI-13439

Cite this

Bauer, J., Boneva, I. B., Kurban, M. E., & Rensink, A. (2008). A Modal-Logic Based Graph Abstraction. In H. Ehrig, R. Heckel, G. Rozenberg, & G. Taentzer (Eds.), International Conference on Graph Transformations (ICGT) (pp. 321-335). [10.1007/978-3-540-87405-8_22] (Lecture Notes in Computer Science; Vol. 5214, No. Supplement). Berlin: Springer. https://doi.org/10.1007/978-3-540-87405-8_22
Bauer, J. ; Boneva, I.B. ; Kurban, M.E. ; Rensink, Arend. / A Modal-Logic Based Graph Abstraction. International Conference on Graph Transformations (ICGT). editor / H Ehrig ; R. Heckel ; G. Rozenberg ; G. Taentzer. Berlin : Springer, 2008. pp. 321-335 (Lecture Notes in Computer Science; Supplement).
@inproceedings{bef3e9473bfe4f48b0b8b5a5804b44e3,
title = "A Modal-Logic Based Graph Abstraction",
abstract = "Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract graphs. In this work, we present a new framework of abstractions unifying and generalising existing takes on abstract graph transformation. The precision of the abstraction can be adjusted according to the properties to be verified facilitating abstraction refinement. We present a modal logic defined on graphs, which is preserved and reflected by our abstractions. Finally, we demonstrate the usability of the framework by verifying a graph transformation model of a firewall.",
keywords = "IR-62461, METIS-251183, EWI-13439",
author = "J. Bauer and I.B. Boneva and M.E. Kurban and Arend Rensink",
note = "EATCS Award for the Best Theoretical Paper",
year = "2008",
doi = "10.1007/978-3-540-87405-8_22",
language = "Undefined",
isbn = "978-3-540-87404-1",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
number = "Supplement",
pages = "321--335",
editor = "H Ehrig and R. Heckel and G. Rozenberg and G. Taentzer",
booktitle = "International Conference on Graph Transformations (ICGT)",

}

Bauer, J, Boneva, IB, Kurban, ME & Rensink, A 2008, A Modal-Logic Based Graph Abstraction. in H Ehrig, R Heckel, G Rozenberg & G Taentzer (eds), International Conference on Graph Transformations (ICGT)., 10.1007/978-3-540-87405-8_22, Lecture Notes in Computer Science, no. Supplement, vol. 5214, Springer, Berlin, pp. 321-335. https://doi.org/10.1007/978-3-540-87405-8_22

A Modal-Logic Based Graph Abstraction. / Bauer, J.; Boneva, I.B.; Kurban, M.E.; Rensink, Arend.

International Conference on Graph Transformations (ICGT). ed. / H Ehrig; R. Heckel; G. Rozenberg; G. Taentzer. Berlin : Springer, 2008. p. 321-335 10.1007/978-3-540-87405-8_22 (Lecture Notes in Computer Science; Vol. 5214, No. Supplement).

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

TY - GEN

T1 - A Modal-Logic Based Graph Abstraction

AU - Bauer, J.

AU - Boneva, I.B.

AU - Kurban, M.E.

AU - Rensink, Arend

N1 - EATCS Award for the Best Theoretical Paper

PY - 2008

Y1 - 2008

N2 - Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract graphs. In this work, we present a new framework of abstractions unifying and generalising existing takes on abstract graph transformation. The precision of the abstraction can be adjusted according to the properties to be verified facilitating abstraction refinement. We present a modal logic defined on graphs, which is preserved and reflected by our abstractions. Finally, we demonstrate the usability of the framework by verifying a graph transformation model of a firewall.

AB - Infinite or very large state spaces often prohibit the successful verification of graph transformation systems. Abstract graph transformation is an approach that tackles this problem by abstracting graphs to abstract graphs of bounded size and by lifting application of productions to abstract graphs. In this work, we present a new framework of abstractions unifying and generalising existing takes on abstract graph transformation. The precision of the abstraction can be adjusted according to the properties to be verified facilitating abstraction refinement. We present a modal logic defined on graphs, which is preserved and reflected by our abstractions. Finally, we demonstrate the usability of the framework by verifying a graph transformation model of a firewall.

KW - IR-62461

KW - METIS-251183

KW - EWI-13439

U2 - 10.1007/978-3-540-87405-8_22

DO - 10.1007/978-3-540-87405-8_22

M3 - Conference contribution

SN - 978-3-540-87404-1

T3 - Lecture Notes in Computer Science

SP - 321

EP - 335

BT - International Conference on Graph Transformations (ICGT)

A2 - Ehrig, H

A2 - Heckel, R.

A2 - Rozenberg, G.

A2 - Taentzer, G.

PB - Springer

CY - Berlin

ER -

Bauer J, Boneva IB, Kurban ME, Rensink A. A Modal-Logic Based Graph Abstraction. In Ehrig H, Heckel R, Rozenberg G, Taentzer G, editors, International Conference on Graph Transformations (ICGT). Berlin: Springer. 2008. p. 321-335. 10.1007/978-3-540-87405-8_22. (Lecture Notes in Computer Science; Supplement). https://doi.org/10.1007/978-3-540-87405-8_22