Orderings for Term-Rewriting Systems

Dershowitz, N. (1982). Orderings for Term-Rewriting Systems. Theoretical Computer Science, 3975(82), 0304-3975.

Type

Journal article

Intellectual base

Primary research

Year

1982

DOI

10.1016/0304-3975(82)90026-3

Link

https://doi.org/10.1016/0304-3975(82)90026-3

Cited from

mathematics

Cited by

2 citations across 2 artifacts.

Each citation links to the sentence it supports in the citing article.

Primes

• Well-Foundedness (Well-Ordering)
  • Totality additional to well-foundedness yields well-ordering, but many important well-founded relations (structural recursion on data types, term-rewriting orders, multiset orderings) are not total — a class of partial well-founded reduction orders that Dershowitz (1982) catalogues in his survey of term-rewriting orderings.

    This sourceSurvey of well-founded reduction orders (including LPO, RPO, multiset extensions).

Domain-specific

• Path ordering (term rewriting)
  • … transfers from A canonical instance directly demonstrates that the ordering is well-founded, stable under substitution and context as required, and every oriented rewrite rule strictly decreases. to An applied instance preserves the same invariant under a changed scale, notation, jurisdiction, or implementation..

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. See how references were verified.

Registry ID ref:0a800b0a5017 · see in the full table