/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: a(a(x1)) -> b(x1) a(a(a(x1))) -> a(b(a(x1))) a(a(a(a(x1)))) -> a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1))))))) a(a(b(a(x1)))) -> a(b(b(a(b(x1))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1))))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) -> b(b(b(x1))) a(b(a(a(x1)))) -> b(a(b(b(a(x1))))) a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1))))))) a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) -> b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1))))))) - Signature: {a/1} / {b/1} - Obligation: derivational complexity wrt. signature {a,b} + 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 + [2] p(b) = [1] x1 + [2] Following rules are strictly oriented: a(a(x1)) = [1] x1 + [4] > [1] x1 + [2] = b(x1) Following rules are (at-least) weakly oriented: a(a(a(x1))) = [1] x1 + [6] >= [1] x1 + [6] = a(b(a(x1))) a(a(a(a(x1)))) = [1] x1 + [8] >= [1] x1 + [10] = a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = a(a(b(b(a(a(b(x1))))))) a(a(b(a(x1)))) = [1] x1 + [8] >= [1] x1 + [10] = a(b(b(a(b(x1))))) a(a(b(a(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = a(b(a(b(a(b(a(x1))))))) a(a(b(b(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) = [1] x1 + [6] >= [1] x1 + [6] = b(b(b(x1))) a(b(a(a(x1)))) = [1] x1 + [8] >= [1] x1 + [10] = b(a(b(b(a(x1))))) a(b(a(a(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = b(a(a(b(b(a(a(x1))))))) a(b(a(b(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) = [1] x1 + [8] >= [1] x1 + [10] = b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) = [1] x1 + [10] >= [1] x1 + [14] = b(b(b(b(b(b(b(x1))))))) 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: a(a(a(x1))) -> a(b(a(x1))) a(a(a(a(x1)))) -> a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1))))))) a(a(b(a(x1)))) -> a(b(b(a(b(x1))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1))))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) -> b(b(b(x1))) a(b(a(a(x1)))) -> b(a(b(b(a(x1))))) a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1))))))) a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) -> b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1))))))) - Weak TRS: a(a(x1)) -> b(x1) - Signature: {a/1} / {b/1} - Obligation: derivational complexity wrt. signature {a,b} + 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 + [2] p(b) = [1] x1 + [0] Following rules are strictly oriented: a(a(a(x1))) = [1] x1 + [6] > [1] x1 + [4] = a(b(a(x1))) a(a(b(a(x1)))) = [1] x1 + [6] > [1] x1 + [4] = a(b(b(a(b(x1))))) a(a(b(b(a(x1))))) = [1] x1 + [6] > [1] x1 + [4] = a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) = [1] x1 + [4] > [1] x1 + [0] = b(b(b(x1))) a(b(a(a(x1)))) = [1] x1 + [6] > [1] x1 + [4] = b(a(b(b(a(x1))))) a(b(a(b(a(x1))))) = [1] x1 + [6] > [1] x1 + [4] = b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) = [1] x1 + [4] > [1] x1 + [0] = b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) = [1] x1 + [6] > [1] x1 + [4] = b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) = [1] x1 + [4] > [1] x1 + [0] = b(b(b(b(b(b(b(x1))))))) Following rules are (at-least) weakly oriented: a(a(x1)) = [1] x1 + [4] >= [1] x1 + [0] = b(x1) a(a(a(a(x1)))) = [1] x1 + [8] >= [1] x1 + [8] = a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) = [1] x1 + [10] >= [1] x1 + [12] = a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) = [1] x1 + [8] >= [1] x1 + [8] = a(a(b(b(a(a(b(x1))))))) a(a(b(a(a(x1))))) = [1] x1 + [8] >= [1] x1 + [8] = a(b(a(b(a(b(a(x1))))))) a(b(a(a(a(x1))))) = [1] x1 + [8] >= [1] x1 + [8] = b(a(a(b(b(a(a(x1))))))) 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: a(a(a(a(x1)))) -> a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1))))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1))))))) a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1))))))) - Weak TRS: a(a(x1)) -> b(x1) a(a(a(x1))) -> a(b(a(x1))) a(a(b(a(x1)))) -> a(b(b(a(b(x1))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) -> b(b(b(x1))) a(b(a(a(x1)))) -> b(a(b(b(a(x1))))) a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) -> b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1))))))) - Signature: {a/1} / {b/1} - Obligation: derivational complexity wrt. signature {a,b} + 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(a) = [1 1 0] [0] [0 0 1] x1 + [0] [0 0 0] [1] p(b) = [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] Following rules are strictly oriented: a(a(a(a(x1)))) = [1 1 1] [2] [0 0 0] x1 + [1] [0 0 0] [1] > [1 1 1] [0] [0 0 0] x1 + [1] [0 0 0] [1] = a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) = [1 1 1] [3] [0 0 0] x1 + [1] [0 0 0] [1] > [1 1 1] [2] [0 0 0] x1 + [1] [0 0 0] [1] = a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) = [1 1 0] [1] [0 0 0] x1 + [1] [0 0 0] [1] > [1 0 0] [0] [0 0 0] x1 + [1] [0 0 0] [1] = a(a(b(b(a(a(b(x1))))))) a(b(a(a(a(x1))))) = [1 1 1] [1] [0 0 0] x1 + [0] [0 0 0] [1] > [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(a(a(b(b(a(a(x1))))))) Following rules are (at-least) weakly oriented: a(a(x1)) = [1 1 1] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(x1) a(a(a(x1))) = [1 1 1] [1] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(a(x1))) a(a(b(a(x1)))) = [1 1 0] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(b(a(b(x1))))) a(a(b(a(a(x1))))) = [1 1 1] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(a(b(a(b(a(x1))))))) a(a(b(b(a(x1))))) = [1 1 0] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) = [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(b(x1))) a(b(a(a(x1)))) = [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(a(b(b(a(x1))))) a(b(a(b(a(x1))))) = [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) = [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) = [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) = [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 0 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(b(b(b(b(b(x1))))))) * Step 4: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict TRS: a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1))))))) - Weak TRS: a(a(x1)) -> b(x1) a(a(a(x1))) -> a(b(a(x1))) a(a(a(a(x1)))) -> a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1))))))) a(a(b(a(x1)))) -> a(b(b(a(b(x1))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) -> b(b(b(x1))) a(b(a(a(x1)))) -> b(a(b(b(a(x1))))) a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1))))))) a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) -> b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1))))))) - Signature: {a/1} / {b/1} - Obligation: derivational complexity wrt. signature {a,b} + 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(a) = [1 1 0] [0] [0 0 1] x1 + [0] [0 0 0] [1] p(b) = [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] Following rules are strictly oriented: a(a(b(a(a(x1))))) = [1 1 1] [1] [0 0 0] x1 + [1] [0 0 0] [1] > [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(a(b(a(b(a(x1))))))) Following rules are (at-least) weakly oriented: a(a(x1)) = [1 1 1] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(x1) a(a(a(x1))) = [1 1 1] [1] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(a(x1))) a(a(a(a(x1)))) = [1 1 1] [2] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 1] [1] [0 0 0] x1 + [1] [0 0 0] [1] = a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) = [1 1 1] [3] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 1] [3] [0 0 0] x1 + [1] [0 0 0] [1] = a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) = [1 1 1] [1] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [1] [0 0 0] x1 + [1] [0 0 0] [1] = a(a(b(b(a(a(b(x1))))))) a(a(b(a(x1)))) = [1 1 1] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(b(a(b(x1))))) a(a(b(b(a(x1))))) = [1 1 1] [0] [0 0 0] x1 + [1] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [1] = a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) = [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(b(x1))) a(b(a(a(x1)))) = [1 1 1] [1] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(a(b(b(a(x1))))) a(b(a(a(a(x1))))) = [1 1 1] [2] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 1] [2] [0 0 0] x1 + [0] [0 0 0] [0] = b(a(a(b(b(a(a(x1))))))) a(b(a(b(a(x1))))) = [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) = [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) = [1 1 1] [1] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) = [1 1 1] [0] [0 0 0] x1 + [0] [0 0 0] [1] >= [1 1 0] [0] [0 0 0] x1 + [0] [0 0 0] [0] = b(b(b(b(b(b(b(x1))))))) * Step 5: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: a(a(x1)) -> b(x1) a(a(a(x1))) -> a(b(a(x1))) a(a(a(a(x1)))) -> a(a(b(a(a(x1))))) a(a(a(a(a(x1))))) -> a(a(a(b(a(a(a(x1))))))) a(a(a(b(a(x1))))) -> a(a(b(b(a(a(b(x1))))))) a(a(b(a(x1)))) -> a(b(b(a(b(x1))))) a(a(b(a(a(x1))))) -> a(b(a(b(a(b(a(x1))))))) a(a(b(b(a(x1))))) -> a(b(b(b(a(b(b(x1))))))) a(b(a(x1))) -> b(b(b(x1))) a(b(a(a(x1)))) -> b(a(b(b(a(x1))))) a(b(a(a(a(x1))))) -> b(a(a(b(b(a(a(x1))))))) a(b(a(b(a(x1))))) -> b(a(b(b(b(a(b(x1))))))) a(b(b(a(x1)))) -> b(b(b(b(b(x1))))) a(b(b(a(a(x1))))) -> b(b(a(b(b(b(a(x1))))))) a(b(b(b(a(x1))))) -> b(b(b(b(b(b(b(x1))))))) - Signature: {a/1} / {b/1} - Obligation: derivational complexity wrt. signature {a,b} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^1))