/export/starexec/sandbox/solver/bin/starexec_run_tct_rci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),O(n^1)) * Step 1: Sum. WORST_CASE(Omega(n^1),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: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: Sum. WORST_CASE(Omega(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: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:2: DecreasingLoops. WORST_CASE(Omega(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: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: even(z){z -> Cons(x,Cons(y,z))} = even(Cons(x,Cons(y,z))) ->^+ even(z) = C[even(z) = even(z){}] ** Step 1.b:1: NaturalMI. 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: 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] x2 + [3] p(False) = [0] p(Nil) = [4] p(True) = [0] p(and) = [1] x1 + [1] x2 + [9] p(even) = [4] x1 + [2] p(goal) = [8] x1 + [3] x2 + [15] p(lte) = [3] x1 + [2] x2 + [4] p(notEmpty) = [2] Following rules are strictly oriented: even(Cons(x,Nil())) = [30] > [0] = False() even(Cons(x',Cons(x,xs))) = [4] xs + [26] > [4] xs + [2] = even(xs) even(Nil()) = [18] > [0] = True() lte(Cons(x,xs),Nil()) = [3] xs + [21] > [0] = False() lte(Cons(x',xs'),Cons(x,xs)) = [2] xs + [3] xs' + [19] > [2] xs + [3] xs' + [4] = lte(xs',xs) lte(Nil(),y) = [2] y + [16] > [0] = True() notEmpty(Cons(x,xs)) = [2] > [0] = True() notEmpty(Nil()) = [2] > [0] = False() Following rules are (at-least) weakly oriented: and(False(),False()) = [9] >= [0] = False() and(False(),True()) = [9] >= [0] = False() and(True(),False()) = [9] >= [0] = False() and(True(),True()) = [9] >= [0] = True() goal(x,y) = [8] x + [3] y + [15] >= [7] x + [2] y + [15] = and(lte(x,y),even(x)) ** Step 1.b:2: NaturalPI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: goal(x,y) -> and(lte(x,y),even(x)) - 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() 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: NaturalPI {shape = Linear, restrict = Restrict, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a polynomial interpretation of kind constructor-based(linear): 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) = x1 p(False) = 0 p(Nil) = 3 p(True) = 0 p(and) = x1 + x2 p(even) = 12 p(goal) = 14 + 2*x1 + x2 p(lte) = 0 p(notEmpty) = 9*x1 Following rules are strictly oriented: goal(x,y) = 14 + 2*x + y > 12 = 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())) = 12 >= 0 = False() even(Cons(x',Cons(x,xs))) = 12 >= 12 = even(xs) even(Nil()) = 12 >= 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)) = 9*x >= 0 = True() notEmpty(Nil()) = 27 >= 0 = False() ** Step 1.b:3: 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(Omega(n^1),O(n^1))