/export/starexec/sandbox/solver/bin/starexec_run_tct_dc /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: f(x,h1(y,z)) -> h2(0(),x,h1(y,z)) f(j(x,y),y) -> g(f(x,k(y))) g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u)) i(f(x,h(y))) -> y i(h2(s(x),y,h1(x,z))) -> z k(h(x)) -> h1(0(),x) k(h1(x,y)) -> h1(s(x),y) - Signature: {f/2,g/1,h2/3,i/1,k/1} / {0/0,h/1,h1/2,j/2,s/1} - Obligation: derivational complexity wrt. signature {0,f,g,h,h1,h2,i,j,k,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(0) = [0] p(f) = [1] x1 + [1] x2 + [3] p(g) = [1] x1 + [0] p(h) = [1] x1 + [0] p(h1) = [1] x1 + [1] x2 + [0] p(h2) = [1] x1 + [1] x2 + [1] x3 + [0] p(i) = [1] x1 + [0] p(j) = [1] x1 + [1] x2 + [0] p(k) = [1] x1 + [1] p(s) = [1] x1 + [0] Following rules are strictly oriented: f(x,h1(y,z)) = [1] x + [1] y + [1] z + [3] > [1] x + [1] y + [1] z + [0] = h2(0(),x,h1(y,z)) i(f(x,h(y))) = [1] x + [1] y + [3] > [1] y + [0] = y k(h(x)) = [1] x + [1] > [1] x + [0] = h1(0(),x) k(h1(x,y)) = [1] x + [1] y + [1] > [1] x + [1] y + [0] = h1(s(x),y) Following rules are (at-least) weakly oriented: f(j(x,y),y) = [1] x + [2] y + [3] >= [1] x + [1] y + [4] = g(f(x,k(y))) g(h2(x,y,h1(z,u))) = [1] u + [1] x + [1] y + [1] z + [0] >= [1] u + [1] x + [1] y + [1] z + [0] = h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) = [2] u + [1] x + [1] y + [2] z + [0] >= [1] u + [1] x + [1] y + [1] z + [0] = h2(s(x),y,h1(s(z),u)) i(h2(s(x),y,h1(x,z))) = [2] x + [1] y + [1] z + [0] >= [1] z + [0] = z 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(j(x,y),y) -> g(f(x,k(y))) g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u)) i(h2(s(x),y,h1(x,z))) -> z - Weak TRS: f(x,h1(y,z)) -> h2(0(),x,h1(y,z)) i(f(x,h(y))) -> y k(h(x)) -> h1(0(),x) k(h1(x,y)) -> h1(s(x),y) - Signature: {f/2,g/1,h2/3,i/1,k/1} / {0/0,h/1,h1/2,j/2,s/1} - Obligation: derivational complexity wrt. signature {0,f,g,h,h1,h2,i,j,k,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(0) = [0] p(f) = [1] x1 + [1] x2 + [0] p(g) = [1] x1 + [5] p(h) = [1] x1 + [3] p(h1) = [1] x1 + [1] x2 + [3] p(h2) = [1] x1 + [1] x2 + [1] x3 + [0] p(i) = [1] x1 + [0] p(j) = [1] x1 + [1] x2 + [0] p(k) = [1] x1 + [0] p(s) = [1] x1 + [0] Following rules are strictly oriented: g(h2(x,y,h1(z,u))) = [1] u + [1] x + [1] y + [1] z + [8] > [1] u + [1] x + [1] y + [1] z + [3] = h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) = [2] u + [1] x + [1] y + [2] z + [6] > [1] u + [1] x + [1] y + [1] z + [3] = h2(s(x),y,h1(s(z),u)) i(h2(s(x),y,h1(x,z))) = [2] x + [1] y + [1] z + [3] > [1] z + [0] = z Following rules are (at-least) weakly oriented: f(x,h1(y,z)) = [1] x + [1] y + [1] z + [3] >= [1] x + [1] y + [1] z + [3] = h2(0(),x,h1(y,z)) f(j(x,y),y) = [1] x + [2] y + [0] >= [1] x + [1] y + [5] = g(f(x,k(y))) i(f(x,h(y))) = [1] x + [1] y + [3] >= [1] y + [0] = y k(h(x)) = [1] x + [3] >= [1] x + [3] = h1(0(),x) k(h1(x,y)) = [1] x + [1] y + [3] >= [1] x + [1] y + [3] = h1(s(x),y) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: f(j(x,y),y) -> g(f(x,k(y))) - Weak TRS: f(x,h1(y,z)) -> h2(0(),x,h1(y,z)) g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u)) i(f(x,h(y))) -> y i(h2(s(x),y,h1(x,z))) -> z k(h(x)) -> h1(0(),x) k(h1(x,y)) -> h1(s(x),y) - Signature: {f/2,g/1,h2/3,i/1,k/1} / {0/0,h/1,h1/2,j/2,s/1} - Obligation: derivational complexity wrt. signature {0,f,g,h,h1,h2,i,j,k,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(0) = [0] p(f) = [1] x1 + [1] x2 + [7] p(g) = [1] x1 + [0] p(h) = [1] x1 + [0] p(h1) = [1] x1 + [1] x2 + [0] p(h2) = [1] x1 + [1] x2 + [1] x3 + [6] p(i) = [1] x1 + [4] p(j) = [1] x1 + [1] x2 + [1] p(k) = [1] x1 + [0] p(s) = [1] x1 + [0] Following rules are strictly oriented: f(j(x,y),y) = [1] x + [2] y + [8] > [1] x + [1] y + [7] = g(f(x,k(y))) Following rules are (at-least) weakly oriented: f(x,h1(y,z)) = [1] x + [1] y + [1] z + [7] >= [1] x + [1] y + [1] z + [6] = h2(0(),x,h1(y,z)) g(h2(x,y,h1(z,u))) = [1] u + [1] x + [1] y + [1] z + [6] >= [1] u + [1] x + [1] y + [1] z + [6] = h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) = [2] u + [1] x + [1] y + [2] z + [7] >= [1] u + [1] x + [1] y + [1] z + [6] = h2(s(x),y,h1(s(z),u)) i(f(x,h(y))) = [1] x + [1] y + [11] >= [1] y + [0] = y i(h2(s(x),y,h1(x,z))) = [2] x + [1] y + [1] z + [10] >= [1] z + [0] = z k(h(x)) = [1] x + [0] >= [1] x + [0] = h1(0(),x) k(h1(x,y)) = [1] x + [1] y + [0] >= [1] x + [1] y + [0] = h1(s(x),y) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: f(x,h1(y,z)) -> h2(0(),x,h1(y,z)) f(j(x,y),y) -> g(f(x,k(y))) g(h2(x,y,h1(z,u))) -> h2(s(x),y,h1(z,u)) h2(x,j(y,h1(z,u)),h1(z,u)) -> h2(s(x),y,h1(s(z),u)) i(f(x,h(y))) -> y i(h2(s(x),y,h1(x,z))) -> z k(h(x)) -> h1(0(),x) k(h1(x,y)) -> h1(s(x),y) - Signature: {f/2,g/1,h2/3,i/1,k/1} / {0/0,h/1,h1/2,j/2,s/1} - Obligation: derivational complexity wrt. signature {0,f,g,h,h1,h2,i,j,k,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))