WORST_CASE(?,O(n^2)) * Step 1: NaturalMI 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: 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(loop[Ite]) = {1} Following symbols are considered usable: {!EQ,loop,loop[Ite],match1} TcT has computed the following interpretation: p(!EQ) = [0] p(0) = [0] p(Cons) = [1] p(False) = [0] p(Nil) = [1] p(S) = [0] p(True) = [0] p(loop) = [8] p(loop[Ite]) = [1] x1 + [8] p(match1) = [8] Following rules are strictly oriented: loop(Cons(x,xs),Nil(),pp,ss) = [8] > [0] = False() loop(Nil(),s,pp,ss) = [8] > [0] = True() Following rules are (at-least) weakly oriented: !EQ(0(),0()) = [0] >= [0] = True() !EQ(0(),S(y)) = [0] >= [0] = False() !EQ(S(x),0()) = [0] >= [0] = False() !EQ(S(x),S(y)) = [0] >= [0] = !EQ(x,y) loop(Cons(x',xs'),Cons(x,xs),pp,ss) = [8] >= [8] = loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop[Ite](False(),p,s,pp,Cons(x,xs)) = [8] >= [8] = loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) = [8] >= [8] = loop(xs',xs,pp,ss) match1(p,s) = [8] >= [8] = loop(p,s,p,s) * Step 2: NaturalMI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) 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(Cons(x,xs),Nil(),pp,ss) -> False() 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) - 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: 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(loop[Ite]) = {1} Following symbols are considered usable: {!EQ,loop,loop[Ite],match1} TcT has computed the following interpretation: p(!EQ) = [7] p(0) = [1] p(Cons) = [1] p(False) = [7] p(Nil) = [0] p(S) = [8] p(True) = [7] p(loop) = [7] p(loop[Ite]) = [1] x1 + [0] p(match1) = [15] Following rules are strictly oriented: match1(p,s) = [15] > [7] = loop(p,s,p,s) Following rules are (at-least) weakly oriented: !EQ(0(),0()) = [7] >= [7] = True() !EQ(0(),S(y)) = [7] >= [7] = False() !EQ(S(x),0()) = [7] >= [7] = False() !EQ(S(x),S(y)) = [7] >= [7] = !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) = [7] >= [7] = False() loop(Cons(x',xs'),Cons(x,xs),pp,ss) = [7] >= [7] = loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) loop(Nil(),s,pp,ss) = [7] >= [7] = True() loop[Ite](False(),p,s,pp,Cons(x,xs)) = [7] >= [7] = loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) = [7] >= [7] = loop(xs',xs,pp,ss) * Step 3: NaturalPI WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: loop(Cons(x',xs'),Cons(x,xs),pp,ss) -> loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,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(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} / {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: NaturalPI {shape = Mixed 2, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(mixed(2)): The following argument positions are considered usable: uargs(loop[Ite]) = {1} Following symbols are considered usable: {!EQ,loop,loop[Ite],match1} TcT has computed the following interpretation: p(!EQ) = 0 p(0) = 0 p(Cons) = 1 + x2 p(False) = 0 p(Nil) = 0 p(S) = x1 p(True) = 0 p(loop) = 1 + 2*x1 + 2*x3*x4 + x4 p(loop[Ite]) = 2*x1 + 2*x1*x5 + 2*x2 + 2*x4*x5 + x5 p(match1) = 1 + 2*x1 + 3*x1*x2 + x1^2 + 2*x2 Following rules are strictly oriented: loop(Cons(x',xs'),Cons(x,xs),pp,ss) = 3 + 2*pp*ss + ss + 2*xs' > 2 + 2*pp*ss + ss + 2*xs' = loop[Ite](!EQ(x',x),Cons(x',xs'),Cons(x,xs),pp,ss) Following rules are (at-least) weakly oriented: !EQ(0(),0()) = 0 >= 0 = True() !EQ(0(),S(y)) = 0 >= 0 = False() !EQ(S(x),0()) = 0 >= 0 = False() !EQ(S(x),S(y)) = 0 >= 0 = !EQ(x,y) loop(Cons(x,xs),Nil(),pp,ss) = 3 + 2*pp*ss + ss + 2*xs >= 0 = False() loop(Nil(),s,pp,ss) = 1 + 2*pp*ss + ss >= 0 = True() loop[Ite](False(),p,s,pp,Cons(x,xs)) = 1 + 2*p + 2*pp + 2*pp*xs + xs >= 1 + 2*pp + 2*pp*xs + xs = loop(pp,xs,pp,xs) loop[Ite](True(),Cons(x',xs'),Cons(x,xs),pp,ss) = 2 + 2*pp*ss + ss + 2*xs' >= 1 + 2*pp*ss + ss + 2*xs' = loop(xs',xs,pp,ss) match1(p,s) = 1 + 2*p + 3*p*s + p^2 + 2*s >= 1 + 2*p + 2*p*s + s = loop(p,s,p,s) * Step 4: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - 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} / {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: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))