/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: add(0(),X) -> X add(s(),Y) -> s() dbl(0()) -> 0() dbl(s()) -> s() first(0(),X) -> nil() first(s(),cons(Y)) -> cons(Y) sqr(0()) -> 0() sqr(s()) -> s() terms(N) -> cons(recip(sqr(N))) - Signature: {add/2,dbl/1,first/2,sqr/1,terms/1} / {0/0,cons/1,nil/0,recip/1,s/0} - Obligation: innermost derivational complexity wrt. signature {0,add,cons,dbl,first,nil,recip,s,sqr,terms} + 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) = [11] p(add) = [1] x1 + [1] x2 + [0] p(cons) = [1] x1 + [8] p(dbl) = [1] x1 + [0] p(first) = [1] x1 + [1] x2 + [0] p(nil) = [1] p(recip) = [1] x1 + [0] p(s) = [0] p(sqr) = [1] x1 + [9] p(terms) = [1] x1 + [0] Following rules are strictly oriented: add(0(),X) = [1] X + [11] > [1] X + [0] = X first(0(),X) = [1] X + [11] > [1] = nil() sqr(0()) = [20] > [11] = 0() sqr(s()) = [9] > [0] = s() Following rules are (at-least) weakly oriented: add(s(),Y) = [1] Y + [0] >= [0] = s() dbl(0()) = [11] >= [11] = 0() dbl(s()) = [0] >= [0] = s() first(s(),cons(Y)) = [1] Y + [8] >= [1] Y + [8] = cons(Y) terms(N) = [1] N + [0] >= [1] N + [17] = cons(recip(sqr(N))) 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: add(s(),Y) -> s() dbl(0()) -> 0() dbl(s()) -> s() first(s(),cons(Y)) -> cons(Y) terms(N) -> cons(recip(sqr(N))) - Weak TRS: add(0(),X) -> X first(0(),X) -> nil() sqr(0()) -> 0() sqr(s()) -> s() - Signature: {add/2,dbl/1,first/2,sqr/1,terms/1} / {0/0,cons/1,nil/0,recip/1,s/0} - Obligation: innermost derivational complexity wrt. signature {0,add,cons,dbl,first,nil,recip,s,sqr,terms} + 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(add) = [1] x1 + [1] x2 + [0] p(cons) = [1] x1 + [14] p(dbl) = [1] x1 + [0] p(first) = [1] x1 + [1] x2 + [0] p(nil) = [0] p(recip) = [1] x1 + [8] p(s) = [1] p(sqr) = [1] x1 + [0] p(terms) = [1] x1 + [0] Following rules are strictly oriented: first(s(),cons(Y)) = [1] Y + [15] > [1] Y + [14] = cons(Y) Following rules are (at-least) weakly oriented: add(0(),X) = [1] X + [0] >= [1] X + [0] = X add(s(),Y) = [1] Y + [1] >= [1] = s() dbl(0()) = [0] >= [0] = 0() dbl(s()) = [1] >= [1] = s() first(0(),X) = [1] X + [0] >= [0] = nil() sqr(0()) = [0] >= [0] = 0() sqr(s()) = [1] >= [1] = s() terms(N) = [1] N + [0] >= [1] N + [22] = cons(recip(sqr(N))) 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: add(s(),Y) -> s() dbl(0()) -> 0() dbl(s()) -> s() terms(N) -> cons(recip(sqr(N))) - Weak TRS: add(0(),X) -> X first(0(),X) -> nil() first(s(),cons(Y)) -> cons(Y) sqr(0()) -> 0() sqr(s()) -> s() - Signature: {add/2,dbl/1,first/2,sqr/1,terms/1} / {0/0,cons/1,nil/0,recip/1,s/0} - Obligation: innermost derivational complexity wrt. signature {0,add,cons,dbl,first,nil,recip,s,sqr,terms} + 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(add) = [1] x1 + [1] x2 + [0] p(cons) = [1] x1 + [6] p(dbl) = [1] x1 + [5] p(first) = [1] x1 + [1] x2 + [2] p(nil) = [1] p(recip) = [1] x1 + [2] p(s) = [8] p(sqr) = [1] x1 + [8] p(terms) = [1] x1 + [0] Following rules are strictly oriented: dbl(0()) = [5] > [0] = 0() dbl(s()) = [13] > [8] = s() Following rules are (at-least) weakly oriented: add(0(),X) = [1] X + [0] >= [1] X + [0] = X add(s(),Y) = [1] Y + [8] >= [8] = s() first(0(),X) = [1] X + [2] >= [1] = nil() first(s(),cons(Y)) = [1] Y + [16] >= [1] Y + [6] = cons(Y) sqr(0()) = [8] >= [0] = 0() sqr(s()) = [16] >= [8] = s() terms(N) = [1] N + [0] >= [1] N + [16] = cons(recip(sqr(N))) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 4: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: add(s(),Y) -> s() terms(N) -> cons(recip(sqr(N))) - Weak TRS: add(0(),X) -> X dbl(0()) -> 0() dbl(s()) -> s() first(0(),X) -> nil() first(s(),cons(Y)) -> cons(Y) sqr(0()) -> 0() sqr(s()) -> s() - Signature: {add/2,dbl/1,first/2,sqr/1,terms/1} / {0/0,cons/1,nil/0,recip/1,s/0} - Obligation: innermost derivational complexity wrt. signature {0,add,cons,dbl,first,nil,recip,s,sqr,terms} + 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) = [11] p(add) = [1] x1 + [1] x2 + [4] p(cons) = [1] x1 + [0] p(dbl) = [1] x1 + [12] p(first) = [1] x1 + [1] x2 + [11] p(nil) = [4] p(recip) = [1] x1 + [14] p(s) = [8] p(sqr) = [1] x1 + [4] p(terms) = [1] x1 + [0] Following rules are strictly oriented: add(s(),Y) = [1] Y + [12] > [8] = s() Following rules are (at-least) weakly oriented: add(0(),X) = [1] X + [15] >= [1] X + [0] = X dbl(0()) = [23] >= [11] = 0() dbl(s()) = [20] >= [8] = s() first(0(),X) = [1] X + [22] >= [4] = nil() first(s(),cons(Y)) = [1] Y + [19] >= [1] Y + [0] = cons(Y) sqr(0()) = [15] >= [11] = 0() sqr(s()) = [12] >= [8] = s() terms(N) = [1] N + [0] >= [1] N + [18] = cons(recip(sqr(N))) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 5: WeightGap. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: terms(N) -> cons(recip(sqr(N))) - Weak TRS: add(0(),X) -> X add(s(),Y) -> s() dbl(0()) -> 0() dbl(s()) -> s() first(0(),X) -> nil() first(s(),cons(Y)) -> cons(Y) sqr(0()) -> 0() sqr(s()) -> s() - Signature: {add/2,dbl/1,first/2,sqr/1,terms/1} / {0/0,cons/1,nil/0,recip/1,s/0} - Obligation: innermost derivational complexity wrt. signature {0,add,cons,dbl,first,nil,recip,s,sqr,terms} + 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) = [8] p(add) = [1] x1 + [1] x2 + [0] p(cons) = [1] x1 + [2] p(dbl) = [1] x1 + [10] p(first) = [1] x1 + [1] x2 + [15] p(nil) = [0] p(recip) = [1] x1 + [8] p(s) = [8] p(sqr) = [1] x1 + [2] p(terms) = [1] x1 + [13] Following rules are strictly oriented: terms(N) = [1] N + [13] > [1] N + [12] = cons(recip(sqr(N))) Following rules are (at-least) weakly oriented: add(0(),X) = [1] X + [8] >= [1] X + [0] = X add(s(),Y) = [1] Y + [8] >= [8] = s() dbl(0()) = [18] >= [8] = 0() dbl(s()) = [18] >= [8] = s() first(0(),X) = [1] X + [23] >= [0] = nil() first(s(),cons(Y)) = [1] Y + [25] >= [1] Y + [2] = cons(Y) sqr(0()) = [10] >= [8] = 0() sqr(s()) = [10] >= [8] = s() Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 6: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: add(0(),X) -> X add(s(),Y) -> s() dbl(0()) -> 0() dbl(s()) -> s() first(0(),X) -> nil() first(s(),cons(Y)) -> cons(Y) sqr(0()) -> 0() sqr(s()) -> s() terms(N) -> cons(recip(sqr(N))) - Signature: {add/2,dbl/1,first/2,sqr/1,terms/1} / {0/0,cons/1,nil/0,recip/1,s/0} - Obligation: innermost derivational complexity wrt. signature {0,add,cons,dbl,first,nil,recip,s,sqr,terms} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))