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: [1 1 0] [1 1 0] [plus](x0, x1) = [1 1 0]x0 + [1 1 0]x1 [0 1 1] [0 1 1] , [1 1 0] [0 0 0] [1] [minus](x0, x1) = [1 1 0]x0 + [1 0 0]x1 + [1] [0 0 1] [0 0 0] [0], [0] [0] = [0] [0], [plus#](x0, x1) = [1 0 0]x0 + [0 1 0]x1, [1] [s](x0) = x0 + [0] [0] orientation: plus#(plus(x,s(0())),plus(y,s(s(z)))) = [1 1 0]x + [1 1 0]y + [1 1 0]z + [3] >= [1 1 0]x + [1 1 0]y + [1 1 0]z + [3] = plus#(plus(y,s(s(z))),plus(x,s(0()))) plus#(minus(x,s(0())),minus(y,s(s(z)))) = [1 1 0]x + [1 1 0]y + [1 0 0]z + [4] >= [1 1 0]x + [1 1 0]y + [3] = plus#(minus(y,s(s(z))),minus(x,s(0()))) [1 1 0] plus(0(),y) = [1 1 0]y >= y = y [0 1 1] [1 1 0] [1 1 0] [1] [1 1 0] [1 1 0] [1] plus(s(x),y) = [1 1 0]x + [1 1 0]y + [1] >= [1 1 0]x + [1 1 0]y + [0] = s(plus(x,y)) [0 1 1] [0 1 1] [0] [0 1 1] [0 1 1] [0] [2 2 0] [2 2 0] [1 0 0] [7] [2 2 0] [2 2 0] [1 0 0] [7] plus(minus(x,s(0())),minus(y,s(s(z)))) = [2 2 0]x + [2 2 0]y + [1 0 0]z + [7] >= [2 2 0]x + [2 2 0]y + [1 0 0]z + [7] = plus(minus(y,s(s(z))),minus(x,s(0()))) [1 1 1] [1 1 1] [1 0 0] [5] [1 1 1] [1 1 1] [1 0 0] [5] [2 2 0] [2 2 0] [2 2 0] [6] [2 2 0] [2 2 0] [2 2 0] [6] plus(plus(x,s(0())),plus(y,s(s(z)))) = [2 2 0]x + [2 2 0]y + [2 2 0]z + [6] >= [2 2 0]x + [2 2 0]y + [2 2 0]z + [6] = plus(plus(y,s(s(z))),plus(x,s(0()))) [1 2 1] [1 2 1] [1 2 1] [3] [1 2 1] [1 2 1] [1 2 1] [3] [1 1 0] [0 0 0] [2] [1 1 0] [0 0 0] [1] minus(s(x),s(y)) = [1 1 0]x + [1 0 0]y + [3] >= [1 1 0]x + [1 0 0]y + [1] = minus(x,y) [0 0 1] [0 0 0] [0] [0 0 1] [0 0 0] [0] [1 1 0] [1] minus(x,0()) = [1 1 0]x + [1] >= x = x [0 0 1] [0] 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: plus{#,1}(20,17) -> 8* s1(7) -> 18* s1(15) -> 16* s1(20) -> 20* s1(18) -> 19* s1(17) -> 17* plus{#,0}(7,7) -> 8* quot0(7,7) -> 7* minus0(7,7) -> 7* plus0(7,7) -> 7* 00() -> 7* s0(7) -> 7* 01() -> 15* plus1(7,16) -> 17* plus1(7,19) -> 20* 19 -> 20* 16 -> 17* 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