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

  • 1
    $\begingroup$ "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. $\endgroup$ – Joel Reyes Noche Feb 24 '14 at 1:43
  • $\begingroup$ nice, thanks for the example $\endgroup$ – cats Feb 24 '14 at 1:49
  • $\begingroup$ 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. $\endgroup$ – Joel Reyes Noche Feb 24 '14 at 14:49

You may look at the following references:

  1. The RTA list of open problems.
  2. The survey paper on rewriting systems Open. Closed. Open. by Nachum Dershowitz, in particular Section 3 "One-Rule Termination".
  3. The article "Calcul de longueurs de chaînes de réécriture dans le monoide libre" by Y. Metivier, Theoretical Computer Science 35 (1985) 71-87.

The following results are extracted from these references.

(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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.