/export/starexec/sandbox/solver/bin/starexec_run_tct_rci /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),?) * Step 1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2} / {0/0,s/1,t/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g} and constructors {0,s,t} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2} / {0/0,s/1,t/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g} and constructors {0,s,t} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () *** Step 1.a:1.a:1: Ara. MAYBE + Considered Problem: - Strict TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2} / {0/0,s/1,t/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g} and constructors {0,s,t} + Applied Processor: Ara {minDegree = 1, maxDegree = 3, araTimeout = 15, araRuleShifting = Just 1, isBestCase = True, mkCompletelyDefined = False, verboseOutput = False} + Details: Signatures used: ---------------- F (TrsFun "0") :: [] -(0)-> "A"(1) F (TrsFun "f") :: ["A"(0) x "A"(0) x "A"(0)] -(1)-> "A"(0) F (TrsFun "g") :: ["A"(0) x "A"(1)] -(1)-> "A"(0) F (TrsFun "main") :: ["A"(0) x "A"(1)] -(1)-> "A"(0) F (TrsFun "s") :: ["A"(0)] -(0)-> "A"(0) F (TrsFun "s") :: ["A"(1)] -(1)-> "A"(1) F (TrsFun "t") :: [] -(0)-> "A"(0) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) main(x1,x2) -> g(x1,x2) 2. Weak: *** Step 1.a:1.b:1: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2} / {0/0,s/1,t/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g} and constructors {0,s,t} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: g(x,y){x -> s(x),y -> s(y)} = g(s(x),s(y)) ->^+ g(x,y) = C[g(x,y) = g(x,y){}] ** Step 1.b:1: DependencyPairs. MAYBE + Considered Problem: - Strict TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2} / {0/0,s/1,t/0} - Obligation: innermost runtime complexity wrt. defined symbols {f,g} and constructors {0,s,t} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) g#(s(x),0()) -> c_2() g#(s(x),s(y)) -> c_3(g#(x,y)) Weak DPs and mark the set of starting terms. ** Step 1.b:2: PredecessorEstimation. MAYBE + Considered Problem: - Strict DPs: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) g#(s(x),0()) -> c_2() g#(s(x),s(y)) -> c_3(g#(x,y)) - Weak TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {2} by application of Pre({2}) = {1,3}. Here rules are labelled as follows: 1: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) 2: g#(s(x),0()) -> c_2() 3: g#(s(x),s(y)) -> c_3(g#(x,y)) ** Step 1.b:3: RemoveWeakSuffixes. MAYBE + Considered Problem: - Strict DPs: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) g#(s(x),s(y)) -> c_3(g#(x,y)) - Weak DPs: g#(s(x),0()) -> c_2() - Weak TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) -->_2 g#(s(x),s(y)) -> c_3(g#(x,y)):2 -->_2 g#(s(x),0()) -> c_2():3 -->_1 f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)):1 2:S:g#(s(x),s(y)) -> c_3(g#(x,y)) -->_1 g#(s(x),0()) -> c_2():3 -->_1 g#(s(x),s(y)) -> c_3(g#(x,y)):2 3:W:g#(s(x),0()) -> c_2() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 3: g#(s(x),0()) -> c_2() ** Step 1.b:4: UsableRules. MAYBE + Considered Problem: - Strict DPs: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) g#(s(x),s(y)) -> c_3(g#(x,y)) - Weak TRS: f(t(),x,y) -> f(g(x,y),x,s(y)) g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) g#(s(x),s(y)) -> c_3(g#(x,y)) ** Step 1.b:5: DecomposeDG. MAYBE + Considered Problem: - Strict DPs: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) g#(s(x),s(y)) -> c_3(g#(x,y)) - Weak TRS: g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: DecomposeDG {onSelection = all below first cut in WDG, onUpper = Nothing, onLower = Nothing} + Details: We decompose the input problem according to the dependency graph into the upper component f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) and a lower component g#(s(x),s(y)) -> c_3(g#(x,y)) Further, following extension rules are added to the lower component. f#(t(),x,y) -> f#(g(x,y),x,s(y)) f#(t(),x,y) -> g#(x,y) *** Step 1.b:5.a:1: SimplifyRHS. MAYBE + Considered Problem: - Strict DPs: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) - Weak TRS: g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)) -->_1 f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y)),g#(x,y)):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y))) *** Step 1.b:5.a:2: Failure MAYBE + Considered Problem: - Strict DPs: f#(t(),x,y) -> c_1(f#(g(x,y),x,s(y))) - Weak TRS: g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/1,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: EmptyProcessor + Details: The problem is still open. *** Step 1.b:5.b:1: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: g#(s(x),s(y)) -> c_3(g#(x,y)) - Weak DPs: f#(t(),x,y) -> f#(g(x,y),x,s(y)) f#(t(),x,y) -> g#(x,y) - Weak TRS: g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: NaturalMI {miDimension = 1, miDegree = 1, miKind = Algebraic, uargs = UArgs, urules = URules, selector = Just any strict-rules} + Details: We apply a matrix interpretation of kind constructor based matrix interpretation: The following argument positions are considered usable: uargs(c_3) = {1} Following symbols are considered usable: {f#,g#} TcT has computed the following interpretation: p(0) = [1] p(f) = [1] x1 + [1] x2 + [1] p(g) = [2] x2 + [0] p(s) = [1] x1 + [4] p(t) = [0] p(f#) = [9] x2 + [12] p(g#) = [4] x1 + [0] p(c_1) = [2] x1 + [0] p(c_2) = [1] p(c_3) = [1] x1 + [12] Following rules are strictly oriented: g#(s(x),s(y)) = [4] x + [16] > [4] x + [12] = c_3(g#(x,y)) Following rules are (at-least) weakly oriented: f#(t(),x,y) = [9] x + [12] >= [9] x + [12] = f#(g(x,y),x,s(y)) f#(t(),x,y) = [9] x + [12] >= [4] x + [0] = g#(x,y) *** Step 1.b:5.b:2: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: f#(t(),x,y) -> f#(g(x,y),x,s(y)) f#(t(),x,y) -> g#(x,y) g#(s(x),s(y)) -> c_3(g#(x,y)) - Weak TRS: g(s(x),0()) -> t() g(s(x),s(y)) -> g(x,y) - Signature: {f/3,g/2,f#/3,g#/2} / {0/0,s/1,t/0,c_1/2,c_2/0,c_3/1} - Obligation: innermost runtime complexity wrt. defined symbols {f#,g#} and constructors {0,s,t} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). WORST_CASE(Omega(n^1),?)