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)) SCC Processor: #sccs: 1 #rules: 6 #arcs: 30/144 DPs: b#(d(b(x1))) -> a#(d(x1)) a#(c(x1)) -> b#(b(c(d(x1)))) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> b#(x1) a#(d(x1)) -> 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)))) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {4} transitions: f70() -> 5* c0(6) -> 7* c0(48) -> 49* b0(7) -> 8* b{#,0}(8) -> 4* d0(47) -> 48* d0(5) -> 6* d0(46) -> 47* 47 -> 48* 46 -> 47* 6 -> 46* 49 -> 8* 5 -> 6* problem: DPs: b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> b#(x1) a#(d(x1)) -> 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)))) Restore Modifier: DPs: b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> b#(x1) a#(d(x1)) -> 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)))) EDG Processor: DPs: b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> b#(x1) a#(d(x1)) -> 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)))) graph: 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)) -> b#(x1) a#(d(x1)) -> b#(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)) KBO Processor: argument filtering: pi(d) = [0] pi(a) = 0 pi(b) = 0 pi(c) = [] pi(a#) = 0 pi(b#) = 0 usable rules: 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)))) weight function: w0 = 1 w(b#) = w(a#) = w(c) = w(b) = w(a) = w(d) = 1 precedence: a# > c > d > b > a > b# problem: DPs: b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> 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)))) Restore Modifier: DPs: b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> 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)))) EDG Processor: DPs: b#(d(b(x1))) -> a#(d(x1)) a#(x1) -> b#(b(b(x1))) a#(x1) -> b#(b(x1)) a#(x1) -> 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)))) graph: 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))) 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)) Matrix Interpretation Processor: dim=1 interpretation: [a#](x0) = 2x0 + 16, [a](x0) = x0 + 16, [c](x0) = 8, [b#](x0) = 2x0, [d](x0) = 4x0, [b](x0) = x0 + 4 orientation: b#(d(b(x1))) = 8x1 + 32 >= 8x1 + 16 = a#(d(x1)) a#(x1) = 2x1 + 16 >= 2x1 + 16 = b#(b(b(x1))) a#(x1) = 2x1 + 16 >= 2x1 + 8 = b#(b(x1)) a#(x1) = 2x1 + 16 >= 2x1 = b#(x1) a(d(x1)) = 4x1 + 16 >= 4x1 + 16 = d(b(x1)) a(x1) = x1 + 16 >= x1 + 12 = b(b(b(x1))) d(x1) = 4x1 >= x1 = x1 a(x1) = x1 + 16 >= x1 = x1 b(d(b(x1))) = 4x1 + 20 >= 4x1 + 16 = a(d(x1)) b(c(x1)) = 12 >= 8 = c(d(d(x1))) a(c(x1)) = 24 >= 16 = b(b(c(d(x1)))) problem: DPs: 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)))) Restore Modifier: DPs: 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)))) EDG Processor: DPs: 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)))) graph: SCC Processor: #sccs: 0 #rules: 0 #arcs: 0/1