YES Problem: p(0(x1)) -> 0(s(s(p(x1)))) p(s(x1)) -> x1 p(p(s(x1))) -> p(x1) f(s(x1)) -> g(s(x1)) g(x1) -> i(s(half(x1))) i(x1) -> f(p(x1)) half(0(x1)) -> 0(s(s(half(x1)))) half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 0(x1) -> x1 rd(0(x1)) -> 0(0(0(0(0(0(rd(x1))))))) Proof: Matrix Interpretation Processor: dim=1 interpretation: [g](x0) = x0, [p](x0) = x0, [f](x0) = x0, [half](x0) = x0, [0](x0) = x0 + 3, [rd](x0) = 6x0, [i](x0) = x0, [s](x0) = x0 orientation: p(0(x1)) = x1 + 3 >= x1 + 3 = 0(s(s(p(x1)))) p(s(x1)) = x1 >= x1 = x1 p(p(s(x1))) = x1 >= x1 = p(x1) f(s(x1)) = x1 >= x1 = g(s(x1)) g(x1) = x1 >= x1 = i(s(half(x1))) i(x1) = x1 >= x1 = f(p(x1)) half(0(x1)) = x1 + 3 >= x1 + 3 = 0(s(s(half(x1)))) half(s(s(x1))) = x1 >= x1 = s(half(p(p(s(s(x1)))))) 0(x1) = x1 + 3 >= x1 = x1 rd(0(x1)) = 6x1 + 18 >= 6x1 + 18 = 0(0(0(0(0(0(rd(x1))))))) problem: p(0(x1)) -> 0(s(s(p(x1)))) p(s(x1)) -> x1 p(p(s(x1))) -> p(x1) f(s(x1)) -> g(s(x1)) g(x1) -> i(s(half(x1))) i(x1) -> f(p(x1)) half(0(x1)) -> 0(s(s(half(x1)))) half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) rd(0(x1)) -> 0(0(0(0(0(0(rd(x1))))))) Matrix Interpretation Processor: dim=1 interpretation: [g](x0) = 8x0, [p](x0) = x0, [f](x0) = 8x0, [half](x0) = x0, [0](x0) = x0 + 1, [rd](x0) = 7x0 + 1, [i](x0) = 8x0, [s](x0) = x0 orientation: p(0(x1)) = x1 + 1 >= x1 + 1 = 0(s(s(p(x1)))) p(s(x1)) = x1 >= x1 = x1 p(p(s(x1))) = x1 >= x1 = p(x1) f(s(x1)) = 8x1 >= 8x1 = g(s(x1)) g(x1) = 8x1 >= 8x1 = i(s(half(x1))) i(x1) = 8x1 >= 8x1 = f(p(x1)) half(0(x1)) = x1 + 1 >= x1 + 1 = 0(s(s(half(x1)))) half(s(s(x1))) = x1 >= x1 = s(half(p(p(s(s(x1)))))) rd(0(x1)) = 7x1 + 8 >= 7x1 + 7 = 0(0(0(0(0(0(rd(x1))))))) problem: p(0(x1)) -> 0(s(s(p(x1)))) p(s(x1)) -> x1 p(p(s(x1))) -> p(x1) f(s(x1)) -> g(s(x1)) g(x1) -> i(s(half(x1))) i(x1) -> f(p(x1)) half(0(x1)) -> 0(s(s(half(x1)))) half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) String Reversal Processor: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) DP Processor: DPs: 0#(p(x1)) -> 0#(x1) 0#(p(x1)) -> s#(0(x1)) 0#(p(x1)) -> s#(s(0(x1))) s#(f(x1)) -> g#(x1) s#(f(x1)) -> s#(g(x1)) g#(x1) -> i#(x1) g#(x1) -> s#(i(x1)) 0#(half(x1)) -> 0#(x1) 0#(half(x1)) -> s#(0(x1)) 0#(half(x1)) -> s#(s(0(x1))) s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) TDG Processor: DPs: 0#(p(x1)) -> 0#(x1) 0#(p(x1)) -> s#(0(x1)) 0#(p(x1)) -> s#(s(0(x1))) s#(f(x1)) -> g#(x1) s#(f(x1)) -> s#(g(x1)) g#(x1) -> i#(x1) g#(x1) -> s#(i(x1)) 0#(half(x1)) -> 0#(x1) 0#(half(x1)) -> s#(0(x1)) 0#(half(x1)) -> s#(s(0(x1))) s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) graph: g#(x1) -> s#(i(x1)) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) g#(x1) -> s#(i(x1)) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) g#(x1) -> s#(i(x1)) -> s#(s(half(x1))) -> s#(x1) g#(x1) -> s#(i(x1)) -> s#(f(x1)) -> s#(g(x1)) g#(x1) -> s#(i(x1)) -> s#(f(x1)) -> g#(x1) s#(f(x1)) -> g#(x1) -> g#(x1) -> s#(i(x1)) s#(f(x1)) -> g#(x1) -> g#(x1) -> i#(x1) s#(f(x1)) -> s#(g(x1)) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(f(x1)) -> s#(g(x1)) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(f(x1)) -> s#(g(x1)) -> s#(s(half(x1))) -> s#(x1) s#(f(x1)) -> s#(g(x1)) -> s#(f(x1)) -> s#(g(x1)) s#(f(x1)) -> s#(g(x1)) -> s#(f(x1)) -> g#(x1) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(f(x1)) -> s#(g(x1)) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(f(x1)) -> g#(x1) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) -> s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) -> s#(f(x1)) -> s#(g(x1)) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) -> s#(f(x1)) -> g#(x1) s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(x1) -> s#(f(x1)) -> s#(g(x1)) s#(s(half(x1))) -> s#(x1) -> s#(f(x1)) -> g#(x1) 0#(half(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(half(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) 0#(half(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(x1) 0#(half(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> s#(g(x1)) 0#(half(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> g#(x1) 0#(half(x1)) -> s#(0(x1)) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(half(x1)) -> s#(0(x1)) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) 0#(half(x1)) -> s#(0(x1)) -> s#(s(half(x1))) -> s#(x1) 0#(half(x1)) -> s#(0(x1)) -> s#(f(x1)) -> s#(g(x1)) 0#(half(x1)) -> s#(0(x1)) -> s#(f(x1)) -> g#(x1) 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(s(0(x1))) 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(0(x1)) 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> 0#(x1) 0#(half(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(s(0(x1))) 0#(half(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(0(x1)) 0#(half(x1)) -> 0#(x1) -> 0#(p(x1)) -> 0#(x1) 0#(p(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(p(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) 0#(p(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(x1) 0#(p(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> s#(g(x1)) 0#(p(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> g#(x1) 0#(p(x1)) -> s#(0(x1)) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(p(x1)) -> s#(0(x1)) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) 0#(p(x1)) -> s#(0(x1)) -> s#(s(half(x1))) -> s#(x1) 0#(p(x1)) -> s#(0(x1)) -> s#(f(x1)) -> s#(g(x1)) 0#(p(x1)) -> s#(0(x1)) -> s#(f(x1)) -> g#(x1) 0#(p(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(s(0(x1))) 0#(p(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(0(x1)) 0#(p(x1)) -> 0#(x1) -> 0#(half(x1)) -> 0#(x1) 0#(p(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(s(0(x1))) 0#(p(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(0(x1)) 0#(p(x1)) -> 0#(x1) -> 0#(p(x1)) -> 0#(x1) EDG Processor: DPs: 0#(p(x1)) -> 0#(x1) 0#(p(x1)) -> s#(0(x1)) 0#(p(x1)) -> s#(s(0(x1))) s#(f(x1)) -> g#(x1) s#(f(x1)) -> s#(g(x1)) g#(x1) -> i#(x1) g#(x1) -> s#(i(x1)) 0#(half(x1)) -> 0#(x1) 0#(half(x1)) -> s#(0(x1)) 0#(half(x1)) -> s#(s(0(x1))) s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) graph: s#(f(x1)) -> g#(x1) -> g#(x1) -> i#(x1) s#(f(x1)) -> g#(x1) -> g#(x1) -> s#(i(x1)) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(f(x1)) -> g#(x1) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(f(x1)) -> s#(g(x1)) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(s(half(x1))) -> s#(x1) -> s#(f(x1)) -> g#(x1) s#(s(half(x1))) -> s#(x1) -> s#(f(x1)) -> s#(g(x1)) s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(x1) s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(half(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> g#(x1) 0#(half(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> s#(g(x1)) 0#(half(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(x1) 0#(half(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) 0#(half(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(half(x1)) -> 0#(x1) -> 0#(p(x1)) -> 0#(x1) 0#(half(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(0(x1)) 0#(half(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(s(0(x1))) 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> 0#(x1) 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(0(x1)) 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(s(0(x1))) 0#(p(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> g#(x1) 0#(p(x1)) -> s#(s(0(x1))) -> s#(f(x1)) -> s#(g(x1)) 0#(p(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(x1) 0#(p(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(p(p(half(s(x1))))) 0#(p(x1)) -> s#(s(0(x1))) -> s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) 0#(p(x1)) -> 0#(x1) -> 0#(p(x1)) -> 0#(x1) 0#(p(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(0(x1)) 0#(p(x1)) -> 0#(x1) -> 0#(p(x1)) -> s#(s(0(x1))) 0#(p(x1)) -> 0#(x1) -> 0#(half(x1)) -> 0#(x1) 0#(p(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(0(x1)) 0#(p(x1)) -> 0#(x1) -> 0#(half(x1)) -> s#(s(0(x1))) SCC Processor: #sccs: 2 #rules: 4 #arcs: 34/169 DPs: 0#(half(x1)) -> 0#(x1) 0#(p(x1)) -> 0#(x1) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) Usable Rule Processor: DPs: 0#(half(x1)) -> 0#(x1) 0#(p(x1)) -> 0#(x1) TRS: Arctic Interpretation Processor: dimension: 1 usable rules: interpretation: [0#](x0) = x0, [p](x0) = 1x0 + 13, [half](x0) = x0 + 4 orientation: 0#(half(x1)) = x1 + 4 >= x1 = 0#(x1) 0#(p(x1)) = 1x1 + 13 >= x1 = 0#(x1) problem: DPs: 0#(half(x1)) -> 0#(x1) TRS: Restore Modifier: DPs: 0#(half(x1)) -> 0#(x1) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) EDG Processor: DPs: 0#(half(x1)) -> 0#(x1) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) graph: 0#(half(x1)) -> 0#(x1) -> 0#(half(x1)) -> 0#(x1) Usable Rule Processor: DPs: 0#(half(x1)) -> 0#(x1) TRS: Arctic Interpretation Processor: dimension: 4 usable rules: interpretation: [0#](x0) = [0 -& -& -&]x0, [1 0 0 0] [0] [0 0 0 0] [0] [half](x0) = [1 0 0 0]x0 + [0] [0 0 0 0] [0] orientation: 0#(half(x1)) = [1 0 0 0]x1 + [0] >= [0 -& -& -&]x1 = 0#(x1) problem: DPs: TRS: Qed DPs: s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(s(half(x1))) -> s#(x1) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) Usable Rule Processor: DPs: s#(s(half(x1))) -> s#(s(p(p(half(s(x1)))))) s#(s(half(x1))) -> s#(x1) TRS: s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) Bounds Processor: bound: 0 enrichment: match-dp automaton: final states: {1} transitions: f0(35) -> 36* s{#,0}(7) -> 1* p0(4) -> 5* p0(36) -> 37* p0(17) -> 18* p0(5) -> 6* f120() -> 2* half0(26) -> 27* half0(3) -> 4* i0(24) -> 25* g0(21) -> 22* s0(41) -> 42* s0(6) -> 7* s0(25) -> 26* s0(22) -> 23* s0(2) -> 3* 27 -> 22* 24 -> 35* 42 -> 3* 7 -> 41* 4 -> 42,3 2 -> 21,17,3 21 -> 24* 36 -> 26* 37 -> 25* 5 -> 7* 18 -> 3* 23 -> 3* problem: DPs: s#(s(half(x1))) -> s#(x1) TRS: s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) Restore Modifier: DPs: s#(s(half(x1))) -> s#(x1) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) EDG Processor: DPs: s#(s(half(x1))) -> s#(x1) TRS: 0(p(x1)) -> p(s(s(0(x1)))) s(p(x1)) -> x1 s(p(p(x1))) -> p(x1) s(f(x1)) -> s(g(x1)) g(x1) -> half(s(i(x1))) i(x1) -> p(f(x1)) 0(half(x1)) -> half(s(s(0(x1)))) s(s(half(x1))) -> s(s(p(p(half(s(x1)))))) graph: s#(s(half(x1))) -> s#(x1) -> s#(s(half(x1))) -> s#(x1) Usable Rule Processor: DPs: s#(s(half(x1))) -> s#(x1) TRS: Arctic Interpretation Processor: dimension: 1 usable rules: interpretation: [half](x0) = 1x0 + 13, [s#](x0) = x0, [s](x0) = x0 + 0 orientation: s#(s(half(x1))) = 1x1 + 13 >= x1 = s#(x1) problem: DPs: TRS: Qed