Conditional Term Graph Rewriting with Indirect Sharing |
| |
Authors: | Enno Ohlebusch |
| |
Affiliation: | aFaculty of Technology, University of Bielefeld, 33501 Bielefeld, Germany |
| |
Abstract: | For reasons of efficiency, term rewriting is usually implemented by term graph rewriting. In term rewriting, expressions are represented as terms, whereas in term graph rewriting these are represented as directed graphs. Unlike terms, graphs allow a sharing of common subexpressions. In previous work, we have shown that conditional term graph rewriting is a sound and complete implementation for a certain class of CTRSs with strict equality, provided that a minimal structure sharing scheme is used. In this paper, we will show that this is also true for two different extensions of normal CTRSs. In contrast to the previous work, however, a non-minimal structure sharing scheme can be used. That is, the amount of sharing is increased. |
| |
Keywords: | Conditional term rewriting system term graph rewriting structure sharing |
本文献已被 ScienceDirect 等数据库收录! |
|