Back to Search
Start Over
Single pushout rewriting in comprehensive systems of graph-like structures
- Source :
- Theoretical Computer Science
- Publication Year :
- 2021
- Publisher :
- Elsevier BV, 2021.
-
Abstract
- The elegance of the single-pushout (SPO) approach to graph transformations arises from substituting total morphisms by partial ones in the underlying category. SPO's applicability depends on the durability of pushouts after this transition. There is a wide range of work on the question when pushouts exist in categories with partial morphisms starting with the pioneering work of Lowe and Kennaway and ending with an essential characterisation in terms of an exactness property (for the interplay between pullbacks and pushouts) and an adjointness condition (w.r.t. inverse image functions) by Hayman and Heindel. Triple graphs and graph diagrams are frameworks to synchronise two or more updatable data sources by means of internal mappings, which identify common sub-structures. Comprehensive systems generalise these frameworks, treating the network of data sources and their structural inter-relations as a homogeneous comprehensive artefact, in which partial maps identify commonalities. Although this inherent partiality produces amplified complexity, we can show that Heindel's characterisation still yields existence of pushouts in the category of comprehensive systems and reflective partial morphisms and thus enables computing by typed SPO graph transformation.
- Subjects :
- Graph rewriting
Property (philosophy)
General Computer Science
Computer science
Pushout
upper adjoint
comprehensive system
VDP::Matematikk og Naturvitenskap: 400::Informasjons- og kommunikasjonsvitenskap: 420
hereditary pushout
Graph
Theoretical Computer Science
Algebra
partial morphism
category theory
Range (mathematics)
Morphism
single pushout rewriting
Homogeneous
Mathematics::Category Theory
Rewriting
Subjects
Details
- ISSN :
- 03043975
- Volume :
- 884
- Database :
- OpenAIRE
- Journal :
- Theoretical Computer Science
- Accession number :
- edsair.doi.dedup.....a3e36574324124e79ef4396425d97121