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\;u\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
$u$ reaches
$v$
using
$R$ with at least one step, 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: