Orderings for Term-Rewriting Systems

Dershowitz, N. (1982). Orderings for Term-Rewriting Systems. Theoretical Computer Science, 17(3), 279-301.

Type

Journal article

Intellectual base

Primary research

Year

1982

Volume

17

Issue

3

Pages

279-301

ISSN

0304-3975

DOI

10.1016/0304-3975(82)90026-3

DOI registrant

Elsevier

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).

    Supported in partVerified against the work's full text

    Dershowitz defines partial well-founded orderings (multiset and recursive path orderings) for termination, but does not discuss totality yielding well-ordering or structural recursion on data types.

    “Given a partial ordering :, on a set S, it may be extended to a partial ordering :* on finite multisets of elements of S”

    Read by an automated reader; not a human review. How support was checked

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

Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.

Does it back the claim? Read against the text for 1 of 2 citations: 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.

Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.

See how references were verified.

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