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|\in\dot{2}\text{ (as a set, i.e., not counting repetitions)}\}$
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 even (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).
Authors: Guillem Godoy
/
Documentation: