Robert Söldner ; Detlef Plump - Formalising the Double-Pushout Approach to Graph Transformation

lmcs:12748 - Logical Methods in Computer Science, October 4, 2024, Volume 20, Issue 4 - https://doi.org/10.46298/lmcs-20(4:3)2024
Formalising the Double-Pushout Approach to Graph TransformationArticle

Authors: Robert Söldner ; Detlef Plump

    In this paper, we utilize Isabelle/HOL to develop a formal framework for the basic theory of double-pushout graph transformation. Our work includes defining essential concepts like graphs, morphisms, pushouts, and pullbacks, and demonstrating their properties. We establish the uniqueness of derivations, drawing upon Rosens 1975 research, and verify the Church-Rosser theorem using Ehrigs and Kreowskis 1976 proof, thereby demonstrating the effectiveness of our formalisation approach. The paper details our methodology in employing Isabelle/HOL, including key design decisions that shaped the current iteration. We explore the technical complexities involved in applying higher-order logic, aiming to give readers an insightful perspective into the engaging aspects of working with an Interactive Theorem Prover. This work emphasizes the increasing importance of formal verification tools in clarifying complex mathematical concepts.


    Volume: Volume 20, Issue 4
    Published on: October 4, 2024
    Accepted on: August 20, 2024
    Submitted on: December 27, 2023
    Keywords: Computer Science - Logic in Computer Science

    Consultation statistics

    This page has been seen 133 times.
    This article's PDF has been downloaded 42 times.