[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]

Problem #20 (Solved !)

Originator: Yves Métivier [Mét85]
Date: April 1991

Summary: What is the best bound on the length of a derivation for a one-rule length-preserving string-rewriting system?

What is the best bound on the length of a derivation for a one-rule length-preserving string-rewriting (semi-Thue) system? Is it O(n2) (n is the size of the initial term) as conjectured in [Mét85], or O(nk) (k is the size of the rule) as proved there.

Remark

The upper bound is n2/4 where n denotes the length of the initiating string [Ber94]. The bound is reached by the derivation from bn/2 an/2 for the string rewriting system {ba → ab}.

More about the history of this problem in the context of the question of one-rule termination can be found in [Der05].

References

[Ber94]
A. Bertrand. Sur une conjecture d’Yves Métivier. Theoretical Computer Science, 123(1):21–30, 1994.
[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.
[Mét85]
Yves Métivier. Calcul de longueurs de chaînes de réécriture dans le monoïde libre. Theoretical Computer Science, 35(1):71–87, January 1985.

[Submit a comment] [RTALooP home] [Index] [Previous] [Next] [Postscript] [PDF] [BibTeX Source] [LaTeX Source]