This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.
$\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 2\;\wedge\;u\to_R^*v\to_R^*w\;\wedge\;u\neq v\neq w\}$
Reduce the word reachability problem restricted to the alphabet $\{a,b\}$ to
the set of tuples $\langle u,v,w,R\rangle$ where $u,v,w$ are words, $R$ is a
word rewrite system, the used alphabet has at most $2$ symbols, $u$ reaches $v$
using $R$, $v$ reaches $w$ using $R$, $u$ is different from $v$, and $v$ is
different from $w$, in order to prove that such set is undecidable (not
recursive).
Authors: Guillem Godoy
/
Documentation: