I have two questions concerning ground reachability in string and term rewriting systems.
String Rewriting Systems:
Let $\Sigma$ be a finite alphabet.
I have a set of rules $R$ of the form $a_ib_i = c_id_i$ where $a_i,b_i,c_i,d_i$ are symbols in $\Sigma$.
Problem 1: Given strings $u$ and $w$ in $\Sigma^*$ of size $n$ can $u$ be transformed into $w$ by the application of rules in $R$?
Question1: Can Problem 1 be solved in time polynomial in $n$? Note that in this case the problem is trivially decidable since the rules do not increase the size of the strings.
Term Rewriting Systems:
Now I have a ranked alphabet $\Sigma$ with function symbols of arity $0$, $1$ and $2$.
I have a set $R$ of rules of the form (where $x,y,z$ are variables and $f,g,h,k$ are function symbols)
- $f(x,y) = g(y,x)$
- $f(x,g(y,z)) = h(x,k(y,z))$
Problem 2: Given ground terms $u$ and $w$ over $\Sigma$ with $n$ leaves, can $u$ be transformed into $w$ by the application of rules in $R$?
Question 2: Can Problem 2 be solved in time polynomial in $n$? Note that decidability is also trivial here, since the rules do not increase the size of a term.