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 4\;\wedge\;u\to_R^*v\to_R^*w\;\wedge\;u\neq v\neq w\}$ (morphism not allowed in the reduction)
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
$4$ 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).
The use of morphism is not allowed in the description of this reduction.
Authors: Guillem Godoy
/
Documentation: