YES Problem: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) Proof: DP Processor: DPs: a#(d(x1)) -> b#(x1) a#(d(x1)) -> d#(b(x1)) a#(x1) -> b#(x1) a#(x1) -> b#(b(x1)) a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) b#(c(x1)) -> d#(x1) b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(c(d(x1))) a#(c(x1)) -> b#(b(c(d(x1)))) TRS: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) TDG Processor: DPs: a#(d(x1)) -> b#(x1) a#(d(x1)) -> d#(b(x1)) a#(x1) -> b#(x1) a#(x1) -> b#(b(x1)) a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) b#(c(x1)) -> d#(x1) b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(c(d(x1))) a#(c(x1)) -> b#(b(c(d(x1)))) TRS: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) graph: b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> b#(b(c(d(x1)))) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> b#(c(d(x1))) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(b(x1)) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(d(x1)) -> d#(b(x1)) b#(d(b(x1))) -> a#(d(x1)) -> a#(d(x1)) -> b#(x1) a#(c(x1)) -> b#(c(d(x1))) -> b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> b#(c(d(x1))) -> b#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(c(d(x1))) -> b#(d(b(x1))) -> a#(d(x1)) a#(c(x1)) -> b#(c(d(x1))) -> b#(d(b(x1))) -> d#(x1) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(d(b(x1))) -> a#(d(x1)) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(d(b(x1))) -> d#(x1) a#(d(x1)) -> b#(x1) -> b#(c(x1)) -> d#(d(x1)) a#(d(x1)) -> b#(x1) -> b#(c(x1)) -> d#(x1) a#(d(x1)) -> b#(x1) -> b#(d(b(x1))) -> a#(d(x1)) a#(d(x1)) -> b#(x1) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(b(b(x1))) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(b(b(x1))) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(b(b(x1))) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(b(x1)) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(b(x1)) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(b(x1)) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(x1)) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(x1) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(x1) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(x1) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(x1) -> b#(d(b(x1))) -> d#(x1) EDG Processor: DPs: a#(d(x1)) -> b#(x1) a#(d(x1)) -> d#(b(x1)) a#(x1) -> b#(x1) a#(x1) -> b#(b(x1)) a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) b#(c(x1)) -> d#(x1) b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(c(d(x1))) a#(c(x1)) -> b#(b(c(d(x1)))) TRS: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) graph: b#(d(b(x1))) -> a#(d(x1)) -> a#(d(x1)) -> b#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(d(x1)) -> d#(b(x1)) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(b(x1)) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> b#(c(d(x1))) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> b#(b(c(d(x1)))) a#(c(x1)) -> b#(c(d(x1))) -> b#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(c(d(x1))) -> b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(d(b(x1))) -> d#(x1) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(d(b(x1))) -> a#(d(x1)) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(c(x1)) -> d#(d(x1)) a#(d(x1)) -> b#(x1) -> b#(d(b(x1))) -> d#(x1) a#(d(x1)) -> b#(x1) -> b#(d(b(x1))) -> a#(d(x1)) a#(d(x1)) -> b#(x1) -> b#(c(x1)) -> d#(x1) a#(d(x1)) -> b#(x1) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(b(b(x1))) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(b(b(x1))) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(b(b(x1))) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(b(x1)) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(b(x1)) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(x1)) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(b(x1)) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(x1) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(x1) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(x1) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(x1) -> b#(c(x1)) -> d#(d(x1)) CDG Processor: DPs: a#(d(x1)) -> b#(x1) a#(d(x1)) -> d#(b(x1)) a#(x1) -> b#(x1) a#(x1) -> b#(b(x1)) a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) b#(c(x1)) -> d#(x1) b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(c(d(x1))) a#(c(x1)) -> b#(b(c(d(x1)))) TRS: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) graph: b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> b#(b(c(d(x1)))) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> b#(c(d(x1))) b#(d(b(x1))) -> a#(d(x1)) -> a#(c(x1)) -> d#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(b(b(x1))) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(b(x1)) b#(d(b(x1))) -> a#(d(x1)) -> a#(x1) -> b#(x1) b#(d(b(x1))) -> a#(d(x1)) -> a#(d(x1)) -> d#(b(x1)) b#(d(b(x1))) -> a#(d(x1)) -> a#(d(x1)) -> b#(x1) a#(c(x1)) -> b#(c(d(x1))) -> b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> b#(c(d(x1))) -> b#(c(x1)) -> d#(x1) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(c(x1)) -> d#(d(x1)) a#(c(x1)) -> b#(b(c(d(x1)))) -> b#(c(x1)) -> d#(x1) a#(d(x1)) -> b#(x1) -> b#(c(x1)) -> d#(d(x1)) a#(d(x1)) -> b#(x1) -> b#(c(x1)) -> d#(x1) a#(d(x1)) -> b#(x1) -> b#(d(b(x1))) -> a#(d(x1)) a#(d(x1)) -> b#(x1) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(b(b(x1))) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(b(b(x1))) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(b(b(x1))) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(b(x1)) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(b(x1)) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(b(x1)) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(x1)) -> b#(d(b(x1))) -> d#(x1) a#(x1) -> b#(x1) -> b#(c(x1)) -> d#(d(x1)) a#(x1) -> b#(x1) -> b#(c(x1)) -> d#(x1) a#(x1) -> b#(x1) -> b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(x1) -> b#(d(b(x1))) -> d#(x1) SCC Processor: #sccs: 1 #rules: 5 #arcs: 28/144 DPs: b#(d(b(x1))) -> a#(d(x1)) a#(d(x1)) -> b#(x1) a#(x1) -> b#(x1) a#(x1) -> b#(b(x1)) a#(x1) -> b#(b(b(x1))) TRS: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) Matrix Interpretation Processor: dim=1 interpretation: [b#](x0) = x0 + 1, [a#](x0) = x0 + 4, [c](x0) = 24, [b](x0) = x0 + 1, [a](x0) = x0 + 4, [d](x0) = 4x0 orientation: b#(d(b(x1))) = 4x1 + 5 >= 4x1 + 4 = a#(d(x1)) a#(d(x1)) = 4x1 + 4 >= x1 + 1 = b#(x1) a#(x1) = x1 + 4 >= x1 + 1 = b#(x1) a#(x1) = x1 + 4 >= x1 + 2 = b#(b(x1)) a#(x1) = x1 + 4 >= x1 + 3 = b#(b(b(x1))) a(d(x1)) = 4x1 + 4 >= 4x1 + 4 = d(b(x1)) a(x1) = x1 + 4 >= x1 + 3 = b(b(b(x1))) d(x1) = 4x1 >= x1 = x1 a(x1) = x1 + 4 >= x1 = x1 b(d(b(x1))) = 4x1 + 5 >= 4x1 + 4 = a(d(x1)) b(c(x1)) = 25 >= 24 = c(d(d(x1))) a(c(x1)) = 28 >= 26 = b(b(c(d(x1)))) problem: DPs: TRS: a(d(x1)) -> d(b(x1)) a(x1) -> b(b(b(x1))) d(x1) -> x1 a(x1) -> x1 b(d(b(x1))) -> a(d(x1)) b(c(x1)) -> c(d(d(x1))) a(c(x1)) -> b(b(c(d(x1)))) Qed