This site uses cookies only for the purpose of identifying user sessions.
This is required to properly register actions.

##
Exercise
1_{›}:

$\{\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 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 even (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: