/export/starexec/sandbox2/solver/bin/starexec_run_ttt2 /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- 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)) Matrix Interpretation Processor: dim=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) 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}()) interpretation: [inc{0,0}](x0) = x0 + 7, [0{0,0}] = 0, [false{0,0}] = 0, [s1_if{0,#}_1#](x0, x1, x2, x3, x4) = 4x0 + 4, [0{1,0}](x0) = 1, [le0](x0, x1) = x0 + 1, [logIter{0,0,#}](x0, x1) = 4, [true0_if{0,#}_1#](x0, x1, x2) = 4, [if{0,#}](x0, x1, x2, x3) = 4x0, [half{0,0}](x0) = 0, [s{0,0}](x0) = x0 + 7, [true{0,0}] = 1, [s{1,0}](x0, x1) = x0 + 1 orientation: if{0,#}(true{0,0}(),x64,x65,x66) = 4 >= 4 = true0_if{0,#}_1#(x64,x65,x66) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) = 4x59 + 4 >= 4x59 + 4 = s1_if{0,#}_1#(x59,x60,x61,x62,x63) s1_if{0,#}_1#(x,0{0,0}(),x53,x54,x55) = 4x + 4 >= 0 = if{0,#}(false{0,0}(),x53,x54,x55) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) = 4x + 4 >= 4x + 4 = if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) = 4 >= 4 = logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) = 4 >= 4 = 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) = 1 >= 1 = 0{1,0}(x18) le0(s{0,0}(x20),x21) = x20 + 8 >= x20 + 1 = s{1,0}(x20,x21) 0{1,0}(y) = 1 >= 1 = true{0,0}() s{1,0}(x,0{0,0}()) = x + 1 >= 0 = false{0,0}() s{1,0}(x,s{0,0}(y)) = x + 1 >= x + 1 = le0(x,y) inc{0,0}(s{0,0}(x)) = x + 14 >= x + 14 = s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) = 7 >= 7 = 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}())) = 0 >= 0 = 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) = 0 >= 7 = s{0,0}(half{0,0}(x)) 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,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) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) -> s1_if{0,#}_1#(x59,x60,x61,x62,x63) 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,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: 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) = 4x0, [0{0,0}] = 0, [false{0,0}] = 0, [s1_if{0,#}_1#](x0, x1, x2, x3, x4) = 4x0, [0{1,0}](x0) = 0, [le0](x0, x1) = x0, [logIter{0,0,#}](x0, x1) = 0, [true0_if{0,#}_1#](x0, x1, x2) = 0, [if{0,#}](x0, x1, x2, x3) = 4x0, [half{0,0}](x0) = 0, [s{0,0}](x0) = 4x0 + 4, [true{0,0}] = 0, [s{1,0}](x0, x1) = 4x0 + 4 orientation: if{0,#}(true{0,0}(),x64,x65,x66) = 0 >= 0 = true0_if{0,#}_1#(x64,x65,x66) if{0,#}(s{1,0}(x59,x60),x61,x62,x63) = 16x59 + 16 >= 4x59 = s1_if{0,#}_1#(x59,x60,x61,x62,x63) s1_if{0,#}_1#(x,s{0,0}(y),x56,x57,x58) = 4x >= 4x = if{0,#}(le0(x,y),x56,x57,x58) true0_if{0,#}_1#(true{0,0}(),x,y) = 0 >= 0 = logIter{0,0,#}(x,y) logIter{0,0,#}(x,y) = 0 >= 0 = 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) = 4x20 + 4 >= 4x20 + 4 = s{1,0}(x20,x21) 0{1,0}(y) = 0 >= 0 = true{0,0}() s{1,0}(x,0{0,0}()) = 4x + 4 >= 0 = false{0,0}() s{1,0}(x,s{0,0}(y)) = 4x + 4 >= x = le0(x,y) inc{0,0}(s{0,0}(x)) = 16x + 16 >= 16x + 4 = s{0,0}(inc{0,0}(x)) inc{0,0}(0{0,0}()) = 0 >= 4 = 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}())) = 0 >= 0 = 0{0,0}() half{0,0}(s{0,0}(s{0,0}(x))) = 0 >= 4 = 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,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