[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |
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(n^{2}) (n is the size of the initial term) as conjectured in [Mét85], or O(n^{k}) (k is the size of the rule) as proved there.
The upper bound is n^{2}/4 where n denotes the length of the initiating string [Ber94]. The bound is reached by the derivation from b^{n/2} a^{n/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].
[Submit a comment] [RTALooP home] [Index] [Previous] [Next] | [Postscript] [PDF] [BibTeX Source] [LaTeX Source] |