Orthogonality (term rewriting)

Orthogonality (term rewriting)

Orthogonality as a property of term rewriting systems describes where the reduction rules of the system are all left-linear, that is each variable occurs only once on the left hand side of each reduction rule, and there is no overlap between them.

Orthogonal term rewriting systems have the consequent property that all reducible expressions (redexes) within a term are completely disjoint -- that is, the redexes share no common function symbol.

For example, the term rewriting system with reduction rules

 \rho_1\ :\ f(x, y) \rightarrow g(y)
 \rho_2\ :\ h(y) \rightarrow f(g(y), y)

is orthogonal -- it is easy to observe that each reduction rule is left-linear, and the left hand side of each reduction rule shares no function symbol in common, so there is no overlap.

Orthogonal term rewriting systems are confluent.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Orthogonality — The line segments AB and CD are orthogonal to each other. Orthogonality occurs when two things can vary independently, they are uncorrelated, or they are perpendicular. Contents 1 Mathematics …   Wikipedia

  • List of mathematics articles (O) — NOTOC O O minimal theory O Nan group O(n) Obelus Oberwolfach Prize Object of the mind Object theory Oblate spheroid Oblate spheroidal coordinates Oblique projection Oblique reflection Observability Observability Gramian Observable subgroup… …   Wikipedia

  • Hermite polynomials — In mathematics, the Hermite polynomials are a classical orthogonal polynomial sequence that arise in probability, such as the Edgeworth series; in combinatorics, as an example of an Appell sequence, obeying the umbral calculus; in numerical… …   Wikipedia

  • List of mathematics articles (S) — NOTOC S S duality S matrix S plane S transform S unit S.O.S. Mathematics SA subgroup Saccheri quadrilateral Sacks spiral Sacred geometry Saddle node bifurcation Saddle point Saddle surface Sadleirian Professor of Pure Mathematics Safe prime Safe… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”