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

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

Problem #9

Originator: Aart Middeldorp
Date: April 1991

Summary: Is left-sequentiality a decidable property of orthogonal systems?

Thatte [Tha87] showed that an orthogonal constructor-based rewrite system is left-sequential if and only if it is strongly sequential. Does this equivalence extend to the whole class of orthogonal term-rewriting systems? If not, is left-sequentiality a decidable property of orthogonal systems? See also [KM91].

References

[KM91]

Jan Willem Klop and Aart Middeldorp. Sequentiality in orthogonal term rewriting systems. Journal of Symbolic Computation, 12:161–195, 1991.

[Tha87]

S. Thatte. A refinement of strong sequentiality for term rewriting with constructors. Information and Computation, 72:46–65, 1987.

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

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