YES Problem: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) Proof: DP Processor: DPs: leq#(s(x),s(y)) -> leq#(x,y) -#(s(x),s(y)) -> -#(x,y) mod#(s(x),s(y)) -> -#(s(x),s(y)) mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) mod#(s(x),s(y)) -> leq#(y,x) mod#(s(x),s(y)) -> if#(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) TDG Processor: DPs: leq#(s(x),s(y)) -> leq#(x,y) -#(s(x),s(y)) -> -#(x,y) mod#(s(x),s(y)) -> -#(s(x),s(y)) mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) mod#(s(x),s(y)) -> leq#(y,x) mod#(s(x),s(y)) -> if#(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) graph: mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) -> mod#(s(x),s(y)) -> if#(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) -> mod#(s(x),s(y)) -> leq#(y,x) mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) -> mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) -> mod#(s(x),s(y)) -> -#(s(x),s(y)) mod#(s(x),s(y)) -> -#(s(x),s(y)) -> -#(s(x),s(y)) -> -#(x,y) mod#(s(x),s(y)) -> leq#(y,x) -> leq#(s(x),s(y)) -> leq#(x,y) -#(s(x),s(y)) -> -#(x,y) -> -#(s(x),s(y)) -> -#(x,y) leq#(s(x),s(y)) -> leq#(x,y) -> leq#(s(x),s(y)) -> leq#(x,y) SCC Processor: #sccs: 3 #rules: 3 #arcs: 8/36 DPs: mod#(s(x),s(y)) -> mod#(-(s(x),s(y)),s(y)) TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) Extended Uncurrying Processor: application symbol: leq symbol table: mod# ==> mod{0,#}/2 mod ==> mod0/2 - ==> -0/2 if ==> if0/3 false ==> false0/0 s ==> s0/1 s1/2 true ==> true0/0 0 ==> 00/0 01/1 uncurry-rules: leq(00(),x8) -> 01(x8) leq(s0(x11),x12) -> s1(x11,x12) eta-rules: problem: DPs: mod{0,#}(s0(x),s0(y)) -> mod{0,#}(-0(s0(x),s0(y)),s0(y)) TRS: 01(y) -> true0() s1(x,00()) -> false0() s1(x,s0(y)) -> leq(x,y) if0(true0(),x,y) -> x if0(false0(),x,y) -> y -0(x,00()) -> x -0(s0(x),s0(y)) -> -0(x,y) mod0(00(),y) -> 00() mod0(s0(x),00()) -> 00() mod0(s0(x),s0(y)) -> if0(leq(y,x),mod0(-0(s0(x),s0(y)),s0(y)),s0(x)) leq(00(),x8) -> 01(x8) leq(s0(x11),x12) -> s1(x11,x12) Extended Uncurrying Processor: application symbol: mod{0,#} symbol table: mod0 ==> mod{0,0}/2 -0 ==> -{0,0}/2 -0_mod{0,#}_1#/3 if0 ==> if{0,0}/3 false0 ==> false{0,0}/0 s1 ==> s{1,0}/2 s0 ==> s{0,0}/1 s0_mod{0,#}_1#/2 true0 ==> true{0,0}/0 01 ==> 0{1,0}/1 00 ==> 0{0,0}/0 leq ==> leq0/2 uncurry-rules: mod{0,#}(-{0,0}(x35,x36),x37) -> -0_mod{0,#}_1#(x35,x36,x37) mod{0,#}(s{0,0}(x33),x34) -> s0_mod{0,#}_1#(x33,x34) eta-rules: mod{0,#}(-0(x,00()),x31) -> mod{0,#}(x,x31) mod{0,#}(-0(s0(x),s0(y)),x32) -> mod{0,#}(-0(x,y),x32) problem: DPs: mod{0,#}(-{0,0}(x35,x36),x37) -> -0_mod{0,#}_1#(x35,x36,x37) mod{0,#}(s{0,0}(x33),x34) -> s0_mod{0,#}_1#(x33,x34) -0_mod{0,#}_1#(x,0{0,0}(),x31) -> mod{0,#}(x,x31) -0_mod{0,#}_1#(s{0,0}(x),s{0,0}(y),x32) -> -0_mod{0,#}_1#(x,y,x32) s0_mod{0,#}_1#(x,s{0,0}(y)) -> -0_mod{0,#}_1#(s{0,0}(x),s{0,0}(y),s{0,0}(y)) TRS: 0{1,0}(y) -> true{0,0}() s{1,0}(x,0{0,0}()) -> false{0,0}() s{1,0}(x,s{0,0}(y)) -> leq0(x,y) if{0,0}(true{0,0}(),x,y) -> x if{0,0}(false{0,0}(),x,y) -> y -{0,0}(x,0{0,0}()) -> x -{0,0}(s{0,0}(x),s{0,0}(y)) -> -{0,0}(x,y) mod{0,0}(0{0,0}(),y) -> 0{0,0}() mod{0,0}(s{0,0}(x),0{0,0}()) -> 0{0,0}() mod{0,0}(s{0,0}(x),s{0,0}(y)) -> if{0,0}(leq0(y,x),mod{0,0}(-{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y)),s{0,0}(x)) leq0(0{0,0}(),x8) -> 0{1,0}(x8) leq0(s{0,0}(x11),x12) -> s{1,0}(x11,x12) Subterm Criterion Processor: simple projection: pi(mod{0,#}) = 0 pi(s{0,0}) = 0 pi(s0_mod{0,#}_1#) = 0 pi(-0_mod{0,#}_1#) = 0 problem: DPs: mod{0,#}(s{0,0}(x33),x34) -> s0_mod{0,#}_1#(x33,x34) -0_mod{0,#}_1#(x,0{0,0}(),x31) -> mod{0,#}(x,x31) -0_mod{0,#}_1#(s{0,0}(x),s{0,0}(y),x32) -> -0_mod{0,#}_1#(x,y,x32) s0_mod{0,#}_1#(x,s{0,0}(y)) -> -0_mod{0,#}_1#(s{0,0}(x),s{0,0}(y),s{0,0}(y)) TRS: 0{1,0}(y) -> true{0,0}() s{1,0}(x,0{0,0}()) -> false{0,0}() s{1,0}(x,s{0,0}(y)) -> leq0(x,y) if{0,0}(true{0,0}(),x,y) -> x if{0,0}(false{0,0}(),x,y) -> y -{0,0}(x,0{0,0}()) -> x -{0,0}(s{0,0}(x),s{0,0}(y)) -> -{0,0}(x,y) mod{0,0}(0{0,0}(),y) -> 0{0,0}() mod{0,0}(s{0,0}(x),0{0,0}()) -> 0{0,0}() mod{0,0}(s{0,0}(x),s{0,0}(y)) -> if{0,0}(leq0(y,x),mod{0,0}(-{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y)),s{0,0}(x)) leq0(0{0,0}(),x8) -> 0{1,0}(x8) leq0(s{0,0}(x11),x12) -> s{1,0}(x11,x12) Subterm Criterion Processor: simple projection: pi(mod{0,#}) = 0 pi(s{0,0}) = [0,0] pi(s0_mod{0,#}_1#) = [0,0] pi(if{0,0}) = [1,2,2] pi(-0_mod{0,#}_1#) = 0 problem: DPs: mod{0,#}(s{0,0}(x33),x34) -> s0_mod{0,#}_1#(x33,x34) -0_mod{0,#}_1#(x,0{0,0}(),x31) -> mod{0,#}(x,x31) s0_mod{0,#}_1#(x,s{0,0}(y)) -> -0_mod{0,#}_1#(s{0,0}(x),s{0,0}(y),s{0,0}(y)) TRS: 0{1,0}(y) -> true{0,0}() s{1,0}(x,0{0,0}()) -> false{0,0}() s{1,0}(x,s{0,0}(y)) -> leq0(x,y) if{0,0}(true{0,0}(),x,y) -> x if{0,0}(false{0,0}(),x,y) -> y -{0,0}(x,0{0,0}()) -> x -{0,0}(s{0,0}(x),s{0,0}(y)) -> -{0,0}(x,y) mod{0,0}(0{0,0}(),y) -> 0{0,0}() mod{0,0}(s{0,0}(x),0{0,0}()) -> 0{0,0}() mod{0,0}(s{0,0}(x),s{0,0}(y)) -> if{0,0}(leq0(y,x),mod{0,0}(-{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y)),s{0,0}(x)) leq0(0{0,0}(),x8) -> 0{1,0}(x8) leq0(s{0,0}(x11),x12) -> s{1,0}(x11,x12) Bounds Processor: bound: 1 enrichment: top-dp automaton: final states: {21,16} transitions: s{1,0,0}(20,20) -> 15* s{1,0,0}(15,15) -> 15* s{1,0,0}(20,15) -> 15* s{1,0,0}(20,21) -> 15* s{1,0,0}(21,15) -> 15* s{1,0,0}(21,20) -> 15* s{1,0,0}(15,20) -> 15* s{1,0,0}(15,21) -> 15* s{1,0,0}(21,21) -> 15* mod{0,0,0}(21,20) -> 15* mod{0,0,0}(20,20) -> 15* mod{0,0,0}(15,21) -> 15* mod{0,0,0}(20,15) -> 15* mod{0,0,0}(20,21) -> 15* mod{0,0,0}(21,15) -> 15* mod{0,0,0}(15,15) -> 15* mod{0,0,0}(15,20) -> 15* mod{0,0,0}(21,21) -> 15* -0_mod{0,#}_1{#,1}(24,23,22) -> 15* -0_mod{0,#}_1{#,1}(22,22,22) -> 15* -0_mod{0,#}_1{#,1}(24,24,24) -> 15* -0_mod{0,#}_1{#,1}(22,24,24) -> 15* -0_mod{0,#}_1{#,0}(20,20,17) -> 16* -0_mod{0,#}_1{#,0}(20,20,21) -> 15* -0_mod{0,#}_1{#,0}(21,20,15) -> 15* -0_mod{0,#}_1{#,0}(21,21,15) -> 15* -0_mod{0,#}_1{#,0}(21,15,21) -> 15* -0_mod{0,#}_1{#,0}(21,21,20) -> 15* -0_mod{0,#}_1{#,0}(15,20,20) -> 15* -0_mod{0,#}_1{#,0}(21,20,20) -> 15* -0_mod{0,#}_1{#,0}(21,15,20) -> 15* -0_mod{0,#}_1{#,0}(20,18,20) -> 16* -0_mod{0,#}_1{#,0}(15,15,21) -> 15* -0_mod{0,#}_1{#,0}(20,21,15) -> 15* -0_mod{0,#}_1{#,0}(15,15,20) -> 15* -0_mod{0,#}_1{#,0}(15,20,21) -> 15* -0_mod{0,#}_1{#,0}(15,15,15) -> 15* -0_mod{0,#}_1{#,0}(20,21,20) -> 15* -0_mod{0,#}_1{#,0}(20,15,15) -> 15* -0_mod{0,#}_1{#,0}(21,20,21) -> 15* -0_mod{0,#}_1{#,0}(20,15,20) -> 15* -0_mod{0,#}_1{#,0}(15,21,20) -> 15* -0_mod{0,#}_1{#,0}(19,20,20) -> 16* -0_mod{0,#}_1{#,0}(15,21,21) -> 15* -0_mod{0,#}_1{#,0}(19,20,17) -> 16* -0_mod{0,#}_1{#,0}(21,15,15) -> 15* -0_mod{0,#}_1{#,0}(20,15,21) -> 15* -0_mod{0,#}_1{#,0}(15,20,15) -> 15* -0_mod{0,#}_1{#,0}(20,21,21) -> 15* -0_mod{0,#}_1{#,0}(21,21,21) -> 15* -0_mod{0,#}_1{#,0}(15,21,15) -> 15* -0_mod{0,#}_1{#,0}(20,20,15) -> 15* -0_mod{0,#}_1{#,0}(20,18,17) -> 16* -0_mod{0,#}_1{#,0}(19,18,17) -> 16* -0_mod{0,#}_1{#,0}(19,18,20) -> 16* -0_mod{0,#}_1{#,0}(20,20,20) -> 21* if{0,0,0}(20,20,15) -> 15* if{0,0,0}(15,21,21) -> 15* if{0,0,0}(15,15,15) -> 15* if{0,0,0}(20,21,20) -> 15* if{0,0,0}(15,20,21) -> 15* if{0,0,0}(20,15,21) -> 15* if{0,0,0}(20,21,21) -> 15* if{0,0,0}(15,15,20) -> 15* if{0,0,0}(15,21,15) -> 15* if{0,0,0}(15,20,15) -> 15* if{0,0,0}(20,21,15) -> 15* if{0,0,0}(20,20,21) -> 15* if{0,0,0}(15,15,21) -> 15* if{0,0,0}(20,15,15) -> 15* if{0,0,0}(15,21,20) -> 15* if{0,0,0}(20,15,20) -> 15* if{0,0,0}(21,21,20) -> 15* if{0,0,0}(21,20,20) -> 15* if{0,0,0}(21,20,21) -> 15* if{0,0,0}(21,20,15) -> 15* if{0,0,0}(21,21,15) -> 15* if{0,0,0}(21,15,15) -> 15* if{0,0,0}(20,20,20) -> 15* if{0,0,0}(15,20,20) -> 15* if{0,0,0}(21,21,21) -> 15* if{0,0,0}(21,15,20) -> 15* if{0,0,0}(21,15,21) -> 15* s0_mod{0,#}_1{#,0}(21,15) -> 15* s0_mod{0,#}_1{#,0}(20,21) -> 15* s0_mod{0,#}_1{#,0}(20,20) -> 15* s0_mod{0,#}_1{#,0}(21,21) -> 15* s0_mod{0,#}_1{#,0}(15,21) -> 15* s0_mod{0,#}_1{#,0}(15,15) -> 15* s0_mod{0,#}_1{#,0}(20,15) -> 15* s0_mod{0,#}_1{#,0}(15,20) -> 15* s0_mod{0,#}_1{#,0}(21,20) -> 15* true{0,0,0}() -> 15* 0{1,0,0}(15) -> 15* 0{1,0,0}(21) -> 15* 0{1,0,0}(20) -> 15* mod{0,#,0}(15,20) -> 15* mod{0,#,0}(21,15) -> 15* mod{0,#,0}(21,21) -> 15* mod{0,#,0}(20,21) -> 15* mod{0,#,0}(20,20) -> 15* mod{0,#,0}(20,15) -> 15* mod{0,#,0}(15,21) -> 15* mod{0,#,0}(15,15) -> 15* mod{0,#,0}(21,20) -> 15* s{0,0,0}(15) -> 20* s{0,0,0}(20) -> 20* s{0,0,0}(21) -> 20* s{0,0,1}(15) -> 23,22 s{0,0,1}(20) -> 23,22 s{0,0,1}(21) -> 24* false{0,0,0}() -> 15* 0{0,0,0}() -> 15* -{0,0,0}(21,21) -> 15* -{0,0,0}(15,20) -> 15* -{0,0,0}(21,15) -> 15* -{0,0,0}(20,15) -> 15* -{0,0,0}(20,21) -> 15* -{0,0,0}(15,15) -> 15* -{0,0,0}(21,20) -> 15* -{0,0,0}(15,21) -> 15* -{0,0,0}(20,20) -> 15* leq{0,0}(15,15) -> 15* leq{0,0}(15,20) -> 15* leq{0,0}(21,15) -> 15* leq{0,0}(21,21) -> 15* leq{0,0}(20,15) -> 15* leq{0,0}(20,20) -> 15* leq{0,0}(20,21) -> 15* leq{0,0}(15,21) -> 15* leq{0,0}(21,20) -> 15* 21 -> 15* 20 -> 15* problem: DPs: mod{0,#}(s{0,0}(x33),x34) -> s0_mod{0,#}_1#(x33,x34) -0_mod{0,#}_1#(x,0{0,0}(),x31) -> mod{0,#}(x,x31) TRS: 0{1,0}(y) -> true{0,0}() s{1,0}(x,0{0,0}()) -> false{0,0}() s{1,0}(x,s{0,0}(y)) -> leq0(x,y) if{0,0}(true{0,0}(),x,y) -> x if{0,0}(false{0,0}(),x,y) -> y -{0,0}(x,0{0,0}()) -> x -{0,0}(s{0,0}(x),s{0,0}(y)) -> -{0,0}(x,y) mod{0,0}(0{0,0}(),y) -> 0{0,0}() mod{0,0}(s{0,0}(x),0{0,0}()) -> 0{0,0}() mod{0,0}(s{0,0}(x),s{0,0}(y)) -> if{0,0}(leq0(y,x),mod{0,0}(-{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y)),s{0,0}(x)) leq0(0{0,0}(),x8) -> 0{1,0}(x8) leq0(s{0,0}(x11),x12) -> s{1,0}(x11,x12) SCC Processor: #sccs: 0 #rules: 0 #arcs: 1/4 DPs: leq#(s(x),s(y)) -> leq#(x,y) TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) Subterm Criterion Processor: simple projection: pi(leq#) = 0 problem: DPs: TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) Qed DPs: -#(s(x),s(y)) -> -#(x,y) TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) Subterm Criterion Processor: simple projection: pi(-#) = 0 problem: DPs: TRS: leq(0(),y) -> true() leq(s(x),0()) -> false() leq(s(x),s(y)) -> leq(x,y) if(true(),x,y) -> x if(false(),x,y) -> y -(x,0()) -> x -(s(x),s(y)) -> -(x,y) mod(0(),y) -> 0() mod(s(x),0()) -> 0() mod(s(x),s(y)) -> if(leq(y,x),mod(-(s(x),s(y)),s(y)),s(x)) Qed