/export/starexec/sandbox2/solver/bin/starexec_run_tct_rc /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^1)) * Step 1: Sum WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: b(x,b(z,y)) -> f(b(f(f(z)),c(x,z,y))) b(y,z) -> z f(c(a(),z,x)) -> b(a(),z) - Signature: {b/2,f/1} / {a/0,c/3} - Obligation: runtime complexity wrt. defined symbols {b,f} and constructors {a,c} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () * Step 2: DependencyPairs WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: b(x,b(z,y)) -> f(b(f(f(z)),c(x,z,y))) b(y,z) -> z f(c(a(),z,x)) -> b(a(),z) - Signature: {b/2,f/1} / {a/0,c/3} - Obligation: runtime complexity wrt. defined symbols {b,f} and constructors {a,c} + Applied Processor: DependencyPairs {dpKind_ = WIDP} + Details: We add the following weak dependency pairs: Strict DPs b#(x,b(z,y)) -> c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) -> c_2(z) f#(c(a(),z,x)) -> c_3(b#(a(),z)) Weak DPs and mark the set of starting terms. * Step 3: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: b#(x,b(z,y)) -> c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) -> c_2(z) f#(c(a(),z,x)) -> c_3(b#(a(),z)) - Strict TRS: b(x,b(z,y)) -> f(b(f(f(z)),c(x,z,y))) b(y,z) -> z f(c(a(),z,x)) -> b(a(),z) - Signature: {b/2,f/1,b#/2,f#/1} / {a/0,c/3,c_1/1,c_2/1,c_3/1} - Obligation: runtime complexity wrt. defined symbols {b#,f#} and constructors {a,c} + Applied Processor: NaturalMI {miDimension = 2, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any intersect of strict-rules and rewrite-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation (containing no more than 1 non-zero interpretation-entries in the diagonal of the component-wise maxima): The following argument positions are considered usable: uargs(b) = {1,2}, uargs(c) = {1,2,3}, uargs(f) = {1}, uargs(b#) = {2}, uargs(f#) = {1}, uargs(c_1) = {1}, uargs(c_2) = {1}, uargs(c_3) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [0] [0] p(b) = [2 0] x1 + [1 1] x2 + [0] [4 2] [1 3] [1] p(c) = [1 0] x1 + [1 1] x2 + [1 0] x3 + [0] [0 0] [0 0] [0 0] [0] p(f) = [1 0] x1 + [0] [4 0] [2] p(b#) = [2 0] x1 + [1 1] x2 + [1] [1 1] [0 2] [0] p(f#) = [1 0] x1 + [1] [0 0] [1] p(c_1) = [2 0] x1 + [0] [0 2] [0] p(c_2) = [1 0] x1 + [1] [0 2] [0] p(c_3) = [1 0] x1 + [0] [0 0] [0] Following rules are strictly oriented: b(x,b(z,y)) = [2 0] x + [2 4] y + [ 6 2] z + [1] [4 2] [4 10] [14 6] [4] > [1 0] x + [1 0] y + [ 3 1] z + [0] [4 0] [4 0] [12 4] [2] = f(b(f(f(z)),c(x,z,y))) Following rules are (at-least) weakly oriented: b#(x,b(z,y)) = [2 0] x + [2 4] y + [6 2] z + [2] [1 1] [2 6] [8 4] [2] >= [2 0] x + [2 0] y + [6 2] z + [2] [0 0] [0 0] [0 0] [2] = c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) = [2 0] y + [1 1] z + [1] [1 1] [0 2] [0] >= [1 0] z + [1] [0 2] [0] = c_2(z) f#(c(a(),z,x)) = [1 0] x + [1 1] z + [1] [0 0] [0 0] [1] >= [1 1] z + [1] [0 0] [0] = c_3(b#(a(),z)) b(y,z) = [2 0] y + [1 1] z + [0] [4 2] [1 3] [1] >= [1 0] z + [0] [0 1] [0] = z f(c(a(),z,x)) = [1 0] x + [1 1] z + [0] [4 0] [4 4] [2] >= [1 1] z + [0] [1 3] [1] = b(a(),z) * Step 4: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: b#(x,b(z,y)) -> c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) -> c_2(z) f#(c(a(),z,x)) -> c_3(b#(a(),z)) - Strict TRS: b(y,z) -> z f(c(a(),z,x)) -> b(a(),z) - Weak TRS: b(x,b(z,y)) -> f(b(f(f(z)),c(x,z,y))) - Signature: {b/2,f/1,b#/2,f#/1} / {a/0,c/3,c_1/1,c_2/1,c_3/1} - Obligation: runtime complexity wrt. defined symbols {b#,f#} and constructors {a,c} + Applied Processor: NaturalMI {miDimension = 2, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any intersect of strict-rules and rewrite-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation (containing no more than 1 non-zero interpretation-entries in the diagonal of the component-wise maxima): The following argument positions are considered usable: uargs(b) = {1,2}, uargs(c) = {1,2,3}, uargs(f) = {1}, uargs(b#) = {2}, uargs(f#) = {1}, uargs(c_1) = {1}, uargs(c_2) = {1}, uargs(c_3) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [0] [4] p(b) = [1 1] x1 + [1 1] x2 + [0] [4 0] [2 2] [5] p(c) = [1 0] x1 + [1 1] x2 + [1 0] x3 + [5] [0 0] [0 0] [0 0] [0] p(f) = [1 0] x1 + [0] [2 0] [0] p(b#) = [3 2] x1 + [2 2] x2 + [4] [1 3] [4 0] [0] p(f#) = [2 0] x1 + [3] [0 0] [1] p(c_1) = [1 0] x1 + [0] [0 0] [0] p(c_2) = [2 2] x1 + [0] [1 0] [0] p(c_3) = [1 0] x1 + [0] [0 0] [0] Following rules are strictly oriented: b#(x,b(z,y)) = [3 2] x + [6 6] y + [10 2] z + [14] [1 3] [4 4] [ 4 4] [0] > [2 0] x + [2 0] y + [8 2] z + [13] [0 0] [0 0] [0 0] [0] = c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) = [3 2] y + [2 2] z + [4] [1 3] [4 0] [0] > [2 2] z + [0] [1 0] [0] = c_2(z) f#(c(a(),z,x)) = [2 0] x + [2 2] z + [13] [0 0] [0 0] [1] > [2 2] z + [12] [0 0] [0] = c_3(b#(a(),z)) f(c(a(),z,x)) = [1 0] x + [1 1] z + [5] [2 0] [2 2] [10] > [1 1] z + [4] [2 2] [5] = b(a(),z) Following rules are (at-least) weakly oriented: b(x,b(z,y)) = [1 1] x + [3 3] y + [ 5 1] z + [5] [4 0] [6 6] [10 2] [15] >= [1 0] x + [1 0] y + [4 1] z + [5] [2 0] [2 0] [8 2] [10] = f(b(f(f(z)),c(x,z,y))) b(y,z) = [1 1] y + [1 1] z + [0] [4 0] [2 2] [5] >= [1 0] z + [0] [0 1] [0] = z * Step 5: NaturalMI WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: b(y,z) -> z - Weak DPs: b#(x,b(z,y)) -> c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) -> c_2(z) f#(c(a(),z,x)) -> c_3(b#(a(),z)) - Weak TRS: b(x,b(z,y)) -> f(b(f(f(z)),c(x,z,y))) f(c(a(),z,x)) -> b(a(),z) - Signature: {b/2,f/1,b#/2,f#/1} / {a/0,c/3,c_1/1,c_2/1,c_3/1} - Obligation: runtime complexity wrt. defined symbols {b#,f#} and constructors {a,c} + Applied Processor: NaturalMI {miDimension = 2, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any intersect of strict-rules and rewrite-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation (containing no more than 1 non-zero interpretation-entries in the diagonal of the component-wise maxima): The following argument positions are considered usable: uargs(b) = {1,2}, uargs(c) = {1,2,3}, uargs(f) = {1}, uargs(b#) = {2}, uargs(f#) = {1}, uargs(c_1) = {1}, uargs(c_2) = {1}, uargs(c_3) = {1} Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [0] [0] p(b) = [2 0] x1 + [1 1] x2 + [1] [4 2] [3 2] [3] p(c) = [1 0] x1 + [1 1] x2 + [1 0] x3 + [2] [0 0] [0 0] [0 0] [0] p(f) = [1 0] x1 + [0] [4 0] [0] p(b#) = [5 2] x1 + [2 2] x2 + [4] [5 5] [1 0] [1] p(f#) = [4 0] x1 + [0] [3 0] [4] p(c_1) = [1 0] x1 + [0] [0 0] [2] p(c_2) = [2 2] x1 + [4] [0 0] [1] p(c_3) = [2 0] x1 + [0] [1 1] [4] Following rules are strictly oriented: b(y,z) = [2 0] y + [1 1] z + [1] [4 2] [3 2] [3] > [1 0] z + [0] [0 1] [0] = z Following rules are (at-least) weakly oriented: b#(x,b(z,y)) = [5 2] x + [8 6] y + [12 4] z + [12] [5 5] [1 1] [ 2 0] [2] >= [4 0] x + [4 0] y + [12 4] z + [12] [0 0] [0 0] [ 0 0] [2] = c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) = [5 2] y + [2 2] z + [4] [5 5] [1 0] [1] >= [2 2] z + [4] [0 0] [1] = c_2(z) f#(c(a(),z,x)) = [4 0] x + [4 4] z + [8] [3 0] [3 3] [10] >= [4 4] z + [8] [3 2] [9] = c_3(b#(a(),z)) b(x,b(z,y)) = [2 0] x + [4 3] y + [ 6 2] z + [5] [4 2] [9 7] [14 4] [12] >= [1 0] x + [1 0] y + [ 3 1] z + [3] [4 0] [4 0] [12 4] [12] = f(b(f(f(z)),c(x,z,y))) f(c(a(),z,x)) = [1 0] x + [1 1] z + [2] [4 0] [4 4] [8] >= [1 1] z + [1] [3 2] [3] = b(a(),z) * Step 6: EmptyProcessor WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: b#(x,b(z,y)) -> c_1(f#(b(f(f(z)),c(x,z,y)))) b#(y,z) -> c_2(z) f#(c(a(),z,x)) -> c_3(b#(a(),z)) - Weak TRS: b(x,b(z,y)) -> f(b(f(f(z)),c(x,z,y))) b(y,z) -> z f(c(a(),z,x)) -> b(a(),z) - Signature: {b/2,f/1,b#/2,f#/1} / {a/0,c/3,c_1/1,c_2/1,c_3/1} - Obligation: runtime complexity wrt. defined symbols {b#,f#} and constructors {a,c} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))