/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^1)) * Step 1: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f(+(x,y)) -> *(f(x),f(y)) f(+(x,s(0()))) -> +(s(s(0())),f(x)) f(0()) -> s(0()) f(s(0())) -> *(s(s(0())),f(0())) f(s(0())) -> s(s(0())) - Signature: {f/1} / {*/2,+/2,0/0,s/1} - Obligation: innermost derivational complexity wrt. signature {*,+,0,f,s} + 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(*) = [1] x1 + [1] x2 + [0] p(+) = [1] x1 + [1] x2 + [0] p(0) = [0] p(f) = [1] x1 + [1] p(s) = [1] x1 + [0] Following rules are strictly oriented: f(0()) = [1] > [0] = s(0()) f(s(0())) = [1] > [0] = s(s(0())) Following rules are (at-least) weakly oriented: f(+(x,y)) = [1] x + [1] y + [1] >= [1] x + [1] y + [2] = *(f(x),f(y)) f(+(x,s(0()))) = [1] x + [1] >= [1] x + [1] = +(s(s(0())),f(x)) f(s(0())) = [1] >= [1] = *(s(s(0())),f(0())) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 2: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f(+(x,y)) -> *(f(x),f(y)) f(+(x,s(0()))) -> +(s(s(0())),f(x)) f(s(0())) -> *(s(s(0())),f(0())) - Weak TRS: f(0()) -> s(0()) f(s(0())) -> s(s(0())) - Signature: {f/1} / {*/2,+/2,0/0,s/1} - Obligation: innermost derivational complexity wrt. signature {*,+,0,f,s} + 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(*) = [1] x1 + [1] x2 + [10] p(+) = [1] x1 + [1] x2 + [15] p(0) = [0] p(f) = [1] x1 + [4] p(s) = [1] x1 + [1] Following rules are strictly oriented: f(+(x,y)) = [1] x + [1] y + [19] > [1] x + [1] y + [18] = *(f(x),f(y)) Following rules are (at-least) weakly oriented: f(+(x,s(0()))) = [1] x + [20] >= [1] x + [21] = +(s(s(0())),f(x)) f(0()) = [4] >= [1] = s(0()) f(s(0())) = [5] >= [16] = *(s(s(0())),f(0())) f(s(0())) = [5] >= [2] = s(s(0())) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f(+(x,s(0()))) -> +(s(s(0())),f(x)) f(s(0())) -> *(s(s(0())),f(0())) - Weak TRS: f(+(x,y)) -> *(f(x),f(y)) f(0()) -> s(0()) f(s(0())) -> s(s(0())) - Signature: {f/1} / {*/2,+/2,0/0,s/1} - Obligation: innermost derivational complexity wrt. signature {*,+,0,f,s} + Applied Processor: NaturalMI {miDimension = 2, miDegree = 1, 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 1 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(*) = [1 0] x1 + [1 0] x2 + [0] [0 0] [0 0] [4] p(+) = [1 1] x1 + [1 1] x2 + [2] [0 0] [0 0] [4] p(0) = [1] [0] p(f) = [1 1] x1 + [3] [0 0] [4] p(s) = [1 0] x1 + [0] [0 0] [4] Following rules are strictly oriented: f(s(0())) = [8] [4] > [5] [4] = *(s(s(0())),f(0())) Following rules are (at-least) weakly oriented: f(+(x,y)) = [1 1] x + [1 1] y + [9] [0 0] [0 0] [4] >= [1 1] x + [1 1] y + [6] [0 0] [0 0] [4] = *(f(x),f(y)) f(+(x,s(0()))) = [1 1] x + [14] [0 0] [4] >= [1 1] x + [14] [0 0] [4] = +(s(s(0())),f(x)) f(0()) = [4] [4] >= [1] [4] = s(0()) f(s(0())) = [8] [4] >= [1] [4] = s(s(0())) * Step 4: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f(+(x,s(0()))) -> +(s(s(0())),f(x)) - Weak TRS: f(+(x,y)) -> *(f(x),f(y)) f(0()) -> s(0()) f(s(0())) -> *(s(s(0())),f(0())) f(s(0())) -> s(s(0())) - Signature: {f/1} / {*/2,+/2,0/0,s/1} - Obligation: innermost derivational complexity wrt. signature {*,+,0,f,s} + Applied Processor: NaturalMI {miDimension = 3, miDegree = 1, 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 1 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(*) = [1 0 1] [1 0 0] [2] [0 0 0] x1 + [0 0 0] x2 + [0] [0 0 0] [0 0 0] [0] p(+) = [1 4 6] [1 1 0] [7] [0 0 2] x1 + [0 0 2] x2 + [4] [0 0 0] [0 0 0] [4] p(0) = [0] [0] [2] p(f) = [1 1 0] [1] [0 0 3] x1 + [0] [0 0 0] [4] p(s) = [1 0 0] [0] [0 0 1] x1 + [0] [0 0 0] [0] Following rules are strictly oriented: f(+(x,s(0()))) = [1 4 8] [14] [0 0 0] x + [12] [0 0 0] [4] > [1 1 3] [8] [0 0 0] x + [12] [0 0 0] [4] = +(s(s(0())),f(x)) Following rules are (at-least) weakly oriented: f(+(x,y)) = [1 4 8] [1 1 2] [12] [0 0 0] x + [0 0 0] y + [12] [0 0 0] [0 0 0] [4] >= [1 1 0] [1 1 0] [8] [0 0 0] x + [0 0 0] y + [0] [0 0 0] [0 0 0] [0] = *(f(x),f(y)) f(0()) = [1] [6] [4] >= [0] [2] [0] = s(0()) f(s(0())) = [3] [0] [4] >= [3] [0] [0] = *(s(s(0())),f(0())) f(s(0())) = [3] [0] [4] >= [0] [0] [0] = s(s(0())) * Step 5: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: f(+(x,y)) -> *(f(x),f(y)) f(+(x,s(0()))) -> +(s(s(0())),f(x)) f(0()) -> s(0()) f(s(0())) -> *(s(s(0())),f(0())) f(s(0())) -> s(s(0())) - Signature: {f/1} / {*/2,+/2,0/0,s/1} - Obligation: innermost derivational complexity wrt. signature {*,+,0,f,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))