Confluence up to garbage in graph transformation
| Autor: | Detlef Plump, Graham Campbell |
|---|---|
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Discrete mathematics Computer Science - Logic in Computer Science Class (set theory) Graph rewriting Lemma (mathematics) General Computer Science Computer science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Logic in Computer Science (cs.LO) Theoretical Computer Science Critical pair TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Transformation (function) 010201 computation theory & mathematics TheoryofComputation_LOGICSANDMEANINGSOFPROGRAMS Confluence 0202 electrical engineering electronic engineering information engineering Graph reduction 020201 artificial intelligence & image processing Garbage |
| Zdroj: | Theoretical Computer Science. 884:1-22 |
| ISSN: | 0304-3975 |
| Popis: | 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. 33 pages, 2021 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect