Paper Info
Title
Confluence Up To Garbage In Graph Transformation
Abstract
The transformation of graphs and graph-like structures is ubiquitous in computer science. When a system is described by graph-transformation rules, it is often desirable that the rules are both terminating and confluent so that rule applications in an arbitrary order produce unique resulting graphs. However, there are application scenarios where the rules are not globally confluent but confluent on a subclass of graphs that are of interest. In other words, non-resolvable conflicts can only occur on graphs that are considered as "garbage". In this paper, we introduce the notion of confluence up to garbage and generalise Plump's critical pair lemma for double-pushout graph transformation, providing a sufficient condition for confluence up to garbage by non-garbage critical pair analysis. We apply our results in two case studies about efficient language recognition: we present backtracking-free graph reduction systems which recognise a class of flow diagrams and a class of labelled series-parallel graphs, respectively. Both systems are non-confluent but confluent up to garbage. We also give a critical pair condition for subcommutativity up to garbage which, together with closedness, implies confluence up to garbage even in non-terminating systems. (C) 2021 The Author(s). Published by Elsevier B.V.
Year
DOI
Venue
2021
10.1016/j.tcs.2021.06.010
THEORETICAL COMPUTER SCIENCE
Keywords
DocType
Volume
Graph transformation, Confluence, Subcommutativity, Critical pair analysis, Graph languages
Journal
884
ISSN
Citations 
PageRank 
0304-3975
0
0.34
References 
Authors
0
2
Name
Order
Citations
PageRank
Graham Campbell100.34
Detlef Plump260462.14