Iterated string replacements from 00: limits, discrepancy bounds and lengths in conjectures of Kimberling

Abstract

In 2017 Kimberling entered in the OEIS the words obtained by iterating string replacements such as 00->0101, 1->010 from the word 00, for 63 such maps, with more than 200 conjectures on the positions a(n) of the letters in the limiting words and on the lengths of the iterates. A string replacement is not a morphism, since the cut points depend on the left context. For 47 of the maps we construct a morphism on labelled parse tokens whose iterates code those of the map, and we prove the correspondence for all n by checking finitely many local conditions. For these maps we settle all 114 conjectures of the form L<m-a(n)/n