orthogonal term rewriting system
orthogonal term rewriting system There are several useful conditions on the set E of equations defining a term rewriting system that lead to a well-behaved reduction system →E. A commonly used condition is orthogonality. If a set E of equations is orthogonal then its term rewriting system →E is Church–Rosser. A set of equations is orthogonal if it is left-linear and nonoverlapping:
the set E of equations is left-linear if for all t = t′ ∈ E, each variable that appears in t does so only once;
the set E of equations is nonoverlapping if
(a) for any pair of different equations t = t′, r = r′ ∈ E, the terms t and r do not overlap in the following sense – there exist closed substitutions τ, ρ of t, r such that ρ(r) is a subterm of τ(t) and the outermost function symbol of ρ(r) occurs as part of t,
(b) for any rule t = t′ ∈ E, t does not overlap with itself in the following sense – there exist closed substitutions τ, ρ of t such that τ(t) is a proper subterm of ρ(t) and the outermost function symbol of τ(t) occurs as a part of t.
the set E of equations is left-linear if for all t = t′ ∈ E, each variable that appears in t does so only once;
the set E of equations is nonoverlapping if
(a) for any pair of different equations t = t′, r = r′ ∈ E, the terms t and r do not overlap in the following sense – there exist closed substitutions τ, ρ of t, r such that ρ(r) is a subterm of τ(t) and the outermost function symbol of ρ(r) occurs as part of t,
(b) for any rule t = t′ ∈ E, t does not overlap with itself in the following sense – there exist closed substitutions τ, ρ of t such that τ(t) is a proper subterm of ρ(t) and the outermost function symbol of τ(t) occurs as a part of t.
More From encyclopedia.com
About this article
orthogonal term rewriting system
You Might Also Like
NEARBY TERMS
orthogonal term rewriting system