[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #6 (Solved !)

Originator: Aart Middeldorp [Mid89]
Date: April 1991

Summary: Is unicity of normal forms with respect to reduction a modular property of left-linear term-rewriting systems?

If R and S are two term-rewriting systems with disjoint vocabularies, such that for each of R and S any two convertible normal forms must be identical, then their union R ∪ S also enjoys this property [Mid89]. Accordingly, we say that unicity of normal forms (UN) is a “modular” property of term-rewriting systems. “Unicity of normal forms with respect to reduction” (UN^→) is the weaker property that any two normal forms of the same term must be identical. For non-left-linear systems, this property is not modular. The question remains: Is UN^→ a modular property of left-linear term-rewriting systems?

Remark

A positive solution is given in [Mar94].

References

[Mar94]

M. Marchiori. Modularity of UN^→ for left-linear term rewriting systems. Technical report, CWI, Amsterdam, 1994.

[Mid89]

Aart Middeldorp. Modular aspects of properties of term rewriting systems related to normal forms. In Nachum Dershowitz, editor, Rewriting Techniques and Applications, volume 355 of Lecture Notes in Computer Science, pages 263–277, Chapel Hill, NC, USA, April 1989. Springer-Verlag.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next]

[Postscript] [PDF] [BibTeX Source] [LaTeX Source]