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

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

Problem #95

Originator: Hans Zantema
Date: 1999

Summary: Is there a one-rule string rewriting system that is non-terminating but also non-looping?

Is there a one-rule string rewriting system that is non-terminating but also non-looping, that is not allowing a rewrite sequence x →^* uxv ? Motivation and examples of two rule string rewriting systems and a one rule term rewriting system that is non-terminating and non-looping, can be found in [ZG96].

This problem is related to Problem #21 and Problem #87. More about the history of this problem in the context of the question of one-rule termination can be found in [Der05].

References

[Der05]

Nachum Dershowitz. Open. Closed. Open. In Jürgen Giesl, editor, 16th International Conference on Rewriting Techniques, volume 3467 of Lecture Notes in Computer Science, Nara, Japan, April 2005. Springer-Verlag.

[ZG96]

Hans Zantema and Alfons Geser. Non-looping rewriting. Technical Report UU-CS-96-03, Utrecht University, Department of Computer Science, January 1996. Extended version to appear in RAIRO Théor. Inf as "Non-looping string rewriting".

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

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