YES Problem: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) Proof: DP Processor: DPs: minus#(s(x),s(y)) -> minus#(x,y) le#(s(x),s(y)) -> le#(x,y) quot#(s(x),s(y)) -> minus#(s(x),s(y)) quot#(s(x),s(y)) -> quot#(minus(s(x),s(y)),s(y)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) TDG Processor: DPs: minus#(s(x),s(y)) -> minus#(x,y) le#(s(x),s(y)) -> le#(x,y) quot#(s(x),s(y)) -> minus#(s(x),s(y)) quot#(s(x),s(y)) -> quot#(minus(s(x),s(y)),s(y)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) graph: quot#(s(x),s(y)) -> quot#(minus(s(x),s(y)),s(y)) -> quot#(s(x),s(y)) -> quot#(minus(s(x),s(y)),s(y)) quot#(s(x),s(y)) -> quot#(minus(s(x),s(y)),s(y)) -> quot#(s(x),s(y)) -> minus#(s(x),s(y)) quot#(s(x),s(y)) -> minus#(s(x),s(y)) -> minus#(s(x),s(y)) -> minus#(x,y) le#(s(x),s(y)) -> le#(x,y) -> le#(s(x),s(y)) -> le#(x,y) minus#(s(x),s(y)) -> minus#(x,y) -> minus#(s(x),s(y)) -> minus#(x,y) SCC Processor: #sccs: 3 #rules: 3 #arcs: 5/16 DPs: le#(s(x),s(y)) -> le#(x,y) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) Subterm Criterion Processor: simple projection: pi(le#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) Qed DPs: quot#(s(x),s(y)) -> quot#(minus(s(x),s(y)),s(y)) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) Extended Uncurrying Processor: application symbol: le symbol table: quot# ==> quot{0,#}/2 quot ==> quot0/2 false ==> false0/0 true ==> true0/0 s ==> s0/1 s1/2 minus ==> minus0/2 0 ==> 00/0 01/1 uncurry-rules: le(00(),x11) -> 01(x11) le(s0(x13),x14) -> s1(x13,x14) eta-rules: problem: DPs: quot{0,#}(s0(x),s0(y)) -> quot{0,#}(minus0(s0(x),s0(y)),s0(y)) TRS: minus0(x,00()) -> x minus0(s0(x),s0(y)) -> minus0(x,y) 01(y) -> true0() s1(x,00()) -> false0() s1(x,s0(y)) -> le(x,y) quot0(00(),s0(y)) -> 00() quot0(s0(x),s0(y)) -> s0(quot0(minus0(s0(x),s0(y)),s0(y))) le(00(),x11) -> 01(x11) le(s0(x13),x14) -> s1(x13,x14) Extended Uncurrying Processor: application symbol: quot{0,#} symbol table: quot0 ==> quot{0,0}/2 false0 ==> false{0,0}/0 true0 ==> true{0,0}/0 s1 ==> s{1,0}/2 s0 ==> s{0,0}/1 s0_quot{0,#}_1#/2 minus0 ==> minus{0,0}/2 minus0_quot{0,#}_1#/3 01 ==> 0{1,0}/1 00 ==> 0{0,0}/0 le ==> le0/2 uncurry-rules: quot{0,#}(s{0,0}(x32),x33) -> s0_quot{0,#}_1#(x32,x33) quot{0,#}(minus{0,0}(x29,x30),x31) -> minus0_quot{0,#}_1#(x29,x30,x31) eta-rules: quot{0,#}(minus0(x,00()),x27) -> quot{0,#}(x,x27) quot{0,#}(minus0(s0(x),s0(y)),x28) -> quot{0,#}(minus0(x,y),x28) problem: DPs: quot{0,#}(s{0,0}(x32),x33) -> s0_quot{0,#}_1#(x32,x33) quot{0,#}(minus{0,0}(x29,x30),x31) -> minus0_quot{0,#}_1#(x29,x30,x31) minus0_quot{0,#}_1#(x,0{0,0}(),x27) -> quot{0,#}(x,x27) minus0_quot{0,#}_1#(s{0,0}(x),s{0,0}(y),x28) -> minus0_quot{0,#}_1#(x,y,x28) s0_quot{0,#}_1#(x,s{0,0}(y)) -> minus0_quot{0,#}_1#(s{0,0}(x),s{0,0}(y),s{0,0}(y)) TRS: minus{0,0}(x,0{0,0}()) -> x minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) 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)) -> le0(x,y) quot{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() quot{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(quot{0,0}(minus{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y))) le0(0{0,0}(),x11) -> 0{1,0}(x11) le0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Subterm Criterion Processor: simple projection: pi(quot{0,#}) = 0 pi(minus0_quot{0,#}_1#) = 0 pi(s{0,0}) = 0 pi(s0_quot{0,#}_1#) = 0 problem: DPs: quot{0,#}(s{0,0}(x32),x33) -> s0_quot{0,#}_1#(x32,x33) minus0_quot{0,#}_1#(x,0{0,0}(),x27) -> quot{0,#}(x,x27) minus0_quot{0,#}_1#(s{0,0}(x),s{0,0}(y),x28) -> minus0_quot{0,#}_1#(x,y,x28) s0_quot{0,#}_1#(x,s{0,0}(y)) -> minus0_quot{0,#}_1#(s{0,0}(x),s{0,0}(y),s{0,0}(y)) TRS: minus{0,0}(x,0{0,0}()) -> x minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) 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)) -> le0(x,y) quot{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() quot{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(quot{0,0}(minus{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y))) le0(0{0,0}(),x11) -> 0{1,0}(x11) le0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Subterm Criterion Processor: simple projection: pi(quot{0,#}) = 0 pi(minus{0,0}) = [0,0] pi(minus0_quot{0,#}_1#) = 0 pi(s{0,0}) = [0,0] pi(s0_quot{0,#}_1#) = [0,0] problem: DPs: quot{0,#}(s{0,0}(x32),x33) -> s0_quot{0,#}_1#(x32,x33) minus0_quot{0,#}_1#(x,0{0,0}(),x27) -> quot{0,#}(x,x27) s0_quot{0,#}_1#(x,s{0,0}(y)) -> minus0_quot{0,#}_1#(s{0,0}(x),s{0,0}(y),s{0,0}(y)) TRS: minus{0,0}(x,0{0,0}()) -> x minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) 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)) -> le0(x,y) quot{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() quot{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(quot{0,0}(minus{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y))) le0(0{0,0}(),x11) -> 0{1,0}(x11) le0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) Bounds Processor: bound: 1 enrichment: top-dp automaton: final states: {21,16} transitions: quot{0,0,0}(20,20) -> 15* quot{0,0,0}(15,15) -> 15* quot{0,0,0}(20,15) -> 15* quot{0,0,0}(20,21) -> 15* quot{0,0,0}(21,15) -> 15* quot{0,0,0}(21,20) -> 15* quot{0,0,0}(15,20) -> 15* quot{0,0,0}(15,21) -> 15* quot{0,0,0}(21,21) -> 15* minus0_quot{0,#}_1{#,0}(20,20,20) -> 21* minus0_quot{0,#}_1{#,0}(15,20,21) -> 15* minus0_quot{0,#}_1{#,0}(19,20,17) -> 16* minus0_quot{0,#}_1{#,0}(15,20,20) -> 15* minus0_quot{0,#}_1{#,0}(19,18,17) -> 16* minus0_quot{0,#}_1{#,0}(21,20,21) -> 15* minus0_quot{0,#}_1{#,0}(21,15,21) -> 15* minus0_quot{0,#}_1{#,0}(15,15,15) -> 15* minus0_quot{0,#}_1{#,0}(19,20,20) -> 16* minus0_quot{0,#}_1{#,0}(21,21,21) -> 15* minus0_quot{0,#}_1{#,0}(19,18,20) -> 16* minus0_quot{0,#}_1{#,0}(20,21,21) -> 15* minus0_quot{0,#}_1{#,0}(20,20,21) -> 15* minus0_quot{0,#}_1{#,0}(21,20,15) -> 15* minus0_quot{0,#}_1{#,0}(15,20,15) -> 15* minus0_quot{0,#}_1{#,0}(15,15,20) -> 15* minus0_quot{0,#}_1{#,0}(15,21,21) -> 15* minus0_quot{0,#}_1{#,0}(21,21,20) -> 15* minus0_quot{0,#}_1{#,0}(15,21,15) -> 15* minus0_quot{0,#}_1{#,0}(20,15,21) -> 15* minus0_quot{0,#}_1{#,0}(15,15,21) -> 15* minus0_quot{0,#}_1{#,0}(21,21,15) -> 15* minus0_quot{0,#}_1{#,0}(21,20,20) -> 15* minus0_quot{0,#}_1{#,0}(15,21,20) -> 15* minus0_quot{0,#}_1{#,0}(21,15,20) -> 15* minus0_quot{0,#}_1{#,0}(20,20,17) -> 16* minus0_quot{0,#}_1{#,0}(21,15,15) -> 15* minus0_quot{0,#}_1{#,0}(20,21,15) -> 15* minus0_quot{0,#}_1{#,0}(20,21,20) -> 15* minus0_quot{0,#}_1{#,0}(20,15,20) -> 15* minus0_quot{0,#}_1{#,0}(20,20,15) -> 15* minus0_quot{0,#}_1{#,0}(20,18,17) -> 16* minus0_quot{0,#}_1{#,0}(20,18,20) -> 16* minus0_quot{0,#}_1{#,0}(20,15,15) -> 15* s0_quot{0,#}_1{#,0}(20,21) -> 15* s0_quot{0,#}_1{#,0}(20,15) -> 15* s0_quot{0,#}_1{#,0}(15,15) -> 15* s0_quot{0,#}_1{#,0}(15,20) -> 15* s0_quot{0,#}_1{#,0}(20,20) -> 15* s0_quot{0,#}_1{#,0}(21,21) -> 15* s0_quot{0,#}_1{#,0}(15,21) -> 15* s0_quot{0,#}_1{#,0}(21,15) -> 15* s0_quot{0,#}_1{#,0}(21,20) -> 15* true{0,0,0}() -> 15* minus0_quot{0,#}_1{#,1}(22,22,22) -> 15* minus0_quot{0,#}_1{#,1}(24,24,24) -> 15* minus0_quot{0,#}_1{#,1}(24,23,22) -> 15* minus0_quot{0,#}_1{#,1}(22,24,24) -> 15* 0{1,0,0}(21) -> 15* 0{1,0,0}(15) -> 15* 0{1,0,0}(20) -> 15* le{0,0}(21,20) -> 15* le{0,0}(20,21) -> 15* le{0,0}(15,20) -> 15* le{0,0}(21,15) -> 15* le{0,0}(15,21) -> 15* le{0,0}(20,20) -> 15* le{0,0}(15,15) -> 15* le{0,0}(21,21) -> 15* le{0,0}(20,15) -> 15* false{0,0,0}() -> 15* 0{0,0,0}() -> 15* minus{0,0,0}(21,21) -> 15* minus{0,0,0}(21,20) -> 15* minus{0,0,0}(15,15) -> 15* minus{0,0,0}(20,20) -> 15* minus{0,0,0}(15,21) -> 15* minus{0,0,0}(20,21) -> 15* minus{0,0,0}(15,20) -> 15* minus{0,0,0}(21,15) -> 15* minus{0,0,0}(20,15) -> 15* s{0,0,0}(20) -> 20* s{0,0,0}(15) -> 20* s{0,0,0}(21) -> 20* s{0,0,1}(21) -> 24* s{0,0,1}(15) -> 23,22 s{0,0,1}(20) -> 23,22 s{1,0,0}(20,21) -> 15* s{1,0,0}(20,15) -> 15* s{1,0,0}(15,21) -> 15* s{1,0,0}(20,20) -> 15* s{1,0,0}(21,15) -> 15* s{1,0,0}(15,15) -> 15* s{1,0,0}(21,20) -> 15* s{1,0,0}(21,21) -> 15* s{1,0,0}(15,20) -> 15* quot{0,#,0}(21,21) -> 15* quot{0,#,0}(15,21) -> 15* quot{0,#,0}(20,21) -> 15* quot{0,#,0}(15,20) -> 15* quot{0,#,0}(15,15) -> 15* quot{0,#,0}(20,15) -> 15* quot{0,#,0}(20,20) -> 15* quot{0,#,0}(21,20) -> 15* quot{0,#,0}(21,15) -> 15* 21 -> 15* 20 -> 15* problem: DPs: quot{0,#}(s{0,0}(x32),x33) -> s0_quot{0,#}_1#(x32,x33) minus0_quot{0,#}_1#(x,0{0,0}(),x27) -> quot{0,#}(x,x27) TRS: minus{0,0}(x,0{0,0}()) -> x minus{0,0}(s{0,0}(x),s{0,0}(y)) -> minus{0,0}(x,y) 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)) -> le0(x,y) quot{0,0}(0{0,0}(),s{0,0}(y)) -> 0{0,0}() quot{0,0}(s{0,0}(x),s{0,0}(y)) -> s{0,0}(quot{0,0}(minus{0,0}(s{0,0}(x),s{0,0}(y)),s{0,0}(y))) le0(0{0,0}(),x11) -> 0{1,0}(x11) le0(s{0,0}(x13),x14) -> s{1,0}(x13,x14) SCC Processor: #sccs: 0 #rules: 0 #arcs: 1/4 DPs: minus#(s(x),s(y)) -> minus#(x,y) TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) Subterm Criterion Processor: simple projection: pi(minus#) = 0 problem: DPs: TRS: minus(x,0()) -> x minus(s(x),s(y)) -> minus(x,y) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) quot(0(),s(y)) -> 0() quot(s(x),s(y)) -> s(quot(minus(s(x),s(y)),s(y))) Qed