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

Plump, Detlef

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.

MSC:

68Q42	Grammars and rewriting systems
68R10	Graph theory (including graph drawing) in computer science

Keywords:

completeness; term rewriting; graph reduction

Citations:

Zbl 0753.00023