/export/starexec/sandbox2/solver/bin/starexec_run_tct_dc /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?,O(n^2)) * Step 1: DecomposeCP. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: a__f(X) -> f(X) a__f(X) -> g(h(f(X))) mark(f(X)) -> a__f(mark(X)) mark(g(X)) -> g(X) mark(h(X)) -> h(mark(X)) - Signature: {a__f/1,mark/1} / {f/1,g/1,h/1} - Obligation: derivational complexity wrt. signature {a__f,f,g,h,mark} + Applied Processor: DecomposeCP {onSelectionCP_ = any strict-rules, withBoundCP_ = RelativeComp, withCP_ = NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing}} + Details: We first use the processor NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Nothing} to orient following rules strictly: a__f(X) -> f(X) a__f(X) -> g(h(f(X))) mark(f(X)) -> a__f(mark(X)) mark(g(X)) -> g(X) mark(h(X)) -> h(mark(X)) The Processor induces the complexity certificate TIME (?,O(n^2)) BEST_CASE TIME (?,?) SPACE(?,?) Observe that weak rules from Problem (R) are non-size-increasing. Once the complexity of (R) has been assessed, it suffices to consider only rules whose complexity has not been estimated in (R) resulting in the following Problem (S). Overall the certificate is obtained by composition. Problem (S) - Signature: {a__f/1,mark/1} / {f/1,g/1,h/1} - Obligation: derivational complexity wrt. signature {a__f,f,g,h,mark} ** Step 1.a:1: NaturalMI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict TRS: a__f(X) -> f(X) a__f(X) -> g(h(f(X))) mark(f(X)) -> a__f(mark(X)) mark(g(X)) -> g(X) mark(h(X)) -> h(mark(X)) - Signature: {a__f/1,mark/1} / {f/1,g/1,h/1} - Obligation: derivational complexity wrt. signature {a__f,f,g,h,mark} + Applied Processor: NaturalMI {miDimension = 2, miDegree = 2, miKind = Algebraic, uargs = NoUArgs, urules = NoURules, selector = Just first alternative for decompose on 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__f) = [1 4] x1 + [6] [0 1] [2] p(f) = [1 4] x1 + [3] [0 1] [2] p(g) = [1 0] x1 + [0] [0 0] [0] p(h) = [1 0] x1 + [2] [0 1] [1] p(mark) = [1 4] x1 + [4] [0 1] [0] Following rules are strictly oriented: a__f(X) = [1 4] X + [6] [0 1] [2] > [1 4] X + [3] [0 1] [2] = f(X) a__f(X) = [1 4] X + [6] [0 1] [2] > [1 4] X + [5] [0 0] [0] = g(h(f(X))) mark(f(X)) = [1 8] X + [15] [0 1] [2] > [1 8] X + [10] [0 1] [2] = a__f(mark(X)) mark(g(X)) = [1 0] X + [4] [0 0] [0] > [1 0] X + [0] [0 0] [0] = g(X) mark(h(X)) = [1 4] X + [10] [0 1] [1] > [1 4] X + [6] [0 1] [1] = h(mark(X)) Following rules are (at-least) weakly oriented: ** Step 1.a:2: Assumption. WORST_CASE(?,O(1)) + Considered Problem: - Weak TRS: a__f(X) -> f(X) a__f(X) -> g(h(f(X))) mark(f(X)) -> a__f(mark(X)) mark(g(X)) -> g(X) mark(h(X)) -> h(mark(X)) - Signature: {a__f/1,mark/1} / {f/1,g/1,h/1} - Obligation: derivational complexity wrt. signature {a__f,f,g,h,mark} + Applied Processor: Assumption {assumed = Certificate {spaceUB = Unknown, spaceLB = Unknown, timeUB = Poly (Just 0), timeLB = Unknown, timeBCUB = Unknown, timeBCLB = Unknown}} + Details: () ** Step 1.b:1: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Signature: {a__f/1,mark/1} / {f/1,g/1,h/1} - Obligation: derivational complexity wrt. signature {a__f,f,g,h,mark} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(?,O(n^2))