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

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

Problem #11 (Solved !)

Originator: Aart Middeldorp [Mid90]
Date: April 1991

Summary: Is unicity of normal forms a modular property of standard conditional systems?

A conditional term-rewriting system has rules of the form p ⇒ l → r, which are only applied to instances of l for which the condition p holds. A “standard” (or “join”) conditional system is one in which the condition p is a conjunction of conditions u ↓ v, meaning that u and v have a common reduct (are “joinable”). Is unicity of normal forms (UN) a modular property of standard conditional systems? See also [Mid93].

Remark

This has been answered in the negative by giving a counterexample [Sch02].

References

[Mid90]

Aart Middeldorp. Modular Properties of Term Rewriting Systems. PhD thesis, Vrije Universiteit, Amsterdam, The Netherlands, 1990.

[Mid93]

Aart Middeldorp. Modular properties of conditional term rewriting systems. Information and Computation, 104(1):110–158, 1993.

[Sch02]

Kai Scheffermann. A countererexample to the modularity of unicity of normal forms for join conditional term rewriting systems. Preprint pr309, Universität Hannover, Institut für Mathematik, April 2002.

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

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