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
Term , term / tərm/ • n. 1. a word or phrase used to describe a thing or to express a concept, esp. in a particular kind of language or branch of study: the… Puree , pu·rée / pyoŏˈrā; -ˈrē/ • n. a smooth, creamy substance made of liquidized or crushed fruit or vegetables: stir in the tomato purée. • v. (pu·rées ,… System , sys·tem / ˈsistəm/ • n. 1. a set of connected things or parts forming a complex whole, in particular: ∎ a set of things working together as parts of… Reset , re·set / rēˈset/ • v. (-set·ting ; past and past part. -set ) [tr.] set again or differently: I must reset the alarm. ∎ Electr. cause (a binary devic… Rendle-Short, John , René •Manet • carnet •nota bene, René •Binet • estaminet •gratiné, matinée •cloisonné, donnée, Dubonnet, Monet •Mornay • panettone • Chardonnay •Hogm… R , R, r [Called ‘ar’]. The 18th LETTER of the Roman ALPHABET as used for English. It originated in Phoenician and was adopted and adapted by the Greeks…
About this article
orthogonal term rewriting system
You Might Also Like
NEARBY TERMS
orthogonal term rewriting system