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

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

Problem #8

Originator: Aart Middeldorp
Date: April 1991

Summary: Is the decidability of strong sequentiality for orthogonal term rewriting systems NP-complete?

Is the decidability of strong sequentiality for orthogonal term rewriting systems NP-complete? See [HL91, KM91].

References

[HL79]

Gérard Huet and Jean-Jacques Lévy. Call by need computations in non-ambiguous linear term rewriting systems. Rapport Laboria 359, Institut National de Recherche en Informatique et en Automatique, Le Chesnay, France, August 1979.

[HL91]

Gérard Huet and Jean-Jacques Lévy. Computations in orthogonal rewriting systems, I and II. In Jean-Louis Lassez and Gordon Plotkin, editors, Computational Logic: Essays in Honor of Alan Robinson, pages 395–443. The MIT Press, Cambridge, MA, 1991. This is a revision of [HL79].

[KM91]

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

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

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