Rewriting Abstract Structures: Materialization Explained Categorically

Andrea Corradini, Tobias Heindel, Barbara König, Dennis Nolte*, Arend Rensink

*Corresponding author for this work

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

2 Citations (Scopus)
17 Downloads (Pure)

Abstract

The paper develops an abstract (over-approximating) semantics for double-pushout rewriting of graphs and graph-like objects. The focus is on the so-called materialization of left-hand sides from abstract graphs, a central concept in previous work. The first contribution is an accessible, general explanation of how materializations arise from universal properties and categorical constructions, in particular partial map classifiers, in a topos. Second, we introduce an extension by enriching objects with annotations and give a precise characterization of strongest post-conditions, which are effectively computable under certain assumptions.

Original languageEnglish
Title of host publicationFoundations of Software Science and Computation Structures
Subtitle of host publication22nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings
EditorsAlex Simpson, Mikolaj Bojanczyk
Place of PublicationCham
PublisherSpringer Verlag
Pages169-188
Number of pages20
ISBN (Electronic)978-3-030-17127-8
ISBN (Print)978-3-030-17126-1
DOIs
Publication statusPublished - 1 Jan 2019
Event22nd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2019 - Orea Hotel Pyramida, Prague, Czech Republic
Duration: 6 Apr 201911 Apr 2019
Conference number: 22
https://www.etaps.org/2019/fossacs

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11425 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on Foundations of Software Science and Computation Structures, FOSSACS 2019
Abbreviated titleFoSSaCS 2019
CountryCzech Republic
CityPrague
Period6/04/1911/04/19
OtherHeld as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019
Internet address

Fingerprint Dive into the research topics of 'Rewriting Abstract Structures: Materialization Explained Categorically'. Together they form a unique fingerprint.

  • Cite this

    Corradini, A., Heindel, T., König, B., Nolte, D., & Rensink, A. (2019). Rewriting Abstract Structures: Materialization Explained Categorically. In A. Simpson, & M. Bojanczyk (Eds.), Foundations of Software Science and Computation Structures: 22nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings (pp. 169-188). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11425 LNCS). Cham: Springer Verlag. https://doi.org/10.1007/978-3-030-17127-8_10