/export/starexec/sandbox2/solver/bin/starexec_run_tct_rci /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1),O(n^3)) * Step 1: Sum. WORST_CASE(Omega(n^1),O(n^3)) + Considered Problem: - Strict TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {choose,insert,sort} and constructors {0,cons,nil,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:1: Sum. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {choose,insert,sort} and constructors {0,cons,nil,s} + Applied Processor: Sum {left = someStrategy, right = someStrategy} + Details: () ** Step 1.a:2: DecreasingLoops. WORST_CASE(Omega(n^1),?) + Considered Problem: - Strict TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {choose,insert,sort} and constructors {0,cons,nil,s} + Applied Processor: DecreasingLoops {bound = AnyLoop, narrow = 10} + Details: The system has following decreasing Loops: choose(x,cons(y,z),u,v){u -> s(u),v -> s(v)} = choose(x,cons(y,z),s(u),s(v)) ->^+ choose(x,cons(y,z),u,v) = C[choose(x,cons(y,z),u,v) = choose(x,cons(y,z),u,v){}] ** Step 1.b:1: DependencyPairs. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1} / {0/0,cons/2,nil/0,s/1} - Obligation: innermost runtime complexity wrt. defined symbols {choose,insert,sort} and constructors {0,cons,nil,s} + Applied Processor: DependencyPairs {dpKind_ = DT} + Details: We add the following dependency tuples: Strict DPs choose#(x,cons(v,w),y,0()) -> c_1() choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) insert#(x,nil()) -> c_5() sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) sort#(nil()) -> c_7() Weak DPs and mark the set of starting terms. ** Step 1.b:2: PredecessorEstimation. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: choose#(x,cons(v,w),y,0()) -> c_1() choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) insert#(x,nil()) -> c_5() sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) sort#(nil()) -> c_7() - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + Applied Processor: PredecessorEstimation {onSelection = all simple predecessor estimation selector} + Details: We estimate the number of application of {1,5,7} by application of Pre({1,5,7}) = {2,3,4,6}. Here rules are labelled as follows: 1: choose#(x,cons(v,w),y,0()) -> c_1() 2: choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) 3: choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) 4: insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) 5: insert#(x,nil()) -> c_5() 6: sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) 7: sort#(nil()) -> c_7() ** Step 1.b:3: RemoveWeakSuffixes. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) - Weak DPs: choose#(x,cons(v,w),y,0()) -> c_1() insert#(x,nil()) -> c_5() sort#(nil()) -> c_7() - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + Applied Processor: RemoveWeakSuffixes + Details: Consider the dependency graph 1:S:choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) -->_1 insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)):3 -->_1 insert#(x,nil()) -> c_5():6 2:S:choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) -->_1 choose#(x,cons(v,w),y,0()) -> c_1():5 -->_1 choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)):2 -->_1 choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)):1 3:S:insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) -->_1 choose#(x,cons(v,w),y,0()) -> c_1():5 -->_1 choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)):2 -->_1 choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)):1 4:S:sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) -->_2 sort#(nil()) -> c_7():7 -->_1 insert#(x,nil()) -> c_5():6 -->_2 sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)):4 -->_1 insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)):3 5:W:choose#(x,cons(v,w),y,0()) -> c_1() 6:W:insert#(x,nil()) -> c_5() 7:W:sort#(nil()) -> c_7() The following weak DPs constitute a sub-graph of the DG that is closed under successors. The DPs are removed. 7: sort#(nil()) -> c_7() 6: insert#(x,nil()) -> c_5() 5: choose#(x,cons(v,w),y,0()) -> c_1() ** Step 1.b:4: DecomposeDG. WORST_CASE(?,O(n^3)) + Considered Problem: - Strict DPs: choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + 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 sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) and a lower component choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) Further, following extension rules are added to the lower component. sort#(cons(x,y)) -> insert#(x,sort(y)) sort#(cons(x,y)) -> sort#(y) *** Step 1.b:4.a:1: SimplifyRHS. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + Applied Processor: SimplifyRHS + Details: Consider the dependency graph 1:S:sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)) -->_2 sort#(cons(x,y)) -> c_6(insert#(x,sort(y)),sort#(y)):1 Due to missing edges in the depndency graph, the right-hand sides of following rules could be simplified: sort#(cons(x,y)) -> c_6(sort#(y)) *** Step 1.b:4.a:2: UsableRules. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: sort#(cons(x,y)) -> c_6(sort#(y)) - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/1,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + Applied Processor: UsableRules + Details: We replace rewrite rules by usable rules: sort#(cons(x,y)) -> c_6(sort#(y)) *** Step 1.b:4.a:3: NaturalMI. WORST_CASE(?,O(n^1)) + Considered Problem: - Strict DPs: sort#(cons(x,y)) -> c_6(sort#(y)) - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/1,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + 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_6) = {1} Following symbols are considered usable: {choose#,insert#,sort#} TcT has computed the following interpretation: p(0) = [1] p(choose) = [2] x2 + [0] p(cons) = [1] x1 + [1] x2 + [8] p(insert) = [1] p(nil) = [1] p(s) = [4] p(sort) = [2] x1 + [1] p(choose#) = [1] x1 + [4] x3 + [1] p(insert#) = [1] x2 + [0] p(sort#) = [2] x1 + [1] p(c_1) = [1] p(c_2) = [1] p(c_3) = [1] x1 + [0] p(c_4) = [2] p(c_5) = [0] p(c_6) = [1] x1 + [9] p(c_7) = [0] Following rules are strictly oriented: sort#(cons(x,y)) = [2] x + [2] y + [17] > [2] y + [10] = c_6(sort#(y)) Following rules are (at-least) weakly oriented: *** Step 1.b:4.a:4: EmptyProcessor. WORST_CASE(?,O(1)) + Considered Problem: - Weak DPs: sort#(cons(x,y)) -> c_6(sort#(y)) - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/1,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + Applied Processor: EmptyProcessor + Details: The problem is already closed. The intended complexity is O(1). *** Step 1.b:4.b:1: NaturalMI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) - Weak DPs: sort#(cons(x,y)) -> insert#(x,sort(y)) sort#(cons(x,y)) -> sort#(y) - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + 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_2) = {1}, uargs(c_3) = {1}, uargs(c_4) = {1} Following symbols are considered usable: {choose,insert,sort,choose#,insert#,sort#} TcT has computed the following interpretation: p(0) = [0] p(choose) = [1] x2 + [1] p(cons) = [1] x2 + [1] p(insert) = [1] x2 + [1] p(nil) = [0] p(s) = [0] p(sort) = [1] x1 + [0] p(choose#) = [2] x2 + [0] p(insert#) = [2] x2 + [0] p(sort#) = [2] x1 + [0] p(c_1) = [0] p(c_2) = [1] x1 + [0] p(c_3) = [1] x1 + [0] p(c_4) = [1] x1 + [0] p(c_5) = [0] p(c_6) = [2] p(c_7) = [4] Following rules are strictly oriented: choose#(x,cons(v,w),0(),s(z)) = [2] w + [2] > [2] w + [0] = c_2(insert#(x,w)) Following rules are (at-least) weakly oriented: choose#(x,cons(v,w),s(y),s(z)) = [2] w + [2] >= [2] w + [2] = c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) = [2] w + [2] >= [2] w + [2] = c_4(choose#(x,cons(v,w),x,v)) sort#(cons(x,y)) = [2] y + [2] >= [2] y + [0] = insert#(x,sort(y)) sort#(cons(x,y)) = [2] y + [2] >= [2] y + [0] = sort#(y) choose(x,cons(v,w),y,0()) = [1] w + [2] >= [1] w + [2] = cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) = [1] w + [2] >= [1] w + [2] = cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) = [1] w + [2] >= [1] w + [2] = choose(x,cons(v,w),y,z) insert(x,cons(v,w)) = [1] w + [2] >= [1] w + [2] = choose(x,cons(v,w),x,v) insert(x,nil()) = [1] >= [1] = cons(x,nil()) sort(cons(x,y)) = [1] y + [1] >= [1] y + [1] = insert(x,sort(y)) sort(nil()) = [0] >= [0] = nil() *** Step 1.b:4.b:2: NaturalMI. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) - Weak DPs: choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) sort#(cons(x,y)) -> insert#(x,sort(y)) sort#(cons(x,y)) -> sort#(y) - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + 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_2) = {1}, uargs(c_3) = {1}, uargs(c_4) = {1} Following symbols are considered usable: {choose,insert,sort,choose#,insert#,sort#} TcT has computed the following interpretation: p(0) = [4] p(choose) = [1] x2 + [2] p(cons) = [1] x2 + [2] p(insert) = [1] x2 + [2] p(nil) = [0] p(s) = [1] x1 + [0] p(sort) = [1] x1 + [0] p(choose#) = [4] x2 + [0] p(insert#) = [4] x2 + [1] p(sort#) = [4] x1 + [1] p(c_1) = [0] p(c_2) = [1] x1 + [2] p(c_3) = [1] x1 + [0] p(c_4) = [1] x1 + [0] p(c_5) = [4] p(c_6) = [4] x1 + [1] x2 + [1] p(c_7) = [2] Following rules are strictly oriented: insert#(x,cons(v,w)) = [4] w + [9] > [4] w + [8] = c_4(choose#(x,cons(v,w),x,v)) Following rules are (at-least) weakly oriented: choose#(x,cons(v,w),0(),s(z)) = [4] w + [8] >= [4] w + [3] = c_2(insert#(x,w)) choose#(x,cons(v,w),s(y),s(z)) = [4] w + [8] >= [4] w + [8] = c_3(choose#(x,cons(v,w),y,z)) sort#(cons(x,y)) = [4] y + [9] >= [4] y + [1] = insert#(x,sort(y)) sort#(cons(x,y)) = [4] y + [9] >= [4] y + [1] = sort#(y) choose(x,cons(v,w),y,0()) = [1] w + [4] >= [1] w + [4] = cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) = [1] w + [4] >= [1] w + [4] = cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) = [1] w + [4] >= [1] w + [4] = choose(x,cons(v,w),y,z) insert(x,cons(v,w)) = [1] w + [4] >= [1] w + [4] = choose(x,cons(v,w),x,v) insert(x,nil()) = [2] >= [2] = cons(x,nil()) sort(cons(x,y)) = [1] y + [2] >= [1] y + [2] = insert(x,sort(y)) sort(nil()) = [0] >= [0] = nil() *** Step 1.b:4.b:3: Ara. WORST_CASE(?,O(n^2)) + Considered Problem: - Strict DPs: choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) - Weak DPs: choose#(x,cons(v,w),0(),s(z)) -> c_2(insert#(x,w)) insert#(x,cons(v,w)) -> c_4(choose#(x,cons(v,w),x,v)) sort#(cons(x,y)) -> insert#(x,sort(y)) sort#(cons(x,y)) -> sort#(y) - Weak TRS: choose(x,cons(v,w),y,0()) -> cons(x,cons(v,w)) choose(x,cons(v,w),0(),s(z)) -> cons(v,insert(x,w)) choose(x,cons(v,w),s(y),s(z)) -> choose(x,cons(v,w),y,z) insert(x,cons(v,w)) -> choose(x,cons(v,w),x,v) insert(x,nil()) -> cons(x,nil()) sort(cons(x,y)) -> insert(x,sort(y)) sort(nil()) -> nil() - Signature: {choose/4,insert/2,sort/1,choose#/4,insert#/2,sort#/1} / {0/0,cons/2,nil/0,s/1,c_1/0,c_2/1,c_3/1,c_4/1,c_5/0 ,c_6/2,c_7/0} - Obligation: innermost runtime complexity wrt. defined symbols {choose#,insert#,sort#} and constructors {0,cons,nil,s} + Applied Processor: Ara {minDegree = 1, maxDegree = 2, araTimeout = 8, araRuleShifting = Just 1, isBestCase = False, mkCompletelyDefined = False, verboseOutput = False} + Details: Signatures used: ---------------- F (TrsFun "0") :: [] -(0)-> "A"(0, 0) F (TrsFun "choose") :: ["A"(15, 0) x "A"(15, 0) x "A"(0, 0) x "A"(0, 0)] -(0)-> "A"(15, 0) F (TrsFun "cons") :: ["A"(2, 0) x "A"(9, 0)] -(0)-> "A"(2, 7) F (TrsFun "cons") :: ["A"(15, 0) x "A"(15, 0)] -(0)-> "A"(15, 0) F (TrsFun "cons") :: ["A"(9, 0) x "A"(9, 0)] -(0)-> "A"(9, 0) F (TrsFun "insert") :: ["A"(15, 0) x "A"(15, 0)] -(0)-> "A"(15, 0) F (TrsFun "nil") :: [] -(0)-> "A"(15, 0) F (TrsFun "nil") :: [] -(0)-> "A"(15, 8) F (TrsFun "s") :: ["A"(0, 0)] -(0)-> "A"(0, 0) F (TrsFun "s") :: ["A"(5, 0)] -(5)-> "A"(5, 0) F (TrsFun "sort") :: ["A"(15, 0)] -(2)-> "A"(15, 0) F (DpFun "choose") :: ["A"(14, 0) x "A"(2, 7) x "A"(0, 0) x "A"(5, 0)] -(3)-> "A"(13, 7) F (DpFun "insert") :: ["A"(14, 0) x "A"(9, 0)] -(6)-> "A"(1, 8) F (DpFun "sort") :: ["A"(15, 0)] -(15)-> "A"(1, 4) F (ComFun 2) :: ["A"(0, 7)] -(0)-> "A"(13, 7) F (ComFun 3) :: ["A"(13, 7)] -(0)-> "A"(13, 7) F (ComFun 4) :: ["A"(5, 0)] -(0)-> "A"(5, 13) Cost-free Signatures used: -------------------------- Base Constructor Signatures used: --------------------------------- "F (ComFun 2)_A" :: ["A"(0, 0)] -(0)-> "A"(1, 0) "F (ComFun 2)_A" :: ["A"(0, 1)] -(0)-> "A"(0, 1) "F (ComFun 3)_A" :: ["A"(1, 0)] -(0)-> "A"(1, 0) "F (ComFun 3)_A" :: ["A"(0, 1)] -(0)-> "A"(0, 1) "F (ComFun 4)_A" :: ["A"(1, 0)] -(0)-> "A"(1, 0) "F (ComFun 4)_A" :: ["A"(0, 0)] -(0)-> "A"(0, 1) "F (TrsFun \"0\")_A" :: [] -(0)-> "A"(1, 0) "F (TrsFun \"0\")_A" :: [] -(0)-> "A"(0, 1) "F (TrsFun \"cons\")_A" :: ["A"(1, 0) x "A"(1, 0)] -(0)-> "A"(1, 0) "F (TrsFun \"cons\")_A" :: ["A"(0, 0) x "A"(1, 0)] -(0)-> "A"(0, 1) "F (TrsFun \"nil\")_A" :: [] -(0)-> "A"(1, 0) "F (TrsFun \"nil\")_A" :: [] -(0)-> "A"(0, 1) "F (TrsFun \"s\")_A" :: ["A"(1, 0)] -(1)-> "A"(1, 0) "F (TrsFun \"s\")_A" :: ["A"(0, 0)] -(0)-> "A"(0, 1) Following Still Strict Rules were Typed as: ------------------------------------------- 1. Strict: choose#(x,cons(v,w),s(y),s(z)) -> c_3(choose#(x,cons(v,w),y,z)) 2. Weak: WORST_CASE(Omega(n^1),O(n^3))