Exercises on reductions of word reachability

  1. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R∗v  ∧  ∣R∣∈2˙ (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)
  2. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R∗v  ∧  ∣R∣∉2˙ (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|\notin\dot{2}\text{ (as a list, i.e., counting repetitions)}\} (morphism not allowed in the reduction)
  3. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣u→R∗v  ∧  ∣R∣∈2˙ (as a set, i.e., not 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 u\to_R^*v\;\wedge\;|R|\in\dot{2}\text{ (as a set, i.e., not counting repetitions)}\} (morphism not allowed in the reduction)
  4. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣u→R∗v  ∧  ∣R∣∉2˙ (as a set, i.e., not 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 u\to_R^*v\;\wedge\;|R|\notin\dot{2}\text{ (as a set, i.e., not counting repetitions)}\} (morphism not allowed in the reduction)
  5. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R∗v  ∧  ∣R∣∈2˙ (as a set, i.e., not 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 3\;\wedge\;u\to_R^*v\;\wedge\;|R|\in\dot{2}\text{ (as a set, i.e., not counting repetitions)}\} (morphism not allowed in the reduction)
  6. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R∗v  ∧  ∣R∣∉2˙ (as a set, i.e., not 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 3\;\wedge\;u\to_R^*v\;\wedge\;|R|\notin\dot{2}\text{ (as a set, i.e., not counting repetitions)}\} (morphism not allowed in the reduction)
  7. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R∗v  ∧  ∣R∣∈2˙ (as a set, i.e., not 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 set, i.e., not counting repetitions)}\}
  8. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R∗v  ∧  ∣R∣∉2˙ (as a set, i.e., not 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|\notin\dot{2}\text{ (as a set, i.e., not counting repetitions)}\}
  9. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R∗v with an even number of steps}\{\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\text{ with an even number of steps}\} (morphism not allowed in the reduction)
  10. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R∗v with an odd number of steps}\{\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\text{ with an odd number of steps}\} (morphism not allowed in the reduction)
  11. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣u→R∗v with an even number of steps but not with an odd number of steps}\{\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\text{ with an even number of steps but not with an odd number of steps}\} (morphism not allowed in the reduction)
  12. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣u→R∗v with an odd number of steps but not with an even number of steps}\{\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\text{ with an odd number of steps but not with an even number of steps}\} (morphism not allowed in the reduction)
  13. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R∗v with an even number of steps but not with an odd number of steps}\{\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 3\;\wedge\;u\to_R^*v\text{ with an even number of steps but not with an odd number of steps}\} (morphism not allowed in the reduction)
  14. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R∗v with an odd number of steps but not with an even number of steps}\{\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 3\;\wedge\;u\to_R^*v\text{ with an odd number of steps but not with an even number of steps}\} (morphism not allowed in the reduction)
  15. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R+v}\{\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 3\;\wedge\;u\to_R^+v\} (morphism not allowed in the reduction)
  16. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤2  ∧  u→R+v}\{\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\} (morphism not allowed in the reduction)
  17. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,w,R⟩∣∣Σ∣≤3  ∧  u→R∗v→R∗w}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 3\;\wedge\;u\to_R^*v\to_R^*w\} (morphism not allowed in the reduction)
  18. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,w,R⟩∣∣Σ∣≤2  ∧  u→R∗v→R∗w}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 2\;\wedge\;u\to_R^*v\to_R^*w\} (morphism not allowed in the reduction)
  19. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,w,R⟩∣∣Σ∣≤4  ∧  u→R∗v→R∗w  ∧  u≠v≠w}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 4\;\wedge\;u\to_R^*v\to_R^*w\;\wedge\;u\neq v\neq w\} (morphism not allowed in the reduction)
  20. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,w,R⟩∣∣Σ∣≤3  ∧  u→R∗v→R∗w  ∧  u≠v≠w}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 3\;\wedge\;u\to_R^*v\to_R^*w\;\wedge\;u\neq v\neq w\} (morphism not allowed in the reduction)
  21. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,w,R⟩∣∣Σ∣≤2  ∧  u→R∗v→R∗w  ∧  u≠v≠w}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,v,w,R\rangle \mid |\Sigma|\leq 2\;\wedge\;u\to_R^*v\to_R^*w\;\wedge\;u\neq v\neq w\}
  22. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R∗vv}\{\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 3\;\wedge\;u\to_R^*vv\} (morphism not allowed in the reduction)
  23. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  uu→R∗v}\{\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 3\;\wedge\;uu\to_R^*v\} (morphism not allowed in the reduction)
  24. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤4  ∧  uu→R∗vv}\{\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 4\;\wedge\;uu\to_R^*vv\} (morphism not allowed in the reduction)
  25. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  uu→R∗vv}\{\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 3\;\wedge\;uu\to_R^*vv\} (morphism not allowed in the reduction)
  26. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,v,R⟩∣∣Σ∣≤3  ∧  u→R∗v  ∧  v→R∗u}\{\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 3\;\wedge\;u\to_R^*v\;\wedge\;v\to_R^*u\} (morphism not allowed in the reduction)
  27. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,R⟩∣∣Σ∣≤4  ∧  u→R+u}\{\langle u,v,R\rangle\mid\Sigma=\{a,b\}\;\wedge\;u\to_R^*v\}\quad\leq\quad\{\langle u,R\rangle \mid |\Sigma|\leq 4\;\wedge\;u\to_R^+u\} (morphism not allowed in the reduction)
  28. {⟨u,v,R⟩∣Σ={a,b}  ∧  u→R∗v}≤{⟨u,R⟩∣∣Σ∣≤3  ∧  u→R+u}\{\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)