YES Problem: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) f(s(0()),y) -> y id(x) -> f(x,s(0())) Proof: Matrix Interpretation Processor: dim=3 interpretation: [0] [h] = [0] [0], [1 0 0] [1] [id](x0) = [1 1 1]x0 + [0] [0 0 1] [1], [1 0 0] [1 0 0] [g](x0, x1) = [0 0 0]x0 + [0 0 0]x1 [0 0 0] [0 0 0] , [1 0 0] [s](x0) = [0 0 0]x0 [0 0 0] , [1 0 0] [double](x0) = [0 1 1]x0 [0 0 0] , [0] [0] = [0] [0], [1 0 0] [1 0 0] [1] [f](x0, x1) = [0 0 0]x0 + [1 1 1]x1 + [0] [0 0 0] [0 1 1] [1], [1 1 0] [half](x0) = [0 1 0]x0 [1 0 0] , [0] [d] = [0] [0] orientation: [1 0 0] [0] g(x,0()) = [0 0 0]x >= [0] = 0() [0 0 0] [0] [1 0 0] [1 0 0] g(d(),s(x)) = [0 0 0]x >= [0 0 0]x = s(s(g(d(),x))) [0 0 0] [0 0 0] [0] [0] g(h(),s(0())) = [0] >= [0] = 0() [0] [0] [1 0 0] [1 0 0] g(h(),s(s(x))) = [0 0 0]x >= [0 0 0]x = s(g(h(),x)) [0 0 0] [0 0 0] [1 0 0] [1 0 0] double(x) = [0 1 1]x >= [0 0 0]x = g(d(),x) [0 0 0] [0 0 0] [1 1 0] [1 0 0] half(x) = [0 1 0]x >= [0 0 0]x = g(h(),x) [1 0 0] [0 0 0] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1] f(s(x),y) = [0 0 0]x + [1 1 1]y + [0] >= [0 0 0]x + [1 1 1]y + [0] = f(half(s(x)),double(y)) [0 0 0] [0 1 1] [1] [0 0 0] [0 1 1] [1] [1 0 0] [1] f(s(0()),y) = [1 1 1]y + [0] >= y = y [0 1 1] [1] [1 0 0] [1] [1 0 0] [1] id(x) = [1 1 1]x + [0] >= [0 0 0]x + [0] = f(x,s(0())) [0 0 1] [1] [0 0 0] [1] problem: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) id(x) -> f(x,s(0())) Matrix Interpretation Processor: dim=3 interpretation: [0] [h] = [0] [0], [1 0 0] [1] [id](x0) = [0 0 0]x0 + [1] [1 0 1] [1], [1 0 0] [1 0 0] [g](x0, x1) = [0 0 0]x0 + [0 1 1]x1 [0 0 0] [0 0 0] , [1 0 0] [s](x0) = [0 1 1]x0 [0 0 0] , [1 0 0] [0] [double](x0) = [0 1 1]x0 + [0] [1 1 0] [1], [0] [0] = [0] [0], [1 0 0] [1 0 0] [0] [f](x0, x1) = [0 0 0]x0 + [0 0 0]x1 + [1] [0 0 0] [0 0 0] [1], [1 0 0] [0] [half](x0) = [0 1 1]x0 + [0] [0 0 1] [1], [0] [d] = [0] [0] orientation: [1 0 0] [0] g(x,0()) = [0 0 0]x >= [0] = 0() [0 0 0] [0] [1 0 0] [1 0 0] g(d(),s(x)) = [0 1 1]x >= [0 1 1]x = s(s(g(d(),x))) [0 0 0] [0 0 0] [0] [0] g(h(),s(0())) = [0] >= [0] = 0() [0] [0] [1 0 0] [1 0 0] g(h(),s(s(x))) = [0 1 1]x >= [0 1 1]x = s(g(h(),x)) [0 0 0] [0 0 0] [1 0 0] [0] [1 0 0] double(x) = [0 1 1]x + [0] >= [0 1 1]x = g(d(),x) [1 1 0] [1] [0 0 0] [1 0 0] [0] [1 0 0] half(x) = [0 1 1]x + [0] >= [0 1 1]x = g(h(),x) [0 0 1] [1] [0 0 0] [1 0 0] [1 0 0] [0] [1 0 0] [1 0 0] [0] f(s(x),y) = [0 0 0]x + [0 0 0]y + [1] >= [0 0 0]x + [0 0 0]y + [1] = f(half(s(x)),double(y)) [0 0 0] [0 0 0] [1] [0 0 0] [0 0 0] [1] [1 0 0] [1] [1 0 0] [0] id(x) = [0 0 0]x + [1] >= [0 0 0]x + [1] = f(x,s(0())) [1 0 1] [1] [0 0 0] [1] problem: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) DP Processor: DPs: g#(d(),s(x)) -> g#(d(),x) g#(h(),s(s(x))) -> g#(h(),x) double#(x) -> g#(d(),x) half#(x) -> g#(h(),x) f#(s(x),y) -> double#(y) f#(s(x),y) -> half#(s(x)) f#(s(x),y) -> f#(half(s(x)),double(y)) TRS: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) TDG Processor: DPs: g#(d(),s(x)) -> g#(d(),x) g#(h(),s(s(x))) -> g#(h(),x) double#(x) -> g#(d(),x) half#(x) -> g#(h(),x) f#(s(x),y) -> double#(y) f#(s(x),y) -> half#(s(x)) f#(s(x),y) -> f#(half(s(x)),double(y)) TRS: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) graph: f#(s(x),y) -> f#(half(s(x)),double(y)) -> f#(s(x),y) -> f#(half(s(x)),double(y)) f#(s(x),y) -> f#(half(s(x)),double(y)) -> f#(s(x),y) -> half#(s(x)) f#(s(x),y) -> f#(half(s(x)),double(y)) -> f#(s(x),y) -> double#(y) f#(s(x),y) -> half#(s(x)) -> half#(x) -> g#(h(),x) f#(s(x),y) -> double#(y) -> double#(x) -> g#(d(),x) half#(x) -> g#(h(),x) -> g#(h(),s(s(x))) -> g#(h(),x) half#(x) -> g#(h(),x) -> g#(d(),s(x)) -> g#(d(),x) double#(x) -> g#(d(),x) -> g#(h(),s(s(x))) -> g#(h(),x) double#(x) -> g#(d(),x) -> g#(d(),s(x)) -> g#(d(),x) g#(h(),s(s(x))) -> g#(h(),x) -> g#(h(),s(s(x))) -> g#(h(),x) g#(h(),s(s(x))) -> g#(h(),x) -> g#(d(),s(x)) -> g#(d(),x) g#(d(),s(x)) -> g#(d(),x) -> g#(h(),s(s(x))) -> g#(h(),x) g#(d(),s(x)) -> g#(d(),x) -> g#(d(),s(x)) -> g#(d(),x) SCC Processor: #sccs: 2 #rules: 3 #arcs: 13/49 DPs: f#(s(x),y) -> f#(half(s(x)),double(y)) TRS: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) Usable Rule Processor: DPs: f#(s(x),y) -> f#(half(s(x)),double(y)) TRS: double(x) -> g(d(),x) g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) half(x) -> g(h(),x) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) Maximal Polynomial Processor: usable rules: g(x,0()) -> 0() half(x) -> g(h(),x) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) interpretations: f#(x0, x1) = max(0, 8 + -2 + x0) half(x0) = max(0, 6 + -8 + x0) double(x0) = 4 h = 2 s(x0) = max(0, 3 + 3 + x0) d = 1 g(x0, x1) = max(0, 0 + -8 + x0 + x1) 0 = 0 problem: DPs: TRS: double(x) -> g(d(),x) g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) half(x) -> g(h(),x) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) Qed DPs: g#(d(),s(x)) -> g#(d(),x) g#(h(),s(s(x))) -> g#(h(),x) TRS: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) Subterm Criterion Processor: simple projection: pi(g#) = 1 problem: DPs: TRS: g(x,0()) -> 0() g(d(),s(x)) -> s(s(g(d(),x))) g(h(),s(0())) -> 0() g(h(),s(s(x))) -> s(g(h(),x)) double(x) -> g(d(),x) half(x) -> g(h(),x) f(s(x),y) -> f(half(s(x)),double(y)) Qed