/export/starexec/sandbox/solver/bin/starexec_run_tct_dci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^1)) * Step 1: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(a(x1)) -> a(b(c(a(x1)))) a(c(b(x1))) -> b(a(b(a(x1)))) b(x1) -> c(a(c(x1))) - Signature: {a/1,b/1} / {c/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c} + Applied Processor: WeightGap {wgDimension = 1, wgDegree = 1, wgKind = Algebraic, wgUArgs = NoUArgs, wgOn = WgOnAny} + Details: The weightgap principle applies using the following nonconstant growth matrix-interpretation: We apply a matrix interpretation of kind triangular matrix interpretation: Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [1] x1 + [0] p(b) = [1] x1 + [11] p(c) = [1] x1 + [0] Following rules are strictly oriented: b(x1) = [1] x1 + [11] > [1] x1 + [0] = c(a(c(x1))) Following rules are (at-least) weakly oriented: a(a(x1)) = [1] x1 + [0] >= [1] x1 + [11] = a(b(c(a(x1)))) a(c(b(x1))) = [1] x1 + [11] >= [1] x1 + [22] = b(a(b(a(x1)))) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 2: Bounds. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(a(x1)) -> a(b(c(a(x1)))) a(c(b(x1))) -> b(a(b(a(x1)))) - Weak TRS: b(x1) -> c(a(c(x1))) - Signature: {a/1,b/1} / {c/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c} + Applied Processor: Bounds {initialAutomaton = minimal, enrichment = match} + Details: The problem is match-bounded by 5. The enriched problem is compatible with follwoing automaton. a_0(1) -> 1 a_1(1) -> 4 a_1(2) -> 1 a_1(2) -> 4 a_1(3) -> 11 a_1(5) -> 4 a_1(6) -> 5 a_1(8) -> 7 a_1(10) -> 9 a_1(15) -> 4 a_1(31) -> 4 a_2(2) -> 14 a_2(5) -> 17 a_2(6) -> 14 a_2(12) -> 4 a_2(12) -> 17 a_2(15) -> 17 a_2(16) -> 15 a_2(19) -> 18 a_2(21) -> 20 a_2(23) -> 22 a_2(25) -> 24 a_2(27) -> 26 a_2(31) -> 17 a_2(32) -> 5 a_2(47) -> 17 a_2(48) -> 5 a_3(15) -> 33 a_3(16) -> 30 a_3(28) -> 17 a_3(28) -> 33 a_3(31) -> 33 a_3(32) -> 31 a_3(35) -> 34 a_3(37) -> 36 a_3(39) -> 38 a_3(41) -> 40 a_3(43) -> 42 a_3(47) -> 33 a_3(48) -> 15 a_4(31) -> 49 a_4(32) -> 46 a_4(44) -> 33 a_4(44) -> 49 a_4(47) -> 64 a_4(48) -> 47 a_4(51) -> 50 a_4(53) -> 52 a_4(55) -> 54 a_4(57) -> 56 a_4(59) -> 58 a_4(61) -> 60 a_4(63) -> 62 a_4(66) -> 65 a_5(48) -> 69 a_5(67) -> 64 a_5(71) -> 70 a_5(73) -> 72 a_5(75) -> 74 a_5(77) -> 76 a_5(79) -> 78 a_5(81) -> 80 b_0(1) -> 1 b_1(3) -> 2 b_1(4) -> 6 b_1(5) -> 1 b_1(5) -> 4 b_1(5) -> 7 b_2(13) -> 12 b_2(15) -> 4 b_2(15) -> 5 b_2(15) -> 7 b_2(15) -> 11 b_2(15) -> 14 b_2(15) -> 20 b_2(17) -> 16 b_2(23) -> 12 b_3(29) -> 28 b_3(31) -> 14 b_3(31) -> 15 b_3(31) -> 17 b_3(31) -> 20 b_3(31) -> 22 b_3(31) -> 26 b_3(31) -> 30 b_3(33) -> 32 b_3(37) -> 28 b_4(45) -> 44 b_4(47) -> 36 b_4(47) -> 38 b_4(49) -> 48 b_4(59) -> 44 b_4(62) -> 30 b_4(64) -> 63 b_5(68) -> 67 c_0(1) -> 1 c_1(1) -> 8 c_1(3) -> 10 c_1(4) -> 3 c_1(5) -> 8 c_1(7) -> 1 c_1(7) -> 4 c_1(9) -> 2 c_1(11) -> 6 c_2(3) -> 19 c_2(4) -> 21 c_2(5) -> 23 c_2(13) -> 25 c_2(14) -> 13 c_2(15) -> 23 c_2(17) -> 27 c_2(18) -> 2 c_2(20) -> 6 c_2(22) -> 1 c_2(22) -> 4 c_2(22) -> 5 c_2(22) -> 7 c_2(22) -> 11 c_2(22) -> 14 c_2(22) -> 20 c_2(24) -> 12 c_2(26) -> 16 c_3(13) -> 35 c_3(15) -> 37 c_3(17) -> 39 c_3(23) -> 35 c_3(29) -> 41 c_3(30) -> 29 c_3(31) -> 37 c_3(33) -> 43 c_3(34) -> 12 c_3(36) -> 4 c_3(36) -> 5 c_3(36) -> 7 c_3(36) -> 11 c_3(36) -> 14 c_3(36) -> 17 c_3(36) -> 20 c_3(36) -> 22 c_3(38) -> 16 c_3(40) -> 28 c_3(42) -> 32 c_4(29) -> 51 c_4(31) -> 53 c_4(33) -> 55 c_4(37) -> 51 c_4(45) -> 57 c_4(46) -> 45 c_4(47) -> 59 c_4(49) -> 61 c_4(50) -> 28 c_4(52) -> 14 c_4(52) -> 15 c_4(52) -> 17 c_4(52) -> 20 c_4(52) -> 22 c_4(52) -> 26 c_4(52) -> 30 c_4(54) -> 32 c_4(56) -> 44 c_4(58) -> 38 c_4(60) -> 48 c_4(62) -> 53 c_4(64) -> 66 c_4(65) -> 63 c_5(45) -> 71 c_5(47) -> 73 c_5(49) -> 75 c_5(59) -> 71 c_5(62) -> 77 c_5(64) -> 79 c_5(68) -> 81 c_5(69) -> 68 c_5(70) -> 44 c_5(72) -> 36 c_5(72) -> 38 c_5(74) -> 48 c_5(76) -> 30 c_5(78) -> 63 c_5(80) -> 67 * Step 3: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: a(a(x1)) -> a(b(c(a(x1)))) a(c(b(x1))) -> b(a(b(a(x1)))) b(x1) -> c(a(c(x1))) - Signature: {a/1,b/1} / {c/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))