# Computational complexity of the word problem for semi-Thue systems with certain restrictions

The word problem (from wikipedia).

Given a semi-Thue system T: = (Σ,R) and two words , can u be transformed into v by applying rules from R?

This problem is undecidable, but with a certain restriction, it is decidable.

The Restriction: All the rules in R are of the form A->B where A and B are string of the same length.

What is the computational complexity of this problem?

The problem is at least NP-hard. Indeed, it is at least PSPACE-hard.

The reason the original semi-Thue rewrite system is undecidable is that it reduces the halting problem. Given any Turing machine program $e$ and input $x$, one sets up a rewrite system acting on strings that code information about the Turing computation. Thus, the string should display the contents of the tape, the head position within that information and the current state. The rewrite rules correspond to the update procedure of the program $e$ as the computation proceeds. For the most part, these rewrite rules are length-preserving. If the head is in the middle of the currently stored information of the tape, then it moves one way or the other and the tape is updated, and changing this information does not make the representing string any longer. One exception to this, however, is when the head moves off to either end of the represented tape, in effect using more tape for the first time. In this case, the rewrite transformation rules will have in effect to add an extra symbol to represent that new cell that was just encountered. (Finally, the rewrite rules should include some rules that propagate a halting configuration to some informative output string.)

My main observation is now that, therefore, if we know in advance how much space the computation will require, then we can set up the rewrite rules with length-preserving transformations, so that the exceptional case is not needed.

Specifically, suppose that we have an NP algorithm $e$ with known polynomial bound $p$ and input $x$. Thus, $x$ is accepted if and only if there is some $y$ such that $e$ accepts $(x,y)$, and this computation will in any event complete in time $p(|x|)$. Let $u$ be a string representing an initial Turing machine set up with $x$ on the input tape, $0$'s on the work tape and wildcard symbols on the witness tape, where the length of these tapes as represented in $u$ is $p(|x|)$. Now, produce a semi-Thue rewrite system whose rules first of all allow the wildcard symbols to assume any specific values (this will produce a potential witness $y$ on the witness tape). Next, the system also has rewrite rules as above carrying out the instructions of program $e$ in the manner of the paragraph above. These are very local length-preserving rewrite transformation rules that correspond to the operation of $e$, and each rule has to look at only a small portion of the represented information, since the Turing machine operation is completely local. Since we know that the computation will end before the ends of the string are met, we do not need the extra non-length-preserving rules that add extra symbols corresponding to the head moving off the represented portion of the tape, since we know this will not happen. Finally, add rules that have the effect that if the accept state is realized, then this information is simply copied to every symbol.

Thus, I claim the original input $x$ is accepted by $e$ (with respect to some unknown $y$) if and only if this semi-Thue rewrite system transforms $u$ to the all accept string. Thus, I have reduced the given NP problem to your restricted semi-Thue problem. The reduction is polynomial time, since we can write down the transformation rules I described above in polynomial time from $e$ and $x$. And so your problem is at least NP-hard.

A similar argument works with PSPACE, without needing any wildcards, so it is also PSPACE hard.

It isn't clear to me, however, whether your problem is actually itself in PSPACE, since although the transformed strings themselves don't take much space, we have somehow to keep track of all possible ways to apply the rewrite rules, and this would seem naively to take exponential space. Certainly your problem is in EXPSPACE, since we could make a list of all possible strings of length |u|, and then just check off which ones are accessible from u by iteratively applying the rules until we have computed the closure of u under those rules, and finally checking if v was obtained. (This argument also shows, crudely, that your problem is at worst double exponential time.)

Joel David Hamkins has done most of the work in his answer, but just to wrap it up, the problem is PSPACE complete. As Joel has explained, the given semi-Thue problem can be simulated by a space-bounded, nondeterministic Turing machine, and conversely. So the problem is (nondeterministic) PSPACE complete. But Savitch's theorem says that this is the same as PSPACE complete.

• Thanks, John. But in my argument at the end, I used exponential space, rather than polynomial space. So why is the problem even in PSPACE at all? – Joel David Hamkins Jun 19 '10 at 12:09
• Oh, I see, the answer to my question is Savitch's theorem! Thanks! – Joel David Hamkins Jun 19 '10 at 12:14