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 u\to_R^*v\;\wedge\;|R|\notin\dot{2}\text{ (as a set, i.e., not 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,
$u$ reaches
$v$ using
$R$, and the number of rules of
$R$ is
odd (by considering
$R$ as a set, i.e., each different rule is counted only
once), 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: