---
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.'
author:
- Andrea Corradini
- Tobias Heindel
- Barbara König
- |
    \
    Dennis Nolte
- Arend Rensink
bibliography:
- 'references.bib'
title: |
    Rewriting Abstract Structures:\
    Materialization Explained Categorically[^1]
---

Introduction {#sec:introduction}
============

Abstract interpretation [@c:abstract-interpretation] is a fundamental static analysis technique that applies not only to conventional programs but also to general infinite-state systems. Shape analysis [@srw:shape-analysis-3vl], a specific instance of abstract interpretation, pioneered an approach for analyzing pointer structures that keeps track of information about the “heap topology”, e.g., out-degrees or existence of certain paths. One central idea of shape analysis is *materialization*, which arises as companion operation to summarizing distinct objects that share relevant properties. Materialization, a.k.a. partial concretization, is 