Name
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1007/11601548_16 | Processes, Terms and Cycles |
Keywords | Field | DocType |
graph rewriting,graph transformation | Discrete mathematics,Combinatorics,Semi-Thue system,Computer science,Hypergraph,Critical pair,Confluence,Rewriting,Graph rewriting,Knuth–Bendix completion algorithm,Lemma (mathematics) | Conference |
Volume | ISSN | ISBN |
3838 | 0302-9743 | 3-540-30911-X |
Citations | PageRank | References |
31 | 1.32 | 19 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Detlef Plump | 1 | 604 | 62.14 |