×

Infinitary term rewriting for weakly orthogonal systems: properties and counterexamples. (English) Zbl 1290.68067

Summary: We present some contributions to the theory of infinitary rewriting for weakly orthogonal term rewrite systems, in which critical pairs may occur provided they are trivial.
We show that the infinitary unique normal form property (UN\(^\infty\)) fails by an example of a weakly orthogonal TRS with two collapsing rules. By translating this example, we show that (UN\(^\infty\)) also fails for the infinitary \(\lambda\beta\eta\)-calculus.
As positive results we obtain the following: Infinitary confluence, and hence UN\(^\infty\), holds for weakly orthogonal TRSs that do not contain collapsing rules. To this end we refine the compression lemma. Furthermore, we establish the triangle and diamond properties for infinitary multi-steps (complete developments) in weakly orthogonal TRSs, by refining an earlier cluster-analysis for the finite case.

MSC:

68Q42 Grammars and rewriting systems
03B40 Combinatory logic and lambda calculus