YES Problem: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Proof: DP Processor: DPs: half#(s(s(x))) -> half#(x) le#(s(x),s(y)) -> le#(x,y) inc#(s(x)) -> inc#(x) logarithm#(x) -> logIter#(x,0()) logIter#(x,y) -> inc#(y) logIter#(x,y) -> half#(x) logIter#(x,y) -> le#(s(s(0())),x) logIter#(x,y) -> le#(s(0()),x) logIter#(x,y) -> if#(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if#(true(),true(),x,y) -> logIter#(x,y) TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() TDG Processor: DPs: half#(s(s(x))) -> half#(x) le#(s(x),s(y)) -> le#(x,y) inc#(s(x)) -> inc#(x) logarithm#(x) -> logIter#(x,0()) logIter#(x,y) -> inc#(y) logIter#(x,y) -> half#(x) logIter#(x,y) -> le#(s(s(0())),x) logIter#(x,y) -> le#(s(0()),x) logIter#(x,y) -> if#(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if#(true(),true(),x,y) -> logIter#(x,y) TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() graph: if#(true(),true(),x,y) -> logIter#(x,y) -> logIter#(x,y) -> if#(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if#(true(),true(),x,y) -> logIter#(x,y) -> logIter#(x,y) -> le#(s(0()),x) if#(true(),true(),x,y) -> logIter#(x,y) -> logIter#(x,y) -> le#(s(s(0())),x) if#(true(),true(),x,y) -> logIter#(x,y) -> logIter#(x,y) -> half#(x) if#(true(),true(),x,y) -> logIter#(x,y) -> logIter#(x,y) -> inc#(y) logIter#(x,y) -> if#(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) -> if#(true(),true(),x,y) -> logIter#(x,y) logIter#(x,y) -> inc#(y) -> inc#(s(x)) -> inc#(x) logIter#(x,y) -> le#(s(s(0())),x) -> le#(s(x),s(y)) -> le#(x,y) logIter#(x,y) -> le#(s(0()),x) -> le#(s(x),s(y)) -> le#(x,y) logIter#(x,y) -> half#(x) -> half#(s(s(x))) -> half#(x) logarithm#(x) -> logIter#(x,0()) -> logIter#(x,y) -> if#(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) logarithm#(x) -> logIter#(x,0()) -> logIter#(x,y) -> le#(s(0()),x) logarithm#(x) -> logIter#(x,0()) -> logIter#(x,y) -> le#(s(s(0())),x) logarithm#(x) -> logIter#(x,0()) -> logIter#(x,y) -> half#(x) logarithm#(x) -> logIter#(x,0()) -> logIter#(x,y) -> inc#(y) inc#(s(x)) -> inc#(x) -> inc#(s(x)) -> inc#(x) le#(s(x),s(y)) -> le#(x,y) -> le#(s(x),s(y)) -> le#(x,y) half#(s(s(x))) -> half#(x) -> half#(s(s(x))) -> half#(x) SCC Processor: #sccs: 4 #rules: 5 #arcs: 18/100 DPs: if#(true(),true(),x,y) -> logIter#(x,y) logIter#(x,y) -> if#(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Extended Uncurrying Processor: application symbol: le symbol table: if# ==> if{0,#}/4 logIter# ==> logIter{0,#}/2 h ==> h0/0 g ==> g0/0 f ==> f0/0 logZeroError ==> logZeroError0/0 if ==> if0/4 logIter ==> logIter0/2 logarithm ==> logarithm0/1 inc ==> inc0/1 false ==> false0/0 true ==> true0/0 s ==> s0/1 s1/2 half ==> half0/1 0 ==> 00/0 01/1 uncurry-rules: le(00(),x18) -> 01(x18) le(s0(x20),x21) -> s1(x20,x21) eta-rules: problem: DPs: if{0,#}(true0(),true0(),x,y) -> logIter{0,#}(x,y) logIter{0,#}(x,y) -> if{0,#}(s1(00(),x),s1(s0(00()),x),half0(x),inc0(y)) TRS: half0(00()) -> 00() half0(s0(00())) -> 00() half0(s0(s0(x))) -> s0(half0(x)) 01(y) -> true0() s1(x,00()) -> false0() s1(x,s0(y)) -> le(x,y) inc0(s0(x)) -> s0(inc0(x)) inc0(00()) -> s0(00()) logarithm0(x) -> logIter0(x,00()) logIter0(x,y) -> if0(s1(00(),x),s1(s0(00()),x),half0(x),inc0(y)) if0(false0(),b,x,y) -> logZeroError0() if0(true0(),false0(),x,s0(y)) -> y if0(true0(),true0(),x,y) -> logIter0(x,y) f0() -> g0() f0() -> h0() le(00(),x18) -> 01(x18) le(s0(x20),x21) -> s1(x20,x21) Extended Uncurrying Processor: application symbol: if{0,#} symbol table: logIter{0,#} ==> logIter{0,0,#}/2 h0 ==> h{0,0}/0 g0 ==> g{0,0}/0 f0 ==> f{0,0}/0 logZeroError0 ==> logZeroError{0,0}/0 if0 ==> if{0,0}/4 logIter0 ==> logIter{0,0}/2 logarithm0 ==> logarithm{0,0}/1 inc0 ==> inc{0,0}/1 false0 ==> false{0,0}/0 true0 ==> true{0,0}/0 true0_if{0,#}_1#/3 s1 ==> s{1,0}/2 s1_if{0,#}_1#/5 s0 ==> s{0,0}/1 half0 ==> half{0,0}/1 01 ==> 0{1,0}/1 00 ==> 0{0,0}/0 le ==> le0/2 uncurry-rules: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) -> s1_if{0,#}_1#(x59,x60,x61,x62,x63) eta-rules: if{0,#}(s1(x,00()),x53,x54,x55) -> if{0,#}(false0(),x53,x54,x55) if{0,#}(s1(x,s0(y)),x56,x57,x58) -> if{0,#}(le(x,y),x56,x57,x58) problem: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) -> s1_if{0,#}_1#(x59,x60,x61,x62,x63) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) -> if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) logarithm{0,0}(x) -> logIter{0,0}(x,0{0,0}()) logIter{0,0}(x,y) -> if{0,0}(s{1,0}(0{0,0}(),x),s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) if{0,0}(false{0,0}(),b,x,y) -> logZeroError{0,0}() if{0,0}(true{0,0}(),false{0,0}(),x,s{0,0}(y)) -> y if{0,0}(true{0,0}(),true{0,0}(),x,y) -> logIter{0,0}(x,y) f{0,0}() -> g{0,0}() f{0,0}() -> h{0,0}() le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) Usable Rule Processor: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) -> s1_if{0,#}_1#(x59,x60,x61,x62,x63) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) -> if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) Arctic Interpretation Processor: dimension: 1 usable rules: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) interpretation: [inc{0,0}](x0) = 6x0 + 3, [0{0,0}] = 0, [false{0,0}] = 0, [s1_if{0,#}_1#](x0, x1, x2, x3, x4) = 6x0 + 6, [0{1,0}](x0) = 0, [le0](x0, x1) = x0, [logIter{0,0,#}](x0, x1) = 6, [true0_if{0,#}_1#](x0, x1, x2) = 6, [if{0,#}](x0, x1, x2, x3) = 6x0 + 0, [half{0,0}](x0) = 2x0, [s{0,0}](x0) = 1x0 + 1, [true{0,0}] = 0, [s{1,0}](x0, x1) = 1x0 + 1 orientation: if{0,#}(true{0,0}(),x64,x65,x66) = 6 >= 6 = true0_if{0,#}_1#(x64,x65,x66) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) = 7x59 + 7 >= 6x59 + 6 = s1_if{0,#}_1#(x59,x60,x61,x62,x63) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) = 6x + 6 >= 6 = if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) = 6x + 6 >= 6x + 0 = if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) = 6 >= 6 = logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) = 6 >= 6 = s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) le0(0{0,0}(),x18) = 0 >= 0 = 0{1,0}(x18) le0(s{0,0}(x20),x21) = 1x20 + 1 >= 1x20 + 1 = s{1,0}(x20,x21) 0{1,0}(y) = 0 >= 0 = true{0,0}() s{1,0}(x,0{0,0}()) = 1x + 1 >= 0 = false{0,0}() s{1,0}(x,s{0,0}(y)) = 1x + 1 >= x = le0(x,y) inc{0,0}(s{0,0}(x)) = 7x + 7 >= 7x + 4 = s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) = 6 >= 1 = s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) = 2 >= 0 = 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) = 3 >= 0 = 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) = 4x + 4 >= 3x + 1 = s{0,0}(half{0,0}(x)) problem: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) -> if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) Restore Modifier: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) -> if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) logarithm{0,0}(x) -> logIter{0,0}(x,0{0,0}()) logIter{0,0}(x,y) -> if{0,0}(s{1,0}(0{0,0}(),x),s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) if{0,0}(false{0,0}(),b,x,y) -> logZeroError{0,0}() if{0,0}(true{0,0}(),false{0,0}(),x,s{0,0}(y)) -> y if{0,0}(true{0,0}(),true{0,0}(),x,y) -> logIter{0,0}(x,y) f{0,0}() -> g{0,0}() f{0,0}() -> h{0,0}() le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) Usable Rule Processor: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) -> if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) Matrix Interpretation Processor: dim=3 usable rules: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) interpretation: [0] [inc{0,0}](x0) = [0] [0], [0] [0{0,0}] = [0] [0], [0] [false{0,0}] = [0] [0], [s1_if{0,#}_1#](x0, x1, x2, x3, x4) = [1 0 0]x2 + [1], [0] [0{1,0}](x0) = [1] [0], [0] [le0](x0, x1) = [1] [0], [logIter{0,0,#}](x0, x1) = [1], [true0_if{0,#}_1#](x0, x1, x2) = [1], [if{0,#}](x0, x1, x2, x3) = [0 1 0]x0 + [1 0 0]x1, [0 0 0] [0] [half{0,0}](x0) = [1 0 0]x0 + [1] [0 0 0] [0], [1 1 1] [0] [s{0,0}](x0) = [0 0 0]x0 + [1] [0 1 1] [0], [0] [true{0,0}] = [1] [0], [0] [s{1,0}](x0, x1) = [1] [0] orientation: if{0,#}(true{0,0}(),x64,x65,x66) = [1 0 0]x64 + [1] >= [1] = true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) = [1 0 0]x53 + [1] >= [1 0 0]x53 = if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) = [1 0 0]x56 + [1] >= [1 0 0]x56 + [1] = if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) = [1] >= [1] = logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) = [1] >= [1] = s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) [0] [0] le0(0{0,0}(),x18) = [1] >= [1] = 0{1,0}(x18) [0] [0] [0] [0] le0(s{0,0}(x20),x21) = [1] >= [1] = s{1,0}(x20,x21) [0] [0] [0] [0] 0{1,0}(y) = [1] >= [1] = true{0,0}() [0] [0] [0] [0] s{1,0}(x,0{0,0}()) = [1] >= [0] = false{0,0}() [0] [0] [0] [0] s{1,0}(x,s{0,0}(y)) = [1] >= [1] = le0(x,y) [0] [0] [0] [0] inc{0,0}(s{0,0}(x)) = [0] >= [1] = s{0,0}(inc{0,0}(x)) [0] [0] [0] [0] inc{0,0}(0{0,0}()) = [0] >= [1] = s{0,0}(0{0,0}()) [0] [0] [0] [0] half{0,0}(0{0,0}()) = [1] >= [0] = 0{0,0}() [0] [0] [0] [0] half{0,0}(s{0,0}(0{0,0}())) = [1] >= [0] = 0{0,0}() [0] [0] [0 0 0] [0] [1 0 0] [1] half{0,0}(s{0,0}(s{0,0}(x))) = [1 2 2]x + [2] >= [0 0 0]x + [1] = s{0,0}(half{0,0}(x)) [0 0 0] [0] [1 0 0] [1] problem: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) Restore Modifier: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) logarithm{0,0}(x) -> logIter{0,0}(x,0{0,0}()) logIter{0,0}(x,y) -> if{0,0}(s{1,0}(0{0,0}(),x),s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) if{0,0}(false{0,0}(),b,x,y) -> logZeroError{0,0}() if{0,0}(true{0,0}(),false{0,0}(),x,s{0,0}(y)) -> y if{0,0}(true{0,0}(),true{0,0}(),x,y) -> logIter{0,0}(x,y) f{0,0}() -> g{0,0}() f{0,0}() -> h{0,0}() le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) Usable Rule Processor: DPs: if{0,#}(true{0,0}(),x64,x65,x66) -> true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) Matrix Interpretation Processor: dim=1 usable rules: half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) interpretation: [inc{0,0}](x0) = 0, [0{0,0}] = 0, [false{0,0}] = 0, [s1_if{0,#}_1#](x0, x1, x2, x3, x4) = 1/2x1 + x3, [0{1,0}](x0) = 0, [le0](x0, x1) = 0, [logIter{0,0,#}](x0, x1) = x0, [true0_if{0,#}_1#](x0, x1, x2) = x1, [if{0,#}](x0, x1, x2, x3) = x2 + 1/2, [half{0,0}](x0) = 1/2x0, [s{0,0}](x0) = x0 + 1, [true{0,0}] = 0, [s{1,0}](x0, x1) = 1 orientation: if{0,#}(true{0,0}(),x64,x65,x66) = x65 + 1/2 >= x65 = true0_if{0,#}_1#(x64,x65,x66) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) = x57 + 1/2y + 1/2 >= x57 + 1/2 = if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) = x >= x = logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) = x >= x = s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) le0(0{0,0}(),x18) = 0 >= 0 = 0{1,0}(x18) le0(s{0,0}(x20),x21) = 0 >= 1 = s{1,0}(x20,x21) 0{1,0}(y) = 0 >= 0 = true{0,0}() s{1,0}(x,0{0,0}()) = 1 >= 0 = false{0,0}() s{1,0}(x,s{0,0}(y)) = 1 >= 0 = le0(x,y) inc{0,0}(s{0,0}(x)) = 0 >= 1 = s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) = 0 >= 1 = s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) = 0 >= 0 = 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) = 1/2 >= 0 = 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) = 1/2x + 1 >= 1/2x + 1 = s{0,0}(half{0,0}(x)) problem: DPs: s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) Restore Modifier: DPs: s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) -> if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) -> logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) -> s1_if{0,#}_1#(0{0,0}(),x,s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) TRS: half{0,0}(0{0,0}()) -> 0{0,0}() half{0,0}(s{0,0}(0{0,0}())) -> 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) -> s{0,0}(half{0,0}(x)) 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) inc{0,0}(s{0,0}(x)) -> s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) -> s{0,0}(0{0,0}()) logarithm{0,0}(x) -> logIter{0,0}(x,0{0,0}()) logIter{0,0}(x,y) -> if{0,0}(s{1,0}(0{0,0}(),x),s{1,0}(s{0,0}(0{0,0}()),x),half{0,0}(x),inc{0,0}(y)) if{0,0}(false{0,0}(),b,x,y) -> logZeroError{0,0}() if{0,0}(true{0,0}(),false{0,0}(),x,s{0,0}(y)) -> y if{0,0}(true{0,0}(),true{0,0}(),x,y) -> logIter{0,0}(x,y) f{0,0}() -> g{0,0}() f{0,0}() -> h{0,0}() le0(0{0,0}(),x18) -> 0{1,0}(x18) le0(s{0,0}(x20),x21) -> s{1,0}(x20,x21) SCC Processor: #sccs: 0 #rules: 0 #arcs: 2/9 DPs: le#(s(x),s(y)) -> le#(x,y) TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Subterm Criterion Processor: simple projection: pi(le#) = 0 problem: DPs: TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Qed DPs: half#(s(s(x))) -> half#(x) TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Subterm Criterion Processor: simple projection: pi(half#) = 0 problem: DPs: TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Qed DPs: inc#(s(x)) -> inc#(x) TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Subterm Criterion Processor: simple projection: pi(inc#) = 0 problem: DPs: TRS: half(0()) -> 0() half(s(0())) -> 0() half(s(s(x))) -> s(half(x)) le(0(),y) -> true() le(s(x),0()) -> false() le(s(x),s(y)) -> le(x,y) inc(s(x)) -> s(inc(x)) inc(0()) -> s(0()) logarithm(x) -> logIter(x,0()) logIter(x,y) -> if(le(s(0()),x),le(s(s(0())),x),half(x),inc(y)) if(false(),b,x,y) -> logZeroError() if(true(),false(),x,s(y)) -> y if(true(),true(),x,y) -> logIter(x,y) f() -> g() f() -> h() Qed