YES Problem: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Proof: DP Processor: DPs: minus#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) plus#(s(x),y) -> plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) TDG Processor: DPs: minus#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) plus#(s(x),y) -> plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) graph: plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) -> plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) -> plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) -> plus#(s(x),y) -> plus#(x,y) plus#(s(x),y) -> plus#(x,y) -> plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(s(x),y) -> plus#(x,y) -> plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(s(x),y) -> plus#(x,y) -> plus#(s(x),y) -> plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) -> plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) -> plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) -> plus#(s(x),y) -> plus#(x,y) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) -> quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) -> quot#(s(x),s(y)) -> minus#(x,y) quot#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y) minus#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y) SCC Processor: #sccs: 3 #rules: 5 #arcs: 13/36 DPs: quot#(s(x),s(y)) -> quot#(minus(x,y),s(y)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Matrix Interpretation Processor: dim=1 interpretation: [quot#](x0, x1) = x0 + 2, [plus](x0, x1) = 2x0 + 2x1 + 2, [quot](x0, x1) = 4x0 + 2x1 + 3, [s](x0) = x0 + 1, [minus](x0, x1) = x0, [0] = 0 orientation: quot#(s(x),s(y)) = x + 3 >= x + 2 = quot#(minus(x,y),s(y)) minus(x,0()) = x >= x = x minus(s(x),s(y)) = x + 1 >= x = minus(x,y) quot(0(),s(y)) = 2y + 5 >= 0 = 0() quot(s(x),s(y)) = 4x + 2y + 9 >= 4x + 2y + 6 = s(quot(minus(x,y),s(y))) plus(0(),y) = 2y + 2 >= y = y plus(s(x),y) = 2x + 2y + 4 >= 2x + 2y + 3 = s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) = 2x + 2y + 2 >= 2x + 2y + 2 = plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) = 4x + 4y + 4z + 22 >= 4x + 4y + 4z + 22 = plus(plus(y,s(s(z))),plus(x,s(0()))) problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Qed DPs: minus#(s(x),s(y)) -> minus#(x,y) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Subterm Criterion Processor: simple projection: pi(minus#) = 1 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Qed DPs: plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(s(x),y) -> plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) CDG Processor: DPs: plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(s(x),y) -> plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) graph: plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) -> plus#(s(x),y) -> plus#(x,y) plus#(s(x),y) -> plus#(x,y) -> plus#(s(x),y) -> plus#(x,y) plus#(s(x),y) -> plus#(x,y) -> plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(s(x),y) -> plus#(x,y) -> plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) -> plus#(s(x),y) -> plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) -> plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) -> plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) Matrix Interpretation Processor: dim=1 interpretation: [plus#](x0, x1) = 4x0 + 4x1, [plus](x0, x1) = x0 + x1, [quot](x0, x1) = x0, [s](x0) = x0 + 1, [minus](x0, x1) = x0, [0] = 1 orientation: plus#(plus(x,s(0())),plus(y,s(s(z)))) = 4x + 4y + 4z + 16 >= 4x + 4y + 4z + 16 = plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(s(x),y) = 4x + 4y + 4 >= 4x + 4y = plus#(x,y) plus#(minus(x,s(0())),minus(y,s(s(z)))) = 4x + 4y >= 4x + 4y = plus#(minus(y,s(s(z))),minus(x,s(0()))) minus(x,0()) = x >= x = x minus(s(x),s(y)) = x + 1 >= x = minus(x,y) quot(0(),s(y)) = 1 >= 1 = 0() quot(s(x),s(y)) = x + 1 >= x + 1 = s(quot(minus(x,y),s(y))) plus(0(),y) = y + 1 >= y = y plus(s(x),y) = x + y + 1 >= x + y + 1 = s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) = x + y >= x + y = plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) = x + y + z + 4 >= x + y + z + 4 = plus(plus(y,s(s(z))),plus(x,s(0()))) problem: DPs: plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) SCC Processor: #sccs: 1 #rules: 1 #arcs: 7/4 DPs: plus#(minus(x,s(0())),minus(y,s(s(z)))) -> plus#(minus(y,s(s(z))),minus(x,s(0()))) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Matrix Interpretation Processor: dim=3 interpretation: [plus#](x0, x1) = [0 0 1]x0 + [0 1 0]x1, [1 0 0] [1 0 0] [plus](x0, x1) = [0 1 1]x0 + [0 1 1]x1 [0 1 1] [0 1 1] , [1 0 0] [quot](x0, x1) = [1 0 0]x0 [1 0 0] , [1 0 0] [1] [s](x0) = [0 0 1]x0 + [1] [0 1 0] [0], [1 0 0] [0 0 0] [minus](x0, x1) = [0 1 1]x0 + [0 1 1]x1 [0 1 1] [0 0 0] , [1] [0] = [0] [0] orientation: plus#(minus(x,s(0())),minus(y,s(s(z)))) = [0 1 1]x + [0 1 1]y + [0 1 1]z + [2] >= [0 1 1]x + [0 1 1]y + [1] = plus#(minus(y,s(s(z))),minus(x,s(0()))) [1 0 0] minus(x,0()) = [0 1 1]x >= x = x [0 1 1] [1 0 0] [0 0 0] [1] [1 0 0] [0 0 0] minus(s(x),s(y)) = [0 1 1]x + [0 1 1]y + [2] >= [0 1 1]x + [0 1 1]y = minus(x,y) [0 1 1] [0 0 0] [1] [0 1 1] [0 0 0] [1] [1] quot(0(),s(y)) = [1] >= [0] = 0() [1] [0] [1 0 0] [1] [1 0 0] [1] quot(s(x),s(y)) = [1 0 0]x + [1] >= [1 0 0]x + [1] = s(quot(minus(x,y),s(y))) [1 0 0] [1] [1 0 0] [0] [1 0 0] [1] plus(0(),y) = [0 1 1]y + [0] >= y = y [0 1 1] [0] [1 0 0] [1 0 0] [1] [1 0 0] [1 0 0] [1] plus(s(x),y) = [0 1 1]x + [0 1 1]y + [1] >= [0 1 1]x + [0 1 1]y + [1] = s(plus(x,y)) [0 1 1] [0 1 1] [1] [0 1 1] [0 1 1] [0] [1 0 0] [1 0 0] [0 0 0] [0] [1 0 0] [1 0 0] [0 0 0] [0] plus(minus(x,s(0())),minus(y,s(s(z)))) = [0 2 2]x + [0 2 2]y + [0 1 1]z + [3] >= [0 2 2]x + [0 2 2]y + [0 1 1]z + [3] = plus(minus(y,s(s(z))),minus(x,s(0()))) [0 2 2] [0 2 2] [0 1 1] [3] [0 2 2] [0 2 2] [0 1 1] [3] [1 0 0] [1 0 0] [1 0 0] [4] [1 0 0] [1 0 0] [1 0 0] [4] plus(plus(x,s(0())),plus(y,s(s(z)))) = [0 2 2]x + [0 2 2]y + [0 2 2]z + [6] >= [0 2 2]x + [0 2 2]y + [0 2 2]z + [6] = plus(plus(y,s(s(z))),plus(x,s(0()))) [0 2 2] [0 2 2] [0 2 2] [6] [0 2 2] [0 2 2] [0 2 2] [6] problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(x,y),s(y))) plus(0(),y) -> y plus(s(x),y) -> s(plus(x,y)) plus(minus(x,s(0())),minus(y,s(s(z)))) -> plus(minus(y,s(s(z))),minus(x,s(0()))) plus(plus(x,s(0())),plus(y,s(s(z)))) -> plus(plus(y,s(s(z))),plus(x,s(0()))) Qed