# Iteratively Replacing Substrings

This problem came up while I was helping someone. Informally, we have a string of characters and a "rule" which replaces a specific string with another one, and we repeat this rule until we can no longer do so (obviously if you replace a string with another which contains the first as a substring, this won't terminate).

The question is, under what conditions will this terminate, and is there a general bound on the length of the resulting string?

Specifically, let's try this with two characters, $a$ and $b,$ and let's assume there's only one rule. As an example, consider the rule $ab \mapsto bba.$ It isn't hard to see for a string of length $n,$ the maximum length of the resulting string is $2^{n-1} + n -1.$ The point here is that this rule essentially moves all $a$'s to the right (and it doesn't change the number of $a$'s), so the most it can do is double the number of $b$'s for each $a.$ A string which achieves this upper bound is $aaa\ldots ab.$

Another question is, why is it true that the order of replacement doesn't matter (this shouldn't be too hard, assuming it terminates... I think)?

• "why is it true that the order of replacement doesn't matter" Consider the rule $aa\to b$ and the string $aaaa$. If we first apply the rule to the second and third $a$'s, we get $aba$ and we stop. If we first apply the rule to the first two $a$'s, we get $baa$; applying the rule again leads to $bb$. The order of replacement mattered. – Joel Reyes Noche Feb 24 '14 at 1:43
• nice, thanks for the example – cats Feb 24 '14 at 1:49
• Note that if your rule replaces a specific letter with a string, then there would be no ambiguity in which replacement should be done first. That is, if your rule is a morphism (see here for a definition) then things would be much easier. – Joel Reyes Noche Feb 24 '14 at 14:49

(1) Your first question (whether a single-rule string rewriting system $u \to v$ is terminating) appears to be a long-standing open problem.
(2) There are some known results for your second question whan $|u| = |v|$. In this case the upper bound is $n^{|u|}$, where $n$ denotes the length of the initiating string. If the alphabet has only two letters, then the upper bound is $n^2/4$ and this bound is tight.