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

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

Problem #14

Originator: Jean-Pierre Jouannaud
Date: April 1991

Summary: Which conditional rewrite systems are subcommutative?

Parallel rewriting with orthogonal term-rewriting systems is “subcommutative” (a “strong” form of confluence). Under which interesting syntactic restrictions do conditional rewrite systems enjoy the same property? It is known that orthogonal “normal” conditional rewriting systems (with conditions u →^! v, where v is a ground normal form) are confluent, while “standard” (join) ones are not [BK86].

References

[BK86]

J. A. Bergstra and Jan Willem Klop. Conditional rewrite rules: Confluency and termination. Journal of Computer and System Sciences, 32(3):323–362, 1986.

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

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