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,R\rangle \mid |\Sigma|\leq 3\;\wedge\;uu\to_R^*v\}$ (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,R\rangle$ where
$u,v$ are words,
$R$ is a word
rewrite system, the used alphabet has at most
$3$ symbols, and
$uu$ reaches
$v$
using
$R$, 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: