/export/starexec/sandbox/solver/bin/starexec_run_tct_rci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^2)) * Step 1: Sum. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() match1(p,s) -> loop(p,s,p,s) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ,loop,loop[Ite],match1} and constructors {0,Cons,False ,Nil,S,True} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DependencyPairs. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() match1(p,s) -> loop(p,s,p,s) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2} / {0/0,Cons/2,False/0,Nil/0,S/1,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ,loop,loop[Ite],match1} and constructors {0,Cons,False ,Nil,S,True} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss),!EQ#(x',x)) loop#(Nil(),s,pp,ss) -> c_3() match1#(p,s) -> c_4(loop#(p,s,p,s)) Weak DPs !EQ#(0(),0()) -> c_5() !EQ#(0(),S(y)) -> c_6() !EQ#(S(x),0()) -> c_7() !EQ#(S(x),S(y)) -> c_8(!EQ#(x,y)) loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) and mark the set of starting terms. * Step 3: RemoveWeakSuffixes. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss),!EQ#(x',x)) loop#(Nil(),s,pp,ss) -> c_3() match1#(p,s) -> c_4(loop#(p,s,p,s)) - Weak DPs: !EQ#(0(),0()) -> c_5() !EQ#(0(),S(y)) -> c_6() !EQ#(S(x),0()) -> c_7() !EQ#(S(x),S(y)) -> c_8(!EQ#(x,y)) loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) match1(p,s) -> loop(p,s,p,s) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2,!EQ#/2,loop#/4,loop[Ite]#/5,match1#/2} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0,c_1/0,c_2/2,c_3/0,c_4/1,c_5/0,c_6/0,c_7/0,c_8/1,c_9/1,c_10/1} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ#,loop#,loop[Ite]#,match1#} and constructors {0,Cons ,False,Nil,S,True} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() 2:S:loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)) -->_1 loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)):10 -->_1 loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)):9 -->_2 !EQ#(S(x),S(y)) -> c_8(!EQ#(x,y)):8 -->_2 !EQ#(S(x),0()) -> c_7():7 -->_2 !EQ#(0(),S(y)) -> c_6():6 -->_2 !EQ#(0(),0()) -> c_5():5 3:S:loop#(Nil(),s,pp,ss) -> c_3() 4:S:match1#(p,s) -> c_4(loop#(p,s,p,s)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 5:W:!EQ#(0(),0()) -> c_5() 6:W:!EQ#(0(),S(y)) -> c_6() 7:W:!EQ#(S(x),0()) -> c_7() 8:W:!EQ#(S(x),S(y)) -> c_8(!EQ#(x,y)) -->_1 !EQ#(S(x),S(y)) -> c_8(!EQ#(x,y)):8 -->_1 !EQ#(S(x),0()) -> c_7():7 -->_1 !EQ#(0(),S(y)) -> c_6():6 -->_1 !EQ#(0(),0()) -> c_5():5 9:W:loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 10:W:loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 8: !EQ#(S(x),S(y)) -> c_8(!EQ#(x,y)) 5: !EQ#(0(),0()) -> c_5() 6: !EQ#(0(),S(y)) -> c_6() 7: !EQ#(S(x),0()) -> c_7() * Step 4: SimplifyRHS. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss),!EQ#(x',x)) loop#(Nil(),s,pp,ss) -> c_3() match1#(p,s) -> c_4(loop#(p,s,p,s)) - Weak DPs: loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) match1(p,s) -> loop(p,s,p,s) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2,!EQ#/2,loop#/4,loop[Ite]#/5,match1#/2} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0,c_1/0,c_2/2,c_3/0,c_4/1,c_5/0,c_6/0,c_7/0,c_8/1,c_9/1,c_10/1} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ#,loop#,loop[Ite]#,match1#} and constructors {0,Cons ,False,Nil,S,True} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() 2:S:loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)) -->_1 loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)):10 -->_1 loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)):9 3:S:loop#(Nil(),s,pp,ss) -> c_3() 4:S:match1#(p,s) -> c_4(loop#(p,s,p,s)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 9:W:loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 10:W:loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) ,!EQ#(x',x)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) * Step 5: UsableRules. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) loop#(Nil(),s,pp,ss) -> c_3() match1#(p,s) -> c_4(loop#(p,s,p,s)) - Weak DPs: loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) -> False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) -> True() loop[Ite](False(),p,s,pp,Cons(x,xs)) -> loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> loop(xs',xs,pp,ss) match1(p,s) -> loop(p,s,p,s) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2,!EQ#/2,loop#/4,loop[Ite]#/5,match1#/2} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0,c_1/0,c_2/1,c_3/0,c_4/1,c_5/0,c_6/0,c_7/0,c_8/1,c_9/1,c_10/1} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ#,loop#,loop[Ite]#,match1#} and constructors {0,Cons ,False,Nil,S,True} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) loop#(Nil(),s,pp,ss) -> c_3() loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) match1#(p,s) -> c_4(loop#(p,s,p,s)) * Step 6: RemoveHeads. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) loop#(Nil(),s,pp,ss) -> c_3() match1#(p,s) -> c_4(loop#(p,s,p,s)) - Weak DPs: loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2,!EQ#/2,loop#/4,loop[Ite]#/5,match1#/2} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0,c_1/0,c_2/1,c_3/0,c_4/1,c_5/0,c_6/0,c_7/0,c_8/1,c_9/1,c_10/1} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ#,loop#,loop[Ite]#,match1#} and constructors {0,Cons ,False,Nil,S,True} + Applied Processor: RemoveHeads + Details: Consider the dependency graph 1:S:loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() 2:S:loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) -->_1 loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)):6 -->_1 loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)):5 3:S:loop#(Nil(),s,pp,ss) -> c_3() 4:S:match1#(p,s) -> c_4(loop#(p,s,p,s)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 5:W:loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 6:W:loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) -->_1 loop#(Nil(),s,pp,ss) -> c_3():3 -->_1 loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)):2 -->_1 loop#(Cons(x,xs),Nil(),pp,ss) -> c_1():1 Following roots of the dependency graph are removed, as the considered set of starting terms is closed under reduction with respect to these rules (modulo compound contexts). [(4,match1#(p,s) -> c_4(loop#(p,s,p,s)))] * Step 7: NaturalMI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) loop#(Nil(),s,pp,ss) -> c_3() - Weak DPs: loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2,!EQ#/2,loop#/4,loop[Ite]#/5,match1#/2} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0,c_1/0,c_2/1,c_3/0,c_4/1,c_5/0,c_6/0,c_7/0,c_8/1,c_9/1,c_10/1} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ#,loop#,loop[Ite]#,match1#} and constructors {0,Cons ,False,Nil,S,True} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(c_2) = {1}, uargs(c_9) = {1}, uargs(c_10) = {1} Following symbols are considered usable: {!EQ#,loop#,loop[Ite]#,match1#} TcT has computed the following interpretation: p(!EQ) = [13] x2 + [5] p(0) = [0] p(Cons) = [1] x1 + [1] x2 + [0] p(False) = [0] p(Nil) = [0] p(S) = [2] p(True) = [0] p(loop) = [0] p(loop[Ite]) = [0] p(match1) = [0] p(!EQ#) = [0] p(loop#) = [9] p(loop[Ite]#) = [9] p(match1#) = [0] p(c_1) = [3] p(c_2) = [1] x1 + [0] p(c_3) = [6] p(c_4) = [1] x1 + [0] p(c_5) = [2] p(c_6) = [1] p(c_7) = [1] p(c_8) = [1] p(c_9) = [1] x1 + [0] p(c_10) = [1] x1 + [0] Following rules are strictly oriented: loop#(Cons(x,xs),Nil(),pp,ss) = [9] > [3] = c_1() loop#(Nil(),s,pp,ss) = [9] > [6] = c_3() Following rules are (at-least) weakly oriented: loop#(Cons(x',xs'),Cons(x,xs),pp,ss) = [9] >= [9] = c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) loop[Ite]#(False(),p,s,pp,Cons(x,xs)) = [9] >= [9] = c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) = [9] >= [9] = c_10(loop#(xs',xs,pp,ss)) * Step 8: Ara. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) - Weak DPs: loop#(Cons(x,xs),Nil(),pp,ss) -> c_1() loop#(Nil(),s,pp,ss) -> c_3() loop[Ite]#(False(),p,s,pp,Cons(x,xs)) -> c_9(loop#(pp,xs,pp,xs)) loop[Ite]#(True(),Cons(x',xs'),Cons(x,xs),pp,ss) -> c_10(loop#(xs',xs,pp,ss)) - Weak TRS: !EQ(0(),0()) -> True() !EQ(0(),S(y)) -> False() !EQ(S(x),0()) -> False() !EQ(S(x),S(y)) -> !EQ(x,y) - Signature: {!EQ/2,loop/4,loop[Ite]/5,match1/2,!EQ#/2,loop#/4,loop[Ite]#/5,match1#/2} / {0/0,Cons/2,False/0,Nil/0,S/1 ,True/0,c_1/0,c_2/1,c_3/0,c_4/1,c_5/0,c_6/0,c_7/0,c_8/1,c_9/1,c_10/1} - Obligation: innermost runtime complexity wrt. defined symbols {!EQ#,loop#,loop[Ite]#,match1#} and constructors {0,Cons ,False,Nil,S,True} + Applied Processor: Ara {minDegree = 1, maxDegree = 2, araTimeout = 8, araRuleShifting = Just 1, isBestCase = False, mkCompletelyDefined = False, verboseOutput = False} + Details: Signatures used: ---------------- F (TrsFun "!EQ") :: ["A"(0, 0) x "A"(0, 0)] -(0)-> "A"(0, 0) F (TrsFun "0") :: [] -(0)-> "A"(0, 0) F (TrsFun "Cons") :: ["A"(0, 0) x "A"(0, 0)] -(0)-> "A"(0, 0) F (TrsFun "Cons") :: ["A"(0, 0) x "A"(3, 0)] -(3)-> "A"(3, 0) F (TrsFun "Cons") :: ["A"(0, 0) x "A"(11, 3)] -(8)-> "A"(8, 3) F (TrsFun "False") :: [] -(0)-> "A"(0, 0) F (TrsFun "Nil") :: [] -(0)-> "A"(3, 0) F (TrsFun "Nil") :: [] -(0)-> "A"(0, 0) F (TrsFun "S") :: ["A"(0, 0)] -(0)-> "A"(0, 0) F (TrsFun "True") :: [] -(0)-> "A"(0, 0) F (DpFun "loop") :: ["A"(0, 0) x "A"(3, 0) x "A"(15, 15) x "A"(8, 3)] -(10)-> "A"(1, 1) F (DpFun "loop[Ite]") :: ["A"(0, 0) x "A"(0, 0) x "A"(3, 0) x "A"(15, 15) x "A"(8, 3)] -(7)-> "A"(8, 1) F (ComFun 1) :: [] -(0)-> "A"(1, 1) F (ComFun 2) :: ["A"(0, 0)] -(0)-> "A"(3, 3) F (ComFun 3) :: [] -(0)-> "A"(1, 1) F (ComFun 9) :: ["A"(0, 0)] -(0)-> "A"(10, 7) F (ComFun 10) :: ["A"(1, 1)] -(0)-> "A"(9, 1) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "F (ComFun 1)_A" :: [] -(0)-> "A"(1, 0) "F (ComFun 1)_A" :: [] -(0)-> "A"(0, 1) "F (ComFun 10)_A" :: ["A"(0, 0)] -(0)-> "A"(1, 0) "F (ComFun 10)_A" :: ["A"(1, 1)] -(0)-> "A"(0, 1) "F (ComFun 2)_A" :: ["A"(0, 0)] -(0)-> "A"(1, 0) "F (ComFun 2)_A" :: ["A"(0, 0)] -(0)-> "A"(0, 1) "F (ComFun 3)_A" :: [] -(0)-> "A"(1, 0) "F (ComFun 3)_A" :: [] -(0)-> "A"(0, 1) "F (ComFun 9)_A" :: ["A"(0, 0)] -(0)-> "A"(1, 0) "F (ComFun 9)_A" :: ["A"(0, 0)] -(0)-> "A"(0, 1) "F (TrsFun \"0\")_A" :: [] -(0)-> "A"(1, 0) "F (TrsFun \"0\")_A" :: [] -(0)-> "A"(0, 1) "F (TrsFun \"Cons\")_A" :: ["A"(0, 0) x "A"(1, 0)] -(1)-> "A"(1, 0) "F (TrsFun \"Cons\")_A" :: ["A"(0, 0) x "A"(1, 1)] -(0)-> "A"(0, 1) "F (TrsFun \"False\")_A" :: [] -(0)-> "A"(1, 0) "F (TrsFun \"False\")_A" :: [] -(0)-> "A"(0, 1) "F (TrsFun \"Nil\")_A" :: [] -(0)-> "A"(1, 0) "F (TrsFun \"Nil\")_A" :: [] -(0)-> "A"(0, 1) "F (TrsFun \"S\")_A" :: ["A"(1, 0)] -(1)-> "A"(1, 0) "F (TrsFun \"S\")_A" :: ["A"(1, 1)] -(1)-> "A"(0, 1) "F (TrsFun \"True\")_A" :: [] -(0)-> "A"(1, 0) "F (TrsFun \"True\")_A" :: [] -(0)-> "A"(0, 1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: loop#(Cons(x',xs'),Cons(x,xs),pp,ss) -> c_2(loop[Ite]#(!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss)) 2. Weak: WORST_CASE(?,O(n^2))