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()))) Subterm Criterion Processor: simple projection: pi(minus) = 0 pi(quot#) = 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#) = 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: 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()))) Subterm Criterion Processor: simple projection: pi(minus) = 0 pi(plus#) = [0,0,1,1] 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()))) Usable Rule Processor: 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: 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()))) minus(s(x),s(y)) -> minus(x,y) minus(x,0()) -> x Matrix Interpretation Processor: dim=3 usable rules: 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()))) minus(s(x),s(y)) -> minus(x,y) minus(x,0()) -> x interpretation: [plus#](x0, x1) = [0 1 0]x0 + [0 0 1]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] [1] [s](x0) = [0 0 1]x0 + [0] [0 1 0] [0], [1 0 0] [0 0 0] [minus](x0, x1) = [0 1 1]x0 + [0 1 1]x1 [0 1 1] [1 1 1] , [0] [0] = [0] [0] orientation: plus#(plus(x,s(0())),plus(y,s(s(z)))) = [0 1 1]x + [0 1 1]y + [0 1 1]z >= [0 1 1]x + [0 1 1]y + [0 1 1]z = plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) = [0 1 1]x + [0 1 1]y + [1 1 1]z + [2] >= [0 1 1]x + [0 1 1]y + [0 1 1]z + [1] = plus#(minus(y,s(s(z))),minus(x,s(0()))) [1 0 0] plus(0(),y) = [0 1 1]y >= y = y [0 1 1] [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 + [0] >= [0 1 1]x + [0 1 1]y + [0] = s(plus(x,y)) [0 1 1] [0 1 1] [0] [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 + [1 2 2]z + [3] >= [0 2 2]x + [0 2 2]y + [1 2 2]z + [3] = plus(minus(y,s(s(z))),minus(x,s(0()))) [0 2 2] [0 2 2] [1 2 2] [3] [0 2 2] [0 2 2] [1 2 2] [3] [1 0 0] [1 0 0] [1 0 0] [3] [1 0 0] [1 0 0] [1 0 0] [3] plus(plus(x,s(0())),plus(y,s(s(z)))) = [0 2 2]x + [0 2 2]y + [0 2 2]z + [0] >= [0 2 2]x + [0 2 2]y + [0 2 2]z + [0] = plus(plus(y,s(s(z))),plus(x,s(0()))) [0 2 2] [0 2 2] [0 2 2] [0] [0 2 2] [0 2 2] [0 2 2] [0] [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 + [0] >= [0 1 1]x + [0 1 1]y = minus(x,y) [0 1 1] [1 1 1] [1] [0 1 1] [1 1 1] [1 0 0] minus(x,0()) = [0 1 1]x >= x = x [0 1 1] problem: DPs: plus#(plus(x,s(0())),plus(y,s(s(z)))) -> plus#(plus(y,s(s(z))),plus(x,s(0()))) TRS: 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()))) minus(s(x),s(y)) -> minus(x,y) minus(x,0()) -> x Restore Modifier: DPs: 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()))) Bounds Processor: bound: 1 enrichment: top-dp automaton: final states: {8} transitions: minus0(7,7) -> 7* quot0(7,7) -> 7* plus{#,1}(20,17) -> 8* plus1(7,16) -> 17* plus1(7,19) -> 20* s1(20) -> 20* s1(15) -> 16* s1(17) -> 17* s1(7) -> 18* s1(18) -> 19* 01() -> 15* plus{#,0}(7,7) -> 8* plus0(7,7) -> 7* s0(7) -> 7* 00() -> 7* 16 -> 17* 19 -> 20* 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