/export/starexec/sandbox2/solver/bin/starexec_run_tct_rci /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/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: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () *** Step 1.a:1.a:1: Ara. MAYBE + Considered Problem: - Strict TRS: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + Applied Processor: Ara {minDegree = 1, maxDegree = 3, araTimeout = 15, araRuleShifting = Just 1, isBestCase = True, mkCompletelyDefined = False, verboseOutput = False} + Details: Signatures used: ---------------- F (TrsFun "0") :: [] -(0)-> "A"(1) F (TrsFun "0") :: [] -(0)-> "A"(0) F (TrsFun "average") :: ["A"(1) x "A"(0)] -(1)-> "A"(0) F (TrsFun "main") :: ["A"(1) x "A"(0)] -(1)-> "A"(0) F (TrsFun "s") :: ["A"(0)] -(0)-> "A"(0) F (TrsFun "s") :: ["A"(1)] -(1)-> "A"(1) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) main(x1,x2) -> average(x1,x2) 2. Weak: *** Step 1.a:1.b:1: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: average(x,y){y -> s(s(s(y)))} = average(x,s(s(s(y)))) ->^+ s(average(s(x),y)) = C[average(s(x),y) = average(x,y){x -> s(x)}] ** Step 1.b:1: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + 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(s) = {1} Following symbols are considered usable: {average} TcT has computed the following interpretation: p(0) = [13] p(average) = [1] x1 + [1] x2 + [3] p(s) = [1] x1 + [1] Following rules are strictly oriented: average(x,s(s(s(y)))) = [1] x + [1] y + [6] > [1] x + [1] y + [5] = s(average(s(x),y)) average(0(),0()) = [29] > [13] = 0() average(0(),s(0())) = [30] > [13] = 0() average(0(),s(s(0()))) = [31] > [14] = s(0()) Following rules are (at-least) weakly oriented: average(s(x),y) = [1] x + [1] y + [4] >= [1] x + [1] y + [4] = average(x,s(y)) ** Step 1.b:2: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: average(s(x),y) -> average(x,s(y)) - Weak TRS: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + 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(s) = {1} Following symbols are considered usable: {average} TcT has computed the following interpretation: p(0) = [4] p(average) = [4] x1 + [2] x2 + [0] p(s) = [1] x1 + [1] Following rules are strictly oriented: average(s(x),y) = [4] x + [2] y + [4] > [4] x + [2] y + [2] = average(x,s(y)) Following rules are (at-least) weakly oriented: average(x,s(s(s(y)))) = [4] x + [2] y + [6] >= [4] x + [2] y + [5] = s(average(s(x),y)) average(0(),0()) = [24] >= [4] = 0() average(0(),s(0())) = [26] >= [4] = 0() average(0(),s(s(0()))) = [28] >= [5] = s(0()) ** Step 1.b:3: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: average(x,s(s(s(y)))) -> s(average(s(x),y)) average(0(),0()) -> 0() average(0(),s(0())) -> 0() average(0(),s(s(0()))) -> s(0()) average(s(x),y) -> average(x,s(y)) - Signature: {average/2} / {0/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {average} and constructors {0,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(Omega(n^1),O(n^1))