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)?