Exercise 1:

{u,v,RΣ={a,b}    uRv}{u,v,RΣ2    uRv    R2˙ (as a list, i.e., counting repetitions)}\{\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}\{a,b\} to the set of tuples u,v,R\langle u,v,R\rangle where u,vu,v are words, RR is a word rewrite system, the used alphabet has at most 22 symbols, uu reaches vv using RR, and the number of rules of RR is even (by considering RR as a list, i.e., each different rule is counted as many times as it occurs in RR), 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:
To be able to submit you need to either log in, register, or become a guest.