##
**Graph-reducible term rewriting systems.**
*(English)*
Zbl 0787.68058

Graph grammars and their application to computer science, Proc. 4th Int. Workshop, Bremen/Ger. 1990, Lect. Notes Comput. Sci. 532, 622-636 (1991).

Summary: [For the entire collection see Zbl 0753.00023.]

Term rewriting is commonly implemented by graph reduction in order to improve efficiency. In general, however, graph reduction is not complete: a term may be not normalizable through graph derivations although a normal form exists. Term rewriting systems which permit a complete implementation by graph reduction are called graph-reducible. We show that the following property is sufficient for graph-reducibility: every term having a normal form can be normalized by parallel term rewrite steps in which a rule is applied to all occurrences of some subterm. As a consequence, a broad class of term rewriting systems which includes all terminating and all orthogonal systems can be shown to be graph- reducible.

Term rewriting is commonly implemented by graph reduction in order to improve efficiency. In general, however, graph reduction is not complete: a term may be not normalizable through graph derivations although a normal form exists. Term rewriting systems which permit a complete implementation by graph reduction are called graph-reducible. We show that the following property is sufficient for graph-reducibility: every term having a normal form can be normalized by parallel term rewrite steps in which a rule is applied to all occurrences of some subterm. As a consequence, a broad class of term rewriting systems which includes all terminating and all orthogonal systems can be shown to be graph- reducible.

### MSC:

68Q42 | Grammars and rewriting systems |

68R10 | Graph theory (including graph drawing) in computer science |