/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^2)) * Step 1: NaturalMI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: a(a(x1)) -> b(b(b(x1))) b(x1) -> c(c(d(x1))) b(c(x1)) -> c(b(x1)) b(c(d(x1))) -> a(x1) c(x1) -> d(d(d(x1))) - Signature: {a/1,b/1,c/1} / {d/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c,d} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation: Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [1] x1 + [12] p(b) = [1] x1 + [8] p(c) = [1] x1 + [4] p(d) = [1] x1 + [0] Following rules are strictly oriented: c(x1) = [1] x1 + [4] > [1] x1 + [0] = d(d(d(x1))) Following rules are (at-least) weakly oriented: a(a(x1)) = [1] x1 + [24] >= [1] x1 + [24] = b(b(b(x1))) b(x1) = [1] x1 + [8] >= [1] x1 + [8] = c(c(d(x1))) b(c(x1)) = [1] x1 + [12] >= [1] x1 + [12] = c(b(x1)) b(c(d(x1))) = [1] x1 + [12] >= [1] x1 + [12] = a(x1) * Step 2: WeightGap. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: a(a(x1)) -> b(b(b(x1))) b(x1) -> c(c(d(x1))) b(c(x1)) -> c(b(x1)) b(c(d(x1))) -> a(x1) - Weak TRS: c(x1) -> d(d(d(x1))) - Signature: {a/1,b/1,c/1} / {d/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c,d} + 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(a) = [1] x1 + [0] p(b) = [1] x1 + [9] p(c) = [1] x1 + [0] p(d) = [1] x1 + [0] Following rules are strictly oriented: b(x1) = [1] x1 + [9] > [1] x1 + [0] = c(c(d(x1))) b(c(d(x1))) = [1] x1 + [9] > [1] x1 + [0] = a(x1) Following rules are (at-least) weakly oriented: a(a(x1)) = [1] x1 + [0] >= [1] x1 + [27] = b(b(b(x1))) b(c(x1)) = [1] x1 + [9] >= [1] x1 + [9] = c(b(x1)) c(x1) = [1] x1 + [0] >= [1] x1 + [0] = d(d(d(x1))) Further, it can be verified that all rules not oriented are covered by the weightgap condition. * Step 3: NaturalMI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: a(a(x1)) -> b(b(b(x1))) b(c(x1)) -> c(b(x1)) - Weak TRS: b(x1) -> c(c(d(x1))) b(c(d(x1))) -> a(x1) c(x1) -> d(d(d(x1))) - Signature: {a/1,b/1,c/1} / {d/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c,d} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind triangular matrix interpretation: Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [1] x1 + [14] p(b) = [1] x1 + [9] p(c) = [1] x1 + [4] p(d) = [1] x1 + [1] Following rules are strictly oriented: a(a(x1)) = [1] x1 + [28] > [1] x1 + [27] = b(b(b(x1))) Following rules are (at-least) weakly oriented: b(x1) = [1] x1 + [9] >= [1] x1 + [9] = c(c(d(x1))) b(c(x1)) = [1] x1 + [13] >= [1] x1 + [13] = c(b(x1)) b(c(d(x1))) = [1] x1 + [14] >= [1] x1 + [14] = a(x1) c(x1) = [1] x1 + [4] >= [1] x1 + [3] = d(d(d(x1))) * Step 4: MI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: b(c(x1)) -> c(b(x1)) - Weak TRS: a(a(x1)) -> b(b(b(x1))) b(x1) -> c(c(d(x1))) b(c(d(x1))) -> a(x1) c(x1) -> d(d(d(x1))) - Signature: {a/1,b/1,c/1} / {d/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c,d} + Applied Processor: MI {miKind = Automaton Nothing, miDimension = 3, miUArgs = NoUArgs, miURules = NoURules, miSelector = Just any strict-rules} + Details: We apply a matrix interpretation of kind Automaton Nothing: Following symbols are considered usable: all TcT has computed the following interpretation: p(a) = [1 0 4] [1] [0 0 0] x_1 + [0] [0 0 1] [3] p(b) = [1 0 2] [0] [0 0 0] x_1 + [0] [0 0 1] [2] p(c) = [1 2 0] [0] [0 0 0] x_1 + [0] [0 1 1] [1] p(d) = [1 0 0] [0] [0 0 1] x_1 + [0] [0 0 0] [0] Following rules are strictly oriented: b(c(x1)) = [1 4 2] [2] [0 0 0] x1 + [0] [0 1 1] [3] > [1 0 2] [0] [0 0 0] x1 + [0] [0 0 1] [3] = c(b(x1)) Following rules are (at-least) weakly oriented: a(a(x1)) = [1 0 8] [14] [0 0 0] x1 + [0] [0 0 1] [6] >= [1 0 6] [12] [0 0 0] x1 + [0] [0 0 1] [6] = b(b(b(x1))) b(x1) = [1 0 2] [0] [0 0 0] x1 + [0] [0 0 1] [2] >= [1 0 2] [0] [0 0 0] x1 + [0] [0 0 1] [2] = c(c(d(x1))) b(c(d(x1))) = [1 0 4] [2] [0 0 0] x1 + [0] [0 0 1] [3] >= [1 0 4] [1] [0 0 0] x1 + [0] [0 0 1] [3] = a(x1) c(x1) = [1 2 0] [0] [0 0 0] x1 + [0] [0 1 1] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = d(d(d(x1))) * Step 5: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: a(a(x1)) -> b(b(b(x1))) b(x1) -> c(c(d(x1))) b(c(x1)) -> c(b(x1)) b(c(d(x1))) -> a(x1) c(x1) -> d(d(d(x1))) - Signature: {a/1,b/1,c/1} / {d/1} - Obligation: innermost derivational complexity wrt. signature {a,b,c,d} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))