/export/starexec/sandbox2/solver/bin/starexec_run_tct_dci /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^3)) * Step 1: WeightGap. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 0(3(x1)) -> 5(3(x1)) 2(4(x1)) -> 0(7(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(3(x1)) -> 6(0(x1)) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + 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(0) = [1] x1 + [0] p(1) = [1] x1 + [0] p(2) = [1] x1 + [3] p(3) = [1] x1 + [0] p(4) = [1] x1 + [0] p(5) = [1] x1 + [0] p(6) = [1] x1 + [0] p(7) = [1] x1 + [4] p(8) = [1] x1 + [3] p(9) = [1] x1 + [1] Following rules are strictly oriented: 2(7(x1)) = [1] x1 + [7] > [1] x1 + [3] = 1(8(x1)) 2(8(x1)) = [1] x1 + [6] > [1] x1 + [0] = 4(x1) 2(8(x1)) = [1] x1 + [6] > [1] x1 + [4] = 7(x1) 2(8(1(x1))) = [1] x1 + [6] > [1] x1 + [3] = 8(x1) 4(7(x1)) = [1] x1 + [4] > [1] x1 + [0] = 1(3(x1)) 5(9(x1)) = [1] x1 + [1] > [1] x1 + [0] = 0(x1) 7(0(x1)) = [1] x1 + [4] > [1] x1 + [1] = 9(3(x1)) 7(2(x1)) = [1] x1 + [7] > [1] x1 + [0] = 4(x1) 9(7(x1)) = [1] x1 + [5] > [1] x1 + [4] = 7(5(x1)) Following rules are (at-least) weakly oriented: 0(3(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 5(3(x1)) 2(4(x1)) = [1] x1 + [3] >= [1] x1 + [4] = 0(7(x1)) 4(x1) = [1] x1 + [0] >= [1] x1 + [3] = 5(2(3(x1))) 4(x1) = [1] x1 + [0] >= [1] x1 + [1] = 9(6(6(x1))) 5(2(6(x1))) = [1] x1 + [3] >= [1] x1 + [3] = 6(2(4(x1))) 5(3(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 6(0(x1)) 6(2(x1)) = [1] x1 + [3] >= [1] x1 + [8] = 7(7(x1)) 6(6(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 3(x1) 6(9(x1)) = [1] x1 + [1] >= [1] x1 + [1] = 9(x1) 9(x1) = [1] x1 + [1] >= [1] x1 + [4] = 6(7(x1)) 9(5(9(x1))) = [1] x1 + [2] >= [1] x1 + [4] = 5(7(x1)) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 2: WeightGap. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 0(3(x1)) -> 5(3(x1)) 2(4(x1)) -> 0(7(x1)) 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) 5(2(6(x1))) -> 6(2(4(x1))) 5(3(x1)) -> 6(0(x1)) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) - Weak TRS: 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(7(x1)) -> 1(3(x1)) 5(9(x1)) -> 0(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + 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(0) = [1] x1 + [2] p(1) = [1] x1 + [0] p(2) = [1] x1 + [1] p(3) = [1] x1 + [0] p(4) = [1] x1 + [0] p(5) = [1] x1 + [1] p(6) = [1] x1 + [4] p(7) = [1] x1 + [0] p(8) = [1] x1 + [1] p(9) = [1] x1 + [1] Following rules are strictly oriented: 0(3(x1)) = [1] x1 + [2] > [1] x1 + [1] = 5(3(x1)) 5(2(6(x1))) = [1] x1 + [6] > [1] x1 + [5] = 6(2(4(x1))) 6(2(x1)) = [1] x1 + [5] > [1] x1 + [0] = 7(7(x1)) 6(6(x1)) = [1] x1 + [8] > [1] x1 + [0] = 3(x1) 6(9(x1)) = [1] x1 + [5] > [1] x1 + [1] = 9(x1) 9(5(9(x1))) = [1] x1 + [3] > [1] x1 + [1] = 5(7(x1)) Following rules are (at-least) weakly oriented: 2(4(x1)) = [1] x1 + [1] >= [1] x1 + [2] = 0(7(x1)) 2(7(x1)) = [1] x1 + [1] >= [1] x1 + [1] = 1(8(x1)) 2(8(x1)) = [1] x1 + [2] >= [1] x1 + [0] = 4(x1) 2(8(x1)) = [1] x1 + [2] >= [1] x1 + [0] = 7(x1) 2(8(1(x1))) = [1] x1 + [2] >= [1] x1 + [1] = 8(x1) 4(x1) = [1] x1 + [0] >= [1] x1 + [2] = 5(2(3(x1))) 4(x1) = [1] x1 + [0] >= [1] x1 + [9] = 9(6(6(x1))) 4(7(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 1(3(x1)) 5(3(x1)) = [1] x1 + [1] >= [1] x1 + [6] = 6(0(x1)) 5(9(x1)) = [1] x1 + [2] >= [1] x1 + [2] = 0(x1) 7(0(x1)) = [1] x1 + [2] >= [1] x1 + [1] = 9(3(x1)) 7(2(x1)) = [1] x1 + [1] >= [1] x1 + [0] = 4(x1) 9(x1) = [1] x1 + [1] >= [1] x1 + [4] = 6(7(x1)) 9(7(x1)) = [1] x1 + [1] >= [1] x1 + [1] = 7(5(x1)) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: WeightGap. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 2(4(x1)) -> 0(7(x1)) 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) 5(3(x1)) -> 6(0(x1)) 9(x1) -> 6(7(x1)) - Weak TRS: 0(3(x1)) -> 5(3(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + 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(0) = [1] x1 + [4] p(1) = [1] x1 + [0] p(2) = [1] x1 + [0] p(3) = [1] x1 + [0] p(4) = [1] x1 + [0] p(5) = [1] x1 + [4] p(6) = [1] x1 + [2] p(7) = [1] x1 + [0] p(8) = [1] x1 + [0] p(9) = [1] x1 + [4] Following rules are strictly oriented: 9(x1) = [1] x1 + [4] > [1] x1 + [2] = 6(7(x1)) Following rules are (at-least) weakly oriented: 0(3(x1)) = [1] x1 + [4] >= [1] x1 + [4] = 5(3(x1)) 2(4(x1)) = [1] x1 + [0] >= [1] x1 + [4] = 0(7(x1)) 2(7(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 1(8(x1)) 2(8(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 4(x1) 2(8(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 7(x1) 2(8(1(x1))) = [1] x1 + [0] >= [1] x1 + [0] = 8(x1) 4(x1) = [1] x1 + [0] >= [1] x1 + [4] = 5(2(3(x1))) 4(x1) = [1] x1 + [0] >= [1] x1 + [8] = 9(6(6(x1))) 4(7(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 1(3(x1)) 5(2(6(x1))) = [1] x1 + [6] >= [1] x1 + [2] = 6(2(4(x1))) 5(3(x1)) = [1] x1 + [4] >= [1] x1 + [6] = 6(0(x1)) 5(9(x1)) = [1] x1 + [8] >= [1] x1 + [4] = 0(x1) 6(2(x1)) = [1] x1 + [2] >= [1] x1 + [0] = 7(7(x1)) 6(6(x1)) = [1] x1 + [4] >= [1] x1 + [0] = 3(x1) 6(9(x1)) = [1] x1 + [6] >= [1] x1 + [4] = 9(x1) 7(0(x1)) = [1] x1 + [4] >= [1] x1 + [4] = 9(3(x1)) 7(2(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 4(x1) 9(5(9(x1))) = [1] x1 + [12] >= [1] x1 + [4] = 5(7(x1)) 9(7(x1)) = [1] x1 + [4] >= [1] x1 + [4] = 7(5(x1)) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: WeightGap. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 2(4(x1)) -> 0(7(x1)) 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) 5(3(x1)) -> 6(0(x1)) - Weak TRS: 0(3(x1)) -> 5(3(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + 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(0) = [1] x1 + [1] p(1) = [1] x1 + [0] p(2) = [1] x1 + [4] p(3) = [1] x1 + [0] p(4) = [1] x1 + [0] p(5) = [1] x1 + [0] p(6) = [1] x1 + [0] p(7) = [1] x1 + [0] p(8) = [1] x1 + [0] p(9) = [1] x1 + [1] Following rules are strictly oriented: 2(4(x1)) = [1] x1 + [4] > [1] x1 + [1] = 0(7(x1)) Following rules are (at-least) weakly oriented: 0(3(x1)) = [1] x1 + [1] >= [1] x1 + [0] = 5(3(x1)) 2(7(x1)) = [1] x1 + [4] >= [1] x1 + [0] = 1(8(x1)) 2(8(x1)) = [1] x1 + [4] >= [1] x1 + [0] = 4(x1) 2(8(x1)) = [1] x1 + [4] >= [1] x1 + [0] = 7(x1) 2(8(1(x1))) = [1] x1 + [4] >= [1] x1 + [0] = 8(x1) 4(x1) = [1] x1 + [0] >= [1] x1 + [4] = 5(2(3(x1))) 4(x1) = [1] x1 + [0] >= [1] x1 + [1] = 9(6(6(x1))) 4(7(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 1(3(x1)) 5(2(6(x1))) = [1] x1 + [4] >= [1] x1 + [4] = 6(2(4(x1))) 5(3(x1)) = [1] x1 + [0] >= [1] x1 + [1] = 6(0(x1)) 5(9(x1)) = [1] x1 + [1] >= [1] x1 + [1] = 0(x1) 6(2(x1)) = [1] x1 + [4] >= [1] x1 + [0] = 7(7(x1)) 6(6(x1)) = [1] x1 + [0] >= [1] x1 + [0] = 3(x1) 6(9(x1)) = [1] x1 + [1] >= [1] x1 + [1] = 9(x1) 7(0(x1)) = [1] x1 + [1] >= [1] x1 + [1] = 9(3(x1)) 7(2(x1)) = [1] x1 + [4] >= [1] x1 + [0] = 4(x1) 9(x1) = [1] x1 + [1] >= [1] x1 + [0] = 6(7(x1)) 9(5(9(x1))) = [1] x1 + [2] >= [1] x1 + [0] = 5(7(x1)) 9(7(x1)) = [1] x1 + [1] >= [1] x1 + [0] = 7(5(x1)) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 5: WeightGap. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) 5(3(x1)) -> 6(0(x1)) - Weak TRS: 0(3(x1)) -> 5(3(x1)) 2(4(x1)) -> 0(7(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + 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(0) = [1] x1 + [6] p(1) = [1] x1 + [1] p(2) = [1] x1 + [4] p(3) = [1] x1 + [4] p(4) = [1] x1 + [5] p(5) = [1] x1 + [5] p(6) = [1] x1 + [2] p(7) = [1] x1 + [3] p(8) = [1] x1 + [4] p(9) = [1] x1 + [5] Following rules are strictly oriented: 5(3(x1)) = [1] x1 + [9] > [1] x1 + [8] = 6(0(x1)) Following rules are (at-least) weakly oriented: 0(3(x1)) = [1] x1 + [10] >= [1] x1 + [9] = 5(3(x1)) 2(4(x1)) = [1] x1 + [9] >= [1] x1 + [9] = 0(7(x1)) 2(7(x1)) = [1] x1 + [7] >= [1] x1 + [5] = 1(8(x1)) 2(8(x1)) = [1] x1 + [8] >= [1] x1 + [5] = 4(x1) 2(8(x1)) = [1] x1 + [8] >= [1] x1 + [3] = 7(x1) 2(8(1(x1))) = [1] x1 + [9] >= [1] x1 + [4] = 8(x1) 4(x1) = [1] x1 + [5] >= [1] x1 + [13] = 5(2(3(x1))) 4(x1) = [1] x1 + [5] >= [1] x1 + [9] = 9(6(6(x1))) 4(7(x1)) = [1] x1 + [8] >= [1] x1 + [5] = 1(3(x1)) 5(2(6(x1))) = [1] x1 + [11] >= [1] x1 + [11] = 6(2(4(x1))) 5(9(x1)) = [1] x1 + [10] >= [1] x1 + [6] = 0(x1) 6(2(x1)) = [1] x1 + [6] >= [1] x1 + [6] = 7(7(x1)) 6(6(x1)) = [1] x1 + [4] >= [1] x1 + [4] = 3(x1) 6(9(x1)) = [1] x1 + [7] >= [1] x1 + [5] = 9(x1) 7(0(x1)) = [1] x1 + [9] >= [1] x1 + [9] = 9(3(x1)) 7(2(x1)) = [1] x1 + [7] >= [1] x1 + [5] = 4(x1) 9(x1) = [1] x1 + [5] >= [1] x1 + [5] = 6(7(x1)) 9(5(9(x1))) = [1] x1 + [15] >= [1] x1 + [8] = 5(7(x1)) 9(7(x1)) = [1] x1 + [8] >= [1] x1 + [8] = 7(5(x1)) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 6: NaturalMI. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) - Weak TRS: 0(3(x1)) -> 5(3(x1)) 2(4(x1)) -> 0(7(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(3(x1)) -> 6(0(x1)) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + Applied Processor: NaturalMI {miDimension = 3, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation (containing no more than 2 non-zero interpretation-entries in the diagonal of the component-wise maxima): Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] p(1) = [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [0] p(2) = [1 1 0] [1] [0 1 1] x1 + [0] [0 0 0] [1] p(3) = [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] p(4) = [1 1 0] [1] [0 1 0] x1 + [0] [0 0 0] [1] p(5) = [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] p(6) = [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] p(7) = [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] p(8) = [1 1 0] [0] [0 1 0] x1 + [1] [0 0 0] [1] p(9) = [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] Following rules are strictly oriented: 4(x1) = [1 1 0] [1] [0 1 0] x1 + [0] [0 0 0] [1] > [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 9(6(6(x1))) Following rules are (at-least) weakly oriented: 0(3(x1)) = [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = 5(3(x1)) 2(4(x1)) = [1 2 0] [2] [0 1 0] x1 + [1] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = 0(7(x1)) 2(7(x1)) = [1 1 0] [1] [0 1 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [0] [0 1 0] x1 + [1] [0 0 0] [0] = 1(8(x1)) 2(8(x1)) = [1 2 0] [2] [0 1 0] x1 + [2] [0 0 0] [1] >= [1 1 0] [1] [0 1 0] x1 + [0] [0 0 0] [1] = 4(x1) 2(8(x1)) = [1 2 0] [2] [0 1 0] x1 + [2] [0 0 0] [1] >= [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 7(x1) 2(8(1(x1))) = [1 2 0] [2] [0 1 0] x1 + [2] [0 0 0] [1] >= [1 1 0] [0] [0 1 0] x1 + [1] [0 0 0] [1] = 8(x1) 4(x1) = [1 1 0] [1] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [1] [0 0 0] x1 + [0] [0 0 0] [1] = 5(2(3(x1))) 4(7(x1)) = [1 1 0] [1] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = 1(3(x1)) 5(2(6(x1))) = [1 2 0] [2] [0 1 0] x1 + [1] [0 0 0] [1] >= [1 2 0] [2] [0 1 0] x1 + [1] [0 0 0] [1] = 6(2(4(x1))) 5(3(x1)) = [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = 6(0(x1)) 5(9(x1)) = [1 2 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = 0(x1) 6(2(x1)) = [1 1 0] [1] [0 1 1] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 7(7(x1)) 6(6(x1)) = [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = 3(x1) 6(9(x1)) = [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 9(x1) 7(0(x1)) = [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = 9(3(x1)) 7(2(x1)) = [1 1 0] [1] [0 1 1] x1 + [0] [0 0 0] [1] >= [1 1 0] [1] [0 1 0] x1 + [0] [0 0 0] [1] = 4(x1) 9(x1) = [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 6(7(x1)) 9(5(9(x1))) = [1 3 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 5(7(x1)) 9(7(x1)) = [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 1 0] x1 + [0] [0 0 0] [1] = 7(5(x1)) * Step 7: NaturalMI. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: 4(x1) -> 5(2(3(x1))) - Weak TRS: 0(3(x1)) -> 5(3(x1)) 2(4(x1)) -> 0(7(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(x1) -> 9(6(6(x1))) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(3(x1)) -> 6(0(x1)) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + Applied Processor: NaturalMI {miDimension = 4, miDegree = 3, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation (containing no more than 3 non-zero interpretation-entries in the diagonal of the component-wise maxima): Following symbols are considered usable: all TcT has computed the following interpretation: p(0) = [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] p(1) = [1 1 0 0] [0] [0 1 1 0] x1 + [0] [0 0 0 1] [0] [0 0 0 0] [0] p(2) = [1 1 0 1] [0] [0 1 1 1] x1 + [0] [0 0 1 1] [0] [0 0 0 0] [1] p(3) = [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [0] [0 0 0 0] [0] p(4) = [1 1 0 1] [1] [0 1 0 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] p(5) = [1 1 1 0] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] p(6) = [1 0 0 0] [0] [0 1 0 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] p(7) = [1 0 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] p(8) = [1 0 0 0] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [1] p(9) = [1 1 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] Following rules are strictly oriented: 4(x1) = [1 1 0 1] [1] [0 1 0 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] > [1 0 0 0] [0] [0 0 0 0] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 5(2(3(x1))) Following rules are (at-least) weakly oriented: 0(3(x1)) = [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 5(3(x1)) 2(4(x1)) = [1 2 0 2] [2] [0 1 0 1] x1 + [2] [0 0 0 0] [1] [0 0 0 0] [1] >= [1 0 0 1] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 0(7(x1)) 2(7(x1)) = [1 1 1 2] [0] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [1] >= [1 1 1 1] [0] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 1(8(x1)) 2(8(x1)) = [1 1 1 1] [1] [0 1 1 1] x1 + [2] [0 0 0 0] [2] [0 0 0 0] [1] >= [1 1 0 1] [1] [0 1 0 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 4(x1) 2(8(x1)) = [1 1 1 1] [1] [0 1 1 1] x1 + [2] [0 0 0 0] [2] [0 0 0 0] [1] >= [1 0 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 7(x1) 2(8(1(x1))) = [1 2 1 1] [1] [0 1 1 1] x1 + [2] [0 0 0 0] [2] [0 0 0 0] [1] >= [1 0 0 0] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [1] = 8(x1) 4(x1) = [1 1 0 1] [1] [0 1 0 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 1 0 1] [0] [0 1 0 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 9(6(6(x1))) 4(7(x1)) = [1 1 1 2] [1] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [0] [0 0 0 0] [0] = 1(3(x1)) 5(2(6(x1))) = [1 2 0 2] [2] [0 1 0 1] x1 + [3] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 2 0 2] [2] [0 1 0 1] x1 + [3] [0 0 0 0] [1] [0 0 0 0] [0] = 6(2(4(x1))) 5(3(x1)) = [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 6(0(x1)) 5(9(x1)) = [1 2 1 2] [1] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 0(x1) 6(2(x1)) = [1 1 0 1] [0] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 1] [0] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 7(7(x1)) 6(6(x1)) = [1 0 0 0] [0] [0 1 0 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [0] [0 0 0 0] [0] = 3(x1) 6(9(x1)) = [1 1 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 1 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 9(x1) 7(0(x1)) = [1 0 0 0] [0] [0 0 0 0] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 0] [0] [0 0 0 0] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 9(3(x1)) 7(2(x1)) = [1 1 0 1] [1] [0 1 2 2] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 1 0 1] [1] [0 1 0 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 4(x1) 9(x1) = [1 1 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 0 0 1] [0] [0 1 1 1] x1 + [0] [0 0 0 0] [1] [0 0 0 0] [0] = 6(7(x1)) 9(5(9(x1))) = [1 3 2 3] [2] [0 1 1 1] x1 + [2] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 1 1 2] [1] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 5(7(x1)) 9(7(x1)) = [1 1 1 2] [0] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] >= [1 1 1 0] [0] [0 1 1 1] x1 + [1] [0 0 0 0] [1] [0 0 0 0] [0] = 7(5(x1)) * Step 8: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: 0(3(x1)) -> 5(3(x1)) 2(4(x1)) -> 0(7(x1)) 2(7(x1)) -> 1(8(x1)) 2(8(x1)) -> 4(x1) 2(8(x1)) -> 7(x1) 2(8(1(x1))) -> 8(x1) 4(x1) -> 5(2(3(x1))) 4(x1) -> 9(6(6(x1))) 4(7(x1)) -> 1(3(x1)) 5(2(6(x1))) -> 6(2(4(x1))) 5(3(x1)) -> 6(0(x1)) 5(9(x1)) -> 0(x1) 6(2(x1)) -> 7(7(x1)) 6(6(x1)) -> 3(x1) 6(9(x1)) -> 9(x1) 7(0(x1)) -> 9(3(x1)) 7(2(x1)) -> 4(x1) 9(x1) -> 6(7(x1)) 9(5(9(x1))) -> 5(7(x1)) 9(7(x1)) -> 7(5(x1)) - Signature: {0/1,2/1,4/1,5/1,6/1,7/1,9/1} / {1/1,3/1,8/1} - Obligation: innermost derivational complexity wrt. signature {0,1,2,3,4,5,6,7,8,9} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^3))