Linearity Requirement for Patterns

Bjorn Lisper
Tue, 20 Mar 2001 15:01:50 +0100 (MET)

Michael Hanus:
>Thus, I think that linearity is a natural requirement
>even for logic languages that support laziness.

Yes. Further evidence for this is that non-left-linear term rewriting systems
typically don't have sequential normalizing evaluation strategies. A
normalizing evaluation strategy might thus be very expensive for a rewrite
system with such rules.

Also, many nice results about confluence do not hold if there are
non-left-linear rules.

Björn Lisper