/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^3)) * Step 1: Sum WORST_CASE(Omega(n^1),O(n^3)) + Considered Problem: - Strict TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n - Signature: {sum/2,weight/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {sum,weight} and constructors {0,cons,nil,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: DecreasingLoops WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n - Signature: {sum/2,weight/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {sum,weight} and constructors {0,cons,nil,s} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: sum(x,y){x -> cons(0(),x)} = sum(cons(0(),x),y) ->^+ sum(x,y) = C[sum(x,y) = sum(x,y){}] ** Step 1.b:1: DependencyPairs WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n - Signature: {sum/2,weight/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {sum,weight} and constructors {0,cons,nil,s} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) sum#(nil(),y) -> c_3() weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) weight#(cons(n,nil())) -> c_5() Weak DPs and mark the set of starting terms. ** Step 1.b:2: PredecessorEstimation WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) sum#(nil(),y) -> c_3() weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) weight#(cons(n,nil())) -> c_5() - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {3,5} by application of Pre({3,5}) = {1,4}. Here rules are labelled as follows: 1: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) 2: sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) 3: sum#(nil(),y) -> c_3() 4: weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) 5: weight#(cons(n,nil())) -> c_5() ** Step 1.b:3: RemoveWeakSuffixes WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) - Weak DPs: sum#(nil(),y) -> c_3() weight#(cons(n,nil())) -> c_5() - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:sum#(cons(0(),x),y) -> c_1(sum#(x,y)) -->_1 sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))):2 -->_1 sum#(nil(),y) -> c_3():4 -->_1 sum#(cons(0(),x),y) -> c_1(sum#(x,y)):1 2:S:sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) -->_1 sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))):2 -->_1 sum#(cons(0(),x),y) -> c_1(sum#(x,y)):1 3:S:weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) -->_1 weight#(cons(n,nil())) -> c_5():5 -->_1 weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))):3 -->_2 sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))):2 -->_2 sum#(cons(0(),x),y) -> c_1(sum#(x,y)):1 4:W:sum#(nil(),y) -> c_3() 5:W:weight#(cons(n,nil())) -> c_5() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 5: weight#(cons(n,nil())) -> c_5() 4: sum#(nil(),y) -> c_3() ** Step 1.b:4: UsableRules WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y weight(cons(n,cons(m,x))) -> weight(sum(cons(n,cons(m,x)),cons(0(),x))) weight(cons(n,nil())) -> n - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) ** Step 1.b:5: DecomposeDG WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: DecomposeDG {onSelection = all below first cut in WDG, onUpper = Nothing, onLower = Nothing} + Details: We decompose the input problem according to the dependency graph into the upper component weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) and a lower component sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) Further, following extension rules are added to the lower component. weight#(cons(n,cons(m,x))) -> sum#(cons(n,cons(m,x)),cons(0(),x)) weight#(cons(n,cons(m,x))) -> weight#(sum(cons(n,cons(m,x)),cons(0(),x))) *** Step 1.b:5.a:1: SimplifyRHS WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))) -->_1 weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x))) ,sum#(cons(n,cons(m,x)),cons(0(),x))):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x)))) *** Step 1.b:5.a:2: WeightGap WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x)))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/1,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following constant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(weight#) = {1}, uargs(c_4) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [0] p(cons) = [1] x2 + [2] p(nil) = [0] p(s) = [1] x1 + [0] p(sum) = [1] x2 + [0] p(weight) = [1] x1 + [8] p(sum#) = [8] x2 + [1] p(weight#) = [1] x1 + [1] p(c_1) = [1] p(c_2) = [8] x1 + [2] p(c_3) = [1] p(c_4) = [1] x1 + [1] p(c_5) = [0] Following rules are strictly oriented: weight#(cons(n,cons(m,x))) = [1] x + [5] > [1] x + [4] = c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x)))) Following rules are (at-least) weakly oriented: sum(cons(0(),x),y) = [1] y + [0] >= [1] y + [0] = sum(x,y) sum(cons(s(n),x),cons(m,y)) = [1] y + [2] >= [1] y + [2] = sum(cons(n,x),cons(s(m),y)) sum(nil(),y) = [1] y + [0] >= [1] y + [0] = y Further, it can be verified that all rules not oriented are covered by the weightgap condition. *** Step 1.b:5.a:3: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: weight#(cons(n,cons(m,x))) -> c_4(weight#(sum(cons(n,cons(m,x)),cons(0(),x)))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/1,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). *** Step 1.b:5.b:1: WeightGap WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) - Weak DPs: weight#(cons(n,cons(m,x))) -> sum#(cons(n,cons(m,x)),cons(0(),x)) weight#(cons(n,cons(m,x))) -> weight#(sum(cons(n,cons(m,x)),cons(0(),x))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = UArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following constant growth matrix-interpretation: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(weight#) = {1}, uargs(c_1) = {1}, uargs(c_2) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [0] p(cons) = [1] x2 + [4] p(nil) = [2] p(s) = [1] x1 + [1] p(sum) = [1] x2 + [0] p(weight) = [1] x1 + [1] p(sum#) = [1] x1 + [1] p(weight#) = [1] x1 + [1] p(c_1) = [1] x1 + [0] p(c_2) = [1] x1 + [3] p(c_3) = [0] p(c_4) = [2] x1 + [0] p(c_5) = [1] Following rules are strictly oriented: sum#(cons(0(),x),y) = [1] x + [5] > [1] x + [1] = c_1(sum#(x,y)) Following rules are (at-least) weakly oriented: sum#(cons(s(n),x),cons(m,y)) = [1] x + [5] >= [1] x + [8] = c_2(sum#(cons(n,x),cons(s(m),y))) weight#(cons(n,cons(m,x))) = [1] x + [9] >= [1] x + [9] = sum#(cons(n,cons(m,x)),cons(0(),x)) weight#(cons(n,cons(m,x))) = [1] x + [9] >= [1] x + [5] = weight#(sum(cons(n,cons(m,x)),cons(0(),x))) sum(cons(0(),x),y) = [1] y + [0] >= [1] y + [0] = sum(x,y) sum(cons(s(n),x),cons(m,y)) = [1] y + [4] >= [1] y + [4] = sum(cons(n,x),cons(s(m),y)) sum(nil(),y) = [1] y + [0] >= [1] y + [0] = y Further, it can be verified that all rules not oriented are covered by the weightgap condition. *** Step 1.b:5.b:2: Ara WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) - Weak DPs: sum#(cons(0(),x),y) -> c_1(sum#(x,y)) weight#(cons(n,cons(m,x))) -> sum#(cons(n,cons(m,x)),cons(0(),x)) weight#(cons(n,cons(m,x))) -> weight#(sum(cons(n,cons(m,x)),cons(0(),x))) - Weak TRS: sum(cons(0(),x),y) -> sum(x,y) sum(cons(s(n),x),cons(m,y)) -> sum(cons(n,x),cons(s(m),y)) sum(nil(),y) -> y - Signature: {sum/2,weight/1,sum#/2,weight#/1} / {0/0,cons/2,nil/0,s/1,c_1/1,c_2/1,c_3/0,c_4/2,c_5/0} - Obligation: innermost runtime complexity wrt. defined symbols {sum#,weight#} and constructors {0,cons,nil,s} + Applied Processor: Ara {araHeuristics = NoHeuristics, minDegree = 2, maxDegree = 2, araTimeout = 8, araRuleShifting = Just 1} + Details: Signatures used: ---------------- 0 :: [] -(0)-> "A"(1, 0) 0 :: [] -(0)-> "A"(12, 12) 0 :: [] -(0)-> "A"(15, 14) cons :: ["A"(1, 0) x "A"(2, 1)] -(1)-> "A"(1, 1) cons :: ["A"(0, 0) x "A"(3, 3)] -(3)-> "A"(0, 3) cons :: ["A"(1, 0) x "A"(1, 0)] -(0)-> "A"(1, 0) cons :: ["A"(1, 0) x "A"(7, 6)] -(6)-> "A"(1, 6) cons :: ["A"(7, 0) x "A"(13, 6)] -(6)-> "A"(7, 6) cons :: ["A"(4, 0) x "A"(5, 1)] -(1)-> "A"(4, 1) cons :: ["A"(4, 0) x "A"(7, 3)] -(3)-> "A"(4, 3) cons :: ["A"(5, 0) x "A"(5, 0)] -(0)-> "A"(5, 0) nil :: [] -(0)-> "A"(1, 0) s :: ["A"(1, 0)] -(1)-> "A"(1, 0) s :: ["A"(0, 0)] -(0)-> "A"(0, 14) sum :: ["A"(1, 0) x "A"(1, 6)] -(0)-> "A"(1, 6) sum# :: ["A"(1, 1) x "A"(0, 3)] -(5)-> "A"(0, 8) weight# :: ["A"(1, 6)] -(3)-> "A"(0, 3) c_1 :: ["A"(0, 0)] -(0)-> "A"(9, 12) c_2 :: ["A"(0, 8)] -(0)-> "A"(0, 8) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "0_A" :: [] -(0)-> "A"(1, 0) "0_A" :: [] -(0)-> "A"(0, 1) "c_1_A" :: ["A"(0)] -(0)-> "A"(1, 0) "c_1_A" :: ["A"(0)] -(0)-> "A"(0, 1) "c_2_A" :: ["A"(0)] -(1)-> "A"(1, 0) "c_2_A" :: ["A"(0)] -(0)-> "A"(0, 1) "cons_A" :: ["A"(1, 0) x "A"(1, 0)] -(0)-> "A"(1, 0) "cons_A" :: ["A"(0, 0) x "A"(1, 1)] -(1)-> "A"(0, 1) "nil_A" :: [] -(0)-> "A"(1, 0) "nil_A" :: [] -(0)-> "A"(0, 1) "s_A" :: ["A"(1, 0)] -(1)-> "A"(1, 0) "s_A" :: ["A"(0, 0)] -(0)-> "A"(0, 1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: sum#(cons(s(n),x),cons(m,y)) -> c_2(sum#(cons(n,x),cons(s(m),y))) 2. Weak: WORST_CASE(Omega(n^1),O(n^3))