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?



Computational complexity of the word problem for semi-Thue systems with certain restrictions
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.)


