/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: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:2: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: decrease(y){y -> Cons(x,y)} = decrease(Cons(x,y)) ->^+ decrease(y) = C[decrease(y) = decrease(y){}] ** Step 1.b:1: Bounds. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: Bounds {initialAutomaton = perSymbol, enrichment = match} + Details: The problem is match-bounded by 2. The enriched problem is compatible with follwoing automaton. Cons_0(1,1) -> 1 Cons_0(1,2) -> 1 Cons_0(2,1) -> 1 Cons_0(2,2) -> 1 Cons_1(6,6) -> 47 Cons_1(6,7) -> 5 Cons_1(6,8) -> 7 Cons_1(6,9) -> 8 Cons_1(6,10) -> 9 Cons_1(6,11) -> 10 Cons_1(6,12) -> 11 Cons_1(6,13) -> 12 Cons_1(6,14) -> 13 Cons_1(6,15) -> 14 Cons_1(6,16) -> 15 Cons_1(6,17) -> 16 Cons_1(6,18) -> 17 Cons_1(6,19) -> 18 Cons_1(6,20) -> 19 Cons_1(6,21) -> 20 Cons_1(6,22) -> 21 Cons_1(6,23) -> 22 Cons_1(6,24) -> 23 Cons_1(6,25) -> 24 Cons_1(6,26) -> 25 Cons_1(6,27) -> 26 Cons_1(6,28) -> 27 Cons_1(6,29) -> 28 Cons_1(6,30) -> 29 Cons_1(6,31) -> 30 Cons_1(6,32) -> 31 Cons_1(6,33) -> 32 Cons_1(6,34) -> 33 Cons_1(6,35) -> 34 Cons_1(6,36) -> 35 Cons_1(6,37) -> 36 Cons_1(6,38) -> 37 Cons_1(6,39) -> 38 Cons_1(6,40) -> 39 Cons_1(6,41) -> 40 Cons_1(6,42) -> 41 Cons_1(6,43) -> 42 Cons_1(6,44) -> 43 Cons_1(6,45) -> 44 Cons_1(6,46) -> 45 Cons_1(6,47) -> 46 Cons_2(48,49) -> 3 Cons_2(50,51) -> 49 Cons_2(52,53) -> 51 Cons_2(54,55) -> 53 Cons_2(56,57) -> 55 Cons_2(58,59) -> 57 Cons_2(60,61) -> 59 Cons_2(62,63) -> 61 Cons_2(64,65) -> 63 Cons_2(66,67) -> 65 Cons_2(68,69) -> 67 Cons_2(70,71) -> 69 Cons_2(72,73) -> 71 Cons_2(74,75) -> 73 Cons_2(76,77) -> 75 Cons_2(78,79) -> 77 Cons_2(80,81) -> 79 Cons_2(82,83) -> 81 Cons_2(84,85) -> 83 Cons_2(86,87) -> 85 Cons_2(88,89) -> 87 Cons_2(90,91) -> 89 Cons_2(92,93) -> 91 Cons_2(94,95) -> 93 Cons_2(96,97) -> 95 Cons_2(98,99) -> 97 Cons_2(100,101) -> 99 Cons_2(102,103) -> 101 Cons_2(104,105) -> 103 Cons_2(106,107) -> 105 Cons_2(108,109) -> 107 Cons_2(110,111) -> 109 Cons_2(112,113) -> 111 Cons_2(114,115) -> 113 Cons_2(116,117) -> 115 Cons_2(118,119) -> 117 Cons_2(120,121) -> 119 Cons_2(122,123) -> 121 Cons_2(124,125) -> 123 Cons_2(126,127) -> 125 Cons_2(128,129) -> 127 Cons_2(130,131) -> 129 Cons_2(131,49) -> 4 Nil_0() -> 2 Nil_1() -> 6 Nil_2() -> 48 Nil_2() -> 50 Nil_2() -> 52 Nil_2() -> 54 Nil_2() -> 56 Nil_2() -> 58 Nil_2() -> 60 Nil_2() -> 62 Nil_2() -> 64 Nil_2() -> 66 Nil_2() -> 68 Nil_2() -> 70 Nil_2() -> 72 Nil_2() -> 74 Nil_2() -> 76 Nil_2() -> 78 Nil_2() -> 80 Nil_2() -> 82 Nil_2() -> 84 Nil_2() -> 86 Nil_2() -> 88 Nil_2() -> 90 Nil_2() -> 92 Nil_2() -> 94 Nil_2() -> 96 Nil_2() -> 98 Nil_2() -> 100 Nil_2() -> 102 Nil_2() -> 104 Nil_2() -> 106 Nil_2() -> 108 Nil_2() -> 110 Nil_2() -> 112 Nil_2() -> 114 Nil_2() -> 116 Nil_2() -> 118 Nil_2() -> 120 Nil_2() -> 122 Nil_2() -> 124 Nil_2() -> 126 Nil_2() -> 128 Nil_2() -> 130 Nil_2() -> 131 decrease_0(1) -> 3 decrease_0(2) -> 3 decrease_1(1) -> 3 decrease_1(1) -> 4 decrease_1(2) -> 3 decrease_1(2) -> 4 goal_0(1) -> 4 goal_0(2) -> 4 number42_0(1) -> 5 number42_0(2) -> 5 number42_1(6) -> 3 number42_1(6) -> 4 ** Step 1.b:2: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: decrease(Cons(x,xs)) -> decrease(xs) decrease(Nil()) -> number42(Nil()) goal(x) -> decrease(x) number42(x) -> Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Cons(Nil() ,Nil())))))))))))))))))))))))))))))))))))))))))) - Signature: {decrease/1,goal/1,number42/1} / {Cons/2,Nil/0} - Obligation: innermost runtime complexity wrt. defined symbols {decrease,goal,number42} and constructors {Cons,Nil} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(Omega(n^1),O(n^1))