YES Problem: pred(s(x)) -> x minus(x,0()) -> x minus(x,s(y)) -> pred(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) Proof: DP Processor: DPs: minus#(x,s(y)) -> minus#(x,y) minus#(x,s(y)) -> pred#(minus(x,y)) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) TRS: pred(s(x)) -> x minus(x,0()) -> x minus(x,s(y)) -> pred(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) Matrix Interpretation Processor: dim=1 interpretation: [quot#](x0, x1) = x0 + 2x1, [minus#](x0, x1) = 1/2x0 + x1 + 1, [pred#](x0) = 1/2x0 + 1, [quot](x0, x1) = 2x0 + 7/2, [minus](x0, x1) = x0, [0] = 2, [pred](x0) = x0, [s](x0) = x0 + 1/2 orientation: minus#(x,s(y)) = 1/2x + y + 3/2 >= 1/2x + y + 1 = minus#(x,y) minus#(x,s(y)) = 1/2x + y + 3/2 >= 1/2x + 1 = pred#(minus(x,y)) quot#(s(x),s(y)) = x + 2y + 3/2 >= 1/2x + y + 1 = minus#(x,y) quot#(s(x),s(y)) = x + 2y + 3/2 >= x + 2y + 1 = quot#(minus(x,y),s(y)) pred(s(x)) = x + 1/2 >= x = x minus(x,0()) = x >= x = x minus(x,s(y)) = x >= x = pred(minus(x,y)) quot(0(),s(y)) = 15/2 >= 2 = 0() quot(s(x),s(y)) = 2x + 9/2 >= 2x + 4 = s(quot(minus(x,y),s(y))) problem: DPs: TRS: pred(s(x)) -> x minus(x,0()) -> x minus(x,s(y)) -> pred(minus(x,y)) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) Qed