Confluence of Graph Transformation Revisited

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract

It is shown that it is undecidable in general whether a terminating graph rewriting system is confluent or not-in contrast to the situation for term and string rewriting systems. Critical pairs are introduced to hypergraph rewriting, a generalisation of graph rewriting, where it turns out that the mere existence of common reducts for all critical pairs of a graph rewriting system does not imply local confluence. A Critical Pair Lemma for hypergraph rewriting is then established which guarantees local confluence if each critical pair of a system has joining derivations that are compatible in that they map certain nodes to the same nodes in the common reduct.

Original languageEnglish
Title of host publicationProcesses, Terms and Cycles: Steps on the Road to Infinity
Subtitle of host publicationEssays Dedicated to Jan Willem Klop on the Occasion of His 60th Birthday
EditorsA Middledorp, V VanOostrom, F VanRaamsdonk, R DeVrijer
Place of PublicationBERLIN
PublisherSpringer
Pages280-308
Number of pages29
ISBN (Print)3-540-30911-X
DOIs
Publication statusPublished - 2005

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume3838

Keywords

  • TERM REWRITING-SYSTEMS

Cite this