WORST_CASE(?,O(n^1)) * Step 1: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: even(Cons(x,Nil())) -> False() even(Cons(x',Cons(x,xs))) -> even(xs) even(Nil()) -> True() goal(x,y) -> and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) -> False() lte(Cons(x',xs'),Cons(x,xs)) -> lte(xs',xs) lte(Nil(),y) -> True() notEmpty(Cons(x,xs)) -> True() notEmpty(Nil()) -> False() - Weak TRS: and(False(),False()) -> False() and(False(),True()) -> False() and(True(),False()) -> False() and(True(),True()) -> True() - Signature: {and/2,even/1,goal/2,lte/2,notEmpty/1} / {Cons/2,False/0,Nil/0,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {and,even,goal,lte,notEmpty} and constructors {Cons,False ,Nil,True} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(and) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(Cons) = [1] x2 + [0] p(False) = [8] p(Nil) = [0] p(True) = [0] p(and) = [1] x1 + [1] x2 + [0] p(even) = [1] x1 + [5] p(goal) = [9] x1 + [0] p(lte) = [8] x1 + [0] p(notEmpty) = [11] Following rules are strictly oriented: even(Nil()) = [5] > [0] = True() notEmpty(Cons(x,xs)) = [11] > [0] = True() notEmpty(Nil()) = [11] > [8] = False() Following rules are (at-least) weakly oriented: and(False(),False()) = [16] >= [8] = False() and(False(),True()) = [8] >= [8] = False() and(True(),False()) = [8] >= [8] = False() and(True(),True()) = [0] >= [0] = True() even(Cons(x,Nil())) = [5] >= [8] = False() even(Cons(x',Cons(x,xs))) = [1] xs + [5] >= [1] xs + [5] = even(xs) goal(x,y) = [9] x + [0] >= [9] x + [5] = and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) = [8] xs + [0] >= [8] = False() lte(Cons(x',xs'),Cons(x,xs)) = [8] xs' + [0] >= [8] xs' + [0] = lte(xs',xs) lte(Nil(),y) = [0] >= [0] = True() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 2: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: even(Cons(x,Nil())) -> False() even(Cons(x',Cons(x,xs))) -> even(xs) goal(x,y) -> and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) -> False() lte(Cons(x',xs'),Cons(x,xs)) -> lte(xs',xs) lte(Nil(),y) -> True() - Weak TRS: and(False(),False()) -> False() and(False(),True()) -> False() and(True(),False()) -> False() and(True(),True()) -> True() even(Nil()) -> True() notEmpty(Cons(x,xs)) -> True() notEmpty(Nil()) -> False() - Signature: {and/2,even/1,goal/2,lte/2,notEmpty/1} / {Cons/2,False/0,Nil/0,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {and,even,goal,lte,notEmpty} and constructors {Cons,False ,Nil,True} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(and) = {1,2} Following symbols are considered usable: all TcT has computed the following interpretation: p(Cons) = [1] x1 + [1] p(False) = [0] p(Nil) = [2] p(True) = [8] p(and) = [1] x1 + [1] x2 + [1] p(even) = [13] p(goal) = [0] p(lte) = [2] p(notEmpty) = [8] x1 + [1] Following rules are strictly oriented: even(Cons(x,Nil())) = [13] > [0] = False() lte(Cons(x,xs),Nil()) = [2] > [0] = False() Following rules are (at-least) weakly oriented: and(False(),False()) = [1] >= [0] = False() and(False(),True()) = [9] >= [0] = False() and(True(),False()) = [9] >= [0] = False() and(True(),True()) = [17] >= [8] = True() even(Cons(x',Cons(x,xs))) = [13] >= [13] = even(xs) even(Nil()) = [13] >= [8] = True() goal(x,y) = [0] >= [16] = and(lte(x,y),even(x)) lte(Cons(x',xs'),Cons(x,xs)) = [2] >= [2] = lte(xs',xs) lte(Nil(),y) = [2] >= [8] = True() notEmpty(Cons(x,xs)) = [8] x + [9] >= [8] = True() notEmpty(Nil()) = [17] >= [0] = False() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: even(Cons(x',Cons(x,xs))) -> even(xs) goal(x,y) -> and(lte(x,y),even(x)) lte(Cons(x',xs'),Cons(x,xs)) -> lte(xs',xs) lte(Nil(),y) -> True() - Weak TRS: and(False(),False()) -> False() and(False(),True()) -> False() and(True(),False()) -> False() and(True(),True()) -> True() even(Cons(x,Nil())) -> False() even(Nil()) -> True() lte(Cons(x,xs),Nil()) -> False() notEmpty(Cons(x,xs)) -> True() notEmpty(Nil()) -> False() - Signature: {and/2,even/1,goal/2,lte/2,notEmpty/1} / {Cons/2,False/0,Nil/0,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {and,even,goal,lte,notEmpty} and constructors {Cons,False ,Nil,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(and) = {1,2} Following symbols are considered usable: {and,even,goal,lte,notEmpty} TcT has computed the following interpretation: p(Cons) = [1] x1 + [1] x2 + [0] p(False) = [0] p(Nil) = [0] p(True) = [0] p(and) = [4] x1 + [1] x2 + [0] p(even) = [6] p(goal) = [8] p(lte) = [0] p(notEmpty) = [0] Following rules are strictly oriented: goal(x,y) = [8] > [6] = and(lte(x,y),even(x)) Following rules are (at-least) weakly oriented: and(False(),False()) = [0] >= [0] = False() and(False(),True()) = [0] >= [0] = False() and(True(),False()) = [0] >= [0] = False() and(True(),True()) = [0] >= [0] = True() even(Cons(x,Nil())) = [6] >= [0] = False() even(Cons(x',Cons(x,xs))) = [6] >= [6] = even(xs) even(Nil()) = [6] >= [0] = True() lte(Cons(x,xs),Nil()) = [0] >= [0] = False() lte(Cons(x',xs'),Cons(x,xs)) = [0] >= [0] = lte(xs',xs) lte(Nil(),y) = [0] >= [0] = True() notEmpty(Cons(x,xs)) = [0] >= [0] = True() notEmpty(Nil()) = [0] >= [0] = False() * Step 4: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: even(Cons(x',Cons(x,xs))) -> even(xs) lte(Cons(x',xs'),Cons(x,xs)) -> lte(xs',xs) lte(Nil(),y) -> True() - Weak TRS: and(False(),False()) -> False() and(False(),True()) -> False() and(True(),False()) -> False() and(True(),True()) -> True() even(Cons(x,Nil())) -> False() even(Nil()) -> True() goal(x,y) -> and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) -> False() notEmpty(Cons(x,xs)) -> True() notEmpty(Nil()) -> False() - Signature: {and/2,even/1,goal/2,lte/2,notEmpty/1} / {Cons/2,False/0,Nil/0,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {and,even,goal,lte,notEmpty} and constructors {Cons,False ,Nil,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(and) = {1,2} Following symbols are considered usable: {and,even,goal,lte,notEmpty} TcT has computed the following interpretation: p(Cons) = [0] p(False) = [0] p(Nil) = [8] p(True) = [0] p(and) = [1] x1 + [1] x2 + [1] p(even) = [1] p(goal) = [12] p(lte) = [8] p(notEmpty) = [12] Following rules are strictly oriented: lte(Nil(),y) = [8] > [0] = True() Following rules are (at-least) weakly oriented: and(False(),False()) = [1] >= [0] = False() and(False(),True()) = [1] >= [0] = False() and(True(),False()) = [1] >= [0] = False() and(True(),True()) = [1] >= [0] = True() even(Cons(x,Nil())) = [1] >= [0] = False() even(Cons(x',Cons(x,xs))) = [1] >= [1] = even(xs) even(Nil()) = [1] >= [0] = True() goal(x,y) = [12] >= [10] = and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) = [8] >= [0] = False() lte(Cons(x',xs'),Cons(x,xs)) = [8] >= [8] = lte(xs',xs) notEmpty(Cons(x,xs)) = [12] >= [0] = True() notEmpty(Nil()) = [12] >= [0] = False() * Step 5: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: even(Cons(x',Cons(x,xs))) -> even(xs) lte(Cons(x',xs'),Cons(x,xs)) -> lte(xs',xs) - Weak TRS: and(False(),False()) -> False() and(False(),True()) -> False() and(True(),False()) -> False() and(True(),True()) -> True() even(Cons(x,Nil())) -> False() even(Nil()) -> True() goal(x,y) -> and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) -> False() lte(Nil(),y) -> True() notEmpty(Cons(x,xs)) -> True() notEmpty(Nil()) -> False() - Signature: {and/2,even/1,goal/2,lte/2,notEmpty/1} / {Cons/2,False/0,Nil/0,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {and,even,goal,lte,notEmpty} and constructors {Cons,False ,Nil,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(and) = {1,2} Following symbols are considered usable: {and,even,goal,lte,notEmpty} TcT has computed the following interpretation: p(Cons) = [1] x1 + [1] x2 + [4] p(False) = [3] p(Nil) = [1] p(True) = [0] p(and) = [1] x1 + [1] x2 + [2] p(even) = [2] x1 + [2] p(goal) = [4] x1 + [8] x2 + [4] p(lte) = [2] x1 + [0] p(notEmpty) = [8] Following rules are strictly oriented: even(Cons(x',Cons(x,xs))) = [2] x + [2] x' + [2] xs + [18] > [2] xs + [2] = even(xs) lte(Cons(x',xs'),Cons(x,xs)) = [2] x' + [2] xs' + [8] > [2] xs' + [0] = lte(xs',xs) Following rules are (at-least) weakly oriented: and(False(),False()) = [8] >= [3] = False() and(False(),True()) = [5] >= [3] = False() and(True(),False()) = [5] >= [3] = False() and(True(),True()) = [2] >= [0] = True() even(Cons(x,Nil())) = [2] x + [12] >= [3] = False() even(Nil()) = [4] >= [0] = True() goal(x,y) = [4] x + [8] y + [4] >= [4] x + [4] = and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) = [2] x + [2] xs + [8] >= [3] = False() lte(Nil(),y) = [2] >= [0] = True() notEmpty(Cons(x,xs)) = [8] >= [0] = True() notEmpty(Nil()) = [8] >= [3] = False() * Step 6: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: and(False(),False()) -> False() and(False(),True()) -> False() and(True(),False()) -> False() and(True(),True()) -> True() even(Cons(x,Nil())) -> False() even(Cons(x',Cons(x,xs))) -> even(xs) even(Nil()) -> True() goal(x,y) -> and(lte(x,y),even(x)) lte(Cons(x,xs),Nil()) -> False() lte(Cons(x',xs'),Cons(x,xs)) -> lte(xs',xs) lte(Nil(),y) -> True() notEmpty(Cons(x,xs)) -> True() notEmpty(Nil()) -> False() - Signature: {and/2,even/1,goal/2,lte/2,notEmpty/1} / {Cons/2,False/0,Nil/0,True/0} - Obligation: innermost runtime complexity wrt. defined symbols {and,even,goal,lte,notEmpty} and constructors {Cons,False ,Nil,True} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))