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 2\;\wedge\;u\to_R^*v\;\wedge\;|R|\notin\dot{2}\text{ (as a list, i.e., counting repetitions)}\}$ (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
$2$ symbols,
$u$ reaches
$v$
using
$R$, and the number of rules of
$R$ is odd (by considering
$R$ as a list,
i.e., each different rule is counted as many times as it occurs in
$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: