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

##
Exercise
_{‹}28:

$\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,R\rangle \mid |\Sigma|\leq 3\;\wedge\;u\to_R^+u\}$ (morphism not allowed in the reduction)

Reduce the word reachability problem restricted to the alphabet

$\{a,b\}$ to
the set of tuples

$\langle u,R\rangle$ where

$u$ is a word,

$R$ is a word
rewrite system, the used alphabet has at most

$3$ symbols, and

$u$ reaches

$u$
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: