/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxWeightedTrs (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxTypedWeightedTrs (5) CompletionProof [UPPER BOUND(ID), 0 ms] (6) CpxTypedWeightedCompleteTrs (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (8) CpxRNTS (9) CompleteCoflocoProof [FINISHED, 533 ms] (10) BOUNDS(1, n^1) (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (12) TRS for Loop Detection (13) DecreasingLoopProof [LOWER BOUND(ID), 42 ms] (14) BEST (15) proven lower bound (16) LowerBoundPropagationProof [FINISHED, 0 ms] (17) BOUNDS(n^1, INF) (18) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) from(X) -> cons(X, n__from(s(X))) add(0, X) -> X add(s(X), Y) -> s(n__add(activate(X), Y)) len(nil) -> 0 len(cons(X, Z)) -> s(n__len(activate(Z))) fst(X1, X2) -> n__fst(X1, X2) from(X) -> n__from(X) add(X1, X2) -> n__add(X1, X2) len(X) -> n__len(X) activate(n__fst(X1, X2)) -> fst(X1, X2) activate(n__from(X)) -> from(X) activate(n__add(X1, X2)) -> add(X1, X2) activate(n__len(X)) -> len(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil [1] fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] from(X) -> cons(X, n__from(s(X))) [1] add(0, X) -> X [1] add(s(X), Y) -> s(n__add(activate(X), Y)) [1] len(nil) -> 0 [1] len(cons(X, Z)) -> s(n__len(activate(Z))) [1] fst(X1, X2) -> n__fst(X1, X2) [1] from(X) -> n__from(X) [1] add(X1, X2) -> n__add(X1, X2) [1] len(X) -> n__len(X) [1] activate(n__fst(X1, X2)) -> fst(X1, X2) [1] activate(n__from(X)) -> from(X) [1] activate(n__add(X1, X2)) -> add(X1, X2) [1] activate(n__len(X)) -> len(X) [1] activate(X) -> X [1] Rewrite Strategy: INNERMOST ---------------------------------------- (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (4) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: fst(0, Z) -> nil [1] fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] from(X) -> cons(X, n__from(s(X))) [1] add(0, X) -> X [1] add(s(X), Y) -> s(n__add(activate(X), Y)) [1] len(nil) -> 0 [1] len(cons(X, Z)) -> s(n__len(activate(Z))) [1] fst(X1, X2) -> n__fst(X1, X2) [1] from(X) -> n__from(X) [1] add(X1, X2) -> n__add(X1, X2) [1] len(X) -> n__len(X) [1] activate(n__fst(X1, X2)) -> fst(X1, X2) [1] activate(n__from(X)) -> from(X) [1] activate(n__add(X1, X2)) -> add(X1, X2) [1] activate(n__len(X)) -> len(X) [1] activate(X) -> X [1] The TRS has the following type information: fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 0 :: 0:nil:s:cons:n__fst:n__from:n__add:n__len nil :: 0:nil:s:cons:n__fst:n__from:n__add:n__len s :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len cons :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len activate :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len Rewrite Strategy: INNERMOST ---------------------------------------- (5) CompletionProof (UPPER BOUND(ID)) The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: none And the following fresh constants: none ---------------------------------------- (6) Obligation: Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: fst(0, Z) -> nil [1] fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) [1] from(X) -> cons(X, n__from(s(X))) [1] add(0, X) -> X [1] add(s(X), Y) -> s(n__add(activate(X), Y)) [1] len(nil) -> 0 [1] len(cons(X, Z)) -> s(n__len(activate(Z))) [1] fst(X1, X2) -> n__fst(X1, X2) [1] from(X) -> n__from(X) [1] add(X1, X2) -> n__add(X1, X2) [1] len(X) -> n__len(X) [1] activate(n__fst(X1, X2)) -> fst(X1, X2) [1] activate(n__from(X)) -> from(X) [1] activate(n__add(X1, X2)) -> add(X1, X2) [1] activate(n__len(X)) -> len(X) [1] activate(X) -> X [1] The TRS has the following type information: fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len 0 :: 0:nil:s:cons:n__fst:n__from:n__add:n__len nil :: 0:nil:s:cons:n__fst:n__from:n__add:n__len s :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len cons :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__fst :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len activate :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__from :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__add :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len n__len :: 0:nil:s:cons:n__fst:n__from:n__add:n__len -> 0:nil:s:cons:n__fst:n__from:n__add:n__len Rewrite Strategy: INNERMOST ---------------------------------------- (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: 0 => 0 nil => 1 ---------------------------------------- (8) Obligation: Complexity RNTS consisting of the following rules: activate(z) -{ 1 }-> X :|: X >= 0, z = X activate(z) -{ 1 }-> len(X) :|: z = 1 + X, X >= 0 activate(z) -{ 1 }-> fst(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 activate(z) -{ 1 }-> from(X) :|: z = 1 + X, X >= 0 activate(z) -{ 1 }-> add(X1, X2) :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 add(z, z') -{ 1 }-> X :|: z' = X, X >= 0, z = 0 add(z, z') -{ 1 }-> 1 + (1 + activate(X) + Y) :|: z = 1 + X, z' = Y, Y >= 0, X >= 0 add(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 from(z) -{ 1 }-> 1 + X :|: X >= 0, z = X from(z) -{ 1 }-> 1 + X + (1 + (1 + X)) :|: X >= 0, z = X fst(z, z') -{ 1 }-> 1 :|: Z >= 0, z' = Z, z = 0 fst(z, z') -{ 1 }-> 1 + X1 + X2 :|: X1 >= 0, X2 >= 0, z = X1, z' = X2 fst(z, z') -{ 1 }-> 1 + Y + (1 + activate(X) + activate(Z)) :|: Z >= 0, z = 1 + X, Y >= 0, X >= 0, z' = 1 + Y + Z len(z) -{ 1 }-> 0 :|: z = 1 len(z) -{ 1 }-> 1 + X :|: X >= 0, z = X len(z) -{ 1 }-> 1 + (1 + activate(Z)) :|: Z >= 0, X >= 0, z = 1 + X + Z Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (9) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V),0,[fst(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[from(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[add(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V),0,[len(V1, Out)],[V1 >= 0]). eq(start(V1, V),0,[activate(V1, Out)],[V1 >= 0]). eq(fst(V1, V, Out),1,[],[Out = 1,Z1 >= 0,V = Z1,V1 = 0]). eq(fst(V1, V, Out),1,[activate(X3, Ret101),activate(Z2, Ret11)],[Out = 2 + Ret101 + Ret11 + Y1,Z2 >= 0,V1 = 1 + X3,Y1 >= 0,X3 >= 0,V = 1 + Y1 + Z2]). eq(from(V1, Out),1,[],[Out = 3 + 2*X4,X4 >= 0,V1 = X4]). eq(add(V1, V, Out),1,[],[Out = X5,V = X5,X5 >= 0,V1 = 0]). eq(add(V1, V, Out),1,[activate(X6, Ret1011)],[Out = 2 + Ret1011 + Y2,V1 = 1 + X6,V = Y2,Y2 >= 0,X6 >= 0]). eq(len(V1, Out),1,[],[Out = 0,V1 = 1]). eq(len(V1, Out),1,[activate(Z3, Ret111)],[Out = 2 + Ret111,Z3 >= 0,X7 >= 0,V1 = 1 + X7 + Z3]). eq(fst(V1, V, Out),1,[],[Out = 1 + X11 + X21,X11 >= 0,X21 >= 0,V1 = X11,V = X21]). eq(from(V1, Out),1,[],[Out = 1 + X8,X8 >= 0,V1 = X8]). eq(add(V1, V, Out),1,[],[Out = 1 + X12 + X22,X12 >= 0,X22 >= 0,V1 = X12,V = X22]). eq(len(V1, Out),1,[],[Out = 1 + X9,X9 >= 0,V1 = X9]). eq(activate(V1, Out),1,[fst(X13, X23, Ret)],[Out = Ret,X13 >= 0,X23 >= 0,V1 = 1 + X13 + X23]). eq(activate(V1, Out),1,[from(X10, Ret1)],[Out = Ret1,V1 = 1 + X10,X10 >= 0]). eq(activate(V1, Out),1,[add(X14, X24, Ret2)],[Out = Ret2,X14 >= 0,X24 >= 0,V1 = 1 + X14 + X24]). eq(activate(V1, Out),1,[len(X15, Ret3)],[Out = Ret3,V1 = 1 + X15,X15 >= 0]). eq(activate(V1, Out),1,[],[Out = X16,X16 >= 0,V1 = X16]). input_output_vars(fst(V1,V,Out),[V1,V],[Out]). input_output_vars(from(V1,Out),[V1],[Out]). input_output_vars(add(V1,V,Out),[V1,V],[Out]). input_output_vars(len(V1,Out),[V1],[Out]). input_output_vars(activate(V1,Out),[V1],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [from/2] 1. recursive [multiple] : [activate/2,add/3,fst/3,len/2] 2. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into from/2 1. SCC is partially evaluated into activate/2 2. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations from/2 * CE 15 is refined into CE [17] * CE 16 is refined into CE [18] ### Cost equations --> "Loop" of from/2 * CEs [17] --> Loop 11 * CEs [18] --> Loop 12 ### Ranking functions of CR from(V1,Out) #### Partial ranking functions of CR from(V1,Out) ### Specialization of cost equations activate/2 * CE 6 is refined into CE [19] * CE 14 is refined into CE [20] * CE 12 is refined into CE [21] * CE 10 is refined into CE [22] * CE 8 is refined into CE [23] * CE 13 is refined into CE [24,25] * CE 11 is refined into CE [26] * CE 7 is refined into CE [27] * CE 9 is refined into CE [28] ### Cost equations --> "Loop" of activate/2 * CEs [28] --> Loop 13 * CEs [26] --> Loop 14 * CEs [27] --> Loop 15 * CEs [25] --> Loop 16 * CEs [19,20,24] --> Loop 17 * CEs [21] --> Loop 18 * CEs [22] --> Loop 19 * CEs [23] --> Loop 20 ### Ranking functions of CR activate(V1,Out) * RF of phase [13,14,15]: [V1-1] #### Partial ranking functions of CR activate(V1,Out) * Partial RF of phase [13,14,15]: - RF of loop [13:1,13:2]: V1-2 - RF of loop [14:1,15:1]: V1-1 ### Specialization of cost equations start/2 * CE 1 is refined into CE [29] * CE 2 is refined into CE [30,31,32,33,34,35] * CE 3 is refined into CE [36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71] * CE 4 is refined into CE [72,73] * CE 5 is refined into CE [74,75,76,77,78,79] ### Cost equations --> "Loop" of start/2 * CEs [36,37,38,39,40,41] --> Loop 21 * CEs [29,30,31,32,33,34,35,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79] --> Loop 22 ### Ranking functions of CR start(V1,V) #### Partial ranking functions of CR start(V1,V) Computing Bounds ===================================== #### Cost of chains of from(V1,Out): * Chain [12]: 1 with precondition: [V1+1=Out,V1>=0] * Chain [11]: 1 with precondition: [2*V1+3=Out,V1>=0] #### Cost of chains of activate(V1,Out): * Chain [20]: 2 with precondition: [V1=2,Out=0] * Chain [19]: 2 with precondition: [Out=1,V1>=1] * Chain [18]: 2 with precondition: [V1=Out+1,V1>=1] * Chain [17]: 2 with precondition: [V1=Out,V1>=0] * Chain [16]: 2 with precondition: [2*V1+1=Out,V1>=1] * Chain [multiple([13,14,15],[[20],[19],[18],[17],[16]])]: 2*it(13)+4*it(14)+2*it([16])+2*it([17])+4*it([18])+2*it([20])+0 Such that:it([20]) =< V1/5+3/5 aux(5) =< V1 aux(6) =< V1/3+1 aux(7) =< V1/4+3/4 aux(8) =< 2/5*V1+1/5 it(14) =< aux(5) it([20]) =< aux(5) it([17]) =< aux(6) it([18]) =< aux(6) it([20]) =< aux(6) it([16]) =< aux(7) it([18]) =< aux(7) it([20]) =< aux(7) it(13) =< aux(8) it([20]) =< aux(8) it(14) =< it([17])+aux(5) it([20]) =< it([17])+aux(5) with precondition: [Out>=2,2*V1>=Out+1,3*V1>=Out+4] #### Cost of chains of start(V1,V): * Chain [22]: 14*s(1)+28*s(6)+14*s(7)+28*s(8)+14*s(9)+14*s(10)+10*s(11)+20*s(16)+10*s(17)+20*s(18)+10*s(19)+10*s(20)+2*s(121)+4*s(126)+2*s(127)+4*s(128)+2*s(129)+2*s(130)+5 Such that:s(123) =< V1/3+1 s(124) =< V1/4+3/4 s(121) =< V1/5+3/5 s(125) =< 2/5*V1+1/5 aux(9) =< V1 aux(10) =< V1/3+2/3 aux(11) =< V1/4+1/2 aux(12) =< V1/5+2/5 aux(13) =< 2/5*V1 aux(14) =< V aux(15) =< V/3+2/3 aux(16) =< V/4+1/2 aux(17) =< V/5+2/5 aux(18) =< 2/5*V s(1) =< aux(12) s(11) =< aux(17) s(6) =< aux(9) s(1) =< aux(9) s(7) =< aux(10) s(8) =< aux(10) s(1) =< aux(10) s(9) =< aux(11) s(8) =< aux(11) s(1) =< aux(11) s(10) =< aux(13) s(1) =< aux(13) s(6) =< s(7)+aux(9) s(1) =< s(7)+aux(9) s(16) =< aux(14) s(11) =< aux(14) s(17) =< aux(15) s(18) =< aux(15) s(11) =< aux(15) s(19) =< aux(16) s(18) =< aux(16) s(11) =< aux(16) s(20) =< aux(18) s(11) =< aux(18) s(16) =< s(17)+aux(14) s(11) =< s(17)+aux(14) s(126) =< aux(9) s(121) =< aux(9) s(127) =< s(123) s(128) =< s(123) s(121) =< s(123) s(129) =< s(124) s(128) =< s(124) s(121) =< s(124) s(130) =< s(125) s(121) =< s(125) s(126) =< s(127)+aux(9) s(121) =< s(127)+aux(9) with precondition: [V1>=0] * Chain [21]: 2*s(131)+4*s(136)+2*s(137)+4*s(138)+2*s(139)+2*s(140)+5 Such that:s(132) =< V s(133) =< V/3+2/3 s(134) =< V/4+1/2 s(131) =< V/5+2/5 s(135) =< 2/5*V s(136) =< s(132) s(131) =< s(132) s(137) =< s(133) s(138) =< s(133) s(131) =< s(133) s(139) =< s(134) s(138) =< s(134) s(131) =< s(134) s(140) =< s(135) s(131) =< s(135) s(136) =< s(137)+s(132) s(131) =< s(137)+s(132) with precondition: [V1=3,V>=1] Closed-form bounds of start(V1,V): ------------------------------------- * Chain [22] with precondition: [V1>=0] - Upper bound: V1/2+3/2+(32*V1+5+nat(V)*20+28/5*V1+nat(2/5*V)*10+(4/5*V1+2/5)+(2*V1+6)+(14*V1+28)+(7/2*V1+7))+(14/5*V1+28/5)+(2/5*V1+6/5)+nat(V/3+2/3)*30+nat(V/4+1/2)*10+nat(V/5+2/5)*10 - Complexity: n * Chain [21] with precondition: [V1=3,V>=1] - Upper bound: 77/10*V+54/5 - Complexity: n ### Maximum cost of start(V1,V): V1/2+3/2+(nat(V)*16+32*V1+28/5*V1+nat(2/5*V)*8+(4/5*V1+2/5)+(2*V1+6)+(14*V1+28)+(7/2*V1+7))+(14/5*V1+28/5)+(2/5*V1+6/5)+nat(V/3+2/3)*24+nat(V/4+1/2)*8+nat(V/5+2/5)*8+(nat(V)*4+5+nat(2/5*V)*2+nat(V/3+2/3)*6+nat(V/4+1/2)*2+nat(V/5+2/5)*2) Asymptotic class: n * Total analysis performed in 396 ms. ---------------------------------------- (10) BOUNDS(1, n^1) ---------------------------------------- (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (12) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) from(X) -> cons(X, n__from(s(X))) add(0, X) -> X add(s(X), Y) -> s(n__add(activate(X), Y)) len(nil) -> 0 len(cons(X, Z)) -> s(n__len(activate(Z))) fst(X1, X2) -> n__fst(X1, X2) from(X) -> n__from(X) add(X1, X2) -> n__add(X1, X2) len(X) -> n__len(X) activate(n__fst(X1, X2)) -> fst(X1, X2) activate(n__from(X)) -> from(X) activate(n__add(X1, X2)) -> add(X1, X2) activate(n__len(X)) -> len(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (13) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence activate(n__fst(s(X1_0), cons(Y2_0, Z3_0))) ->^+ cons(Y2_0, n__fst(activate(X1_0), activate(Z3_0))) gives rise to a decreasing loop by considering the right hand sides subterm at position [1,0]. The pumping substitution is [X1_0 / n__fst(s(X1_0), cons(Y2_0, Z3_0))]. The result substitution is [ ]. ---------------------------------------- (14) Complex Obligation (BEST) ---------------------------------------- (15) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) from(X) -> cons(X, n__from(s(X))) add(0, X) -> X add(s(X), Y) -> s(n__add(activate(X), Y)) len(nil) -> 0 len(cons(X, Z)) -> s(n__len(activate(Z))) fst(X1, X2) -> n__fst(X1, X2) from(X) -> n__from(X) add(X1, X2) -> n__add(X1, X2) len(X) -> n__len(X) activate(n__fst(X1, X2)) -> fst(X1, X2) activate(n__from(X)) -> from(X) activate(n__add(X1, X2)) -> add(X1, X2) activate(n__len(X)) -> len(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (16) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (17) BOUNDS(n^1, INF) ---------------------------------------- (18) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: fst(0, Z) -> nil fst(s(X), cons(Y, Z)) -> cons(Y, n__fst(activate(X), activate(Z))) from(X) -> cons(X, n__from(s(X))) add(0, X) -> X add(s(X), Y) -> s(n__add(activate(X), Y)) len(nil) -> 0 len(cons(X, Z)) -> s(n__len(activate(Z))) fst(X1, X2) -> n__fst(X1, X2) from(X) -> n__from(X) add(X1, X2) -> n__add(X1, X2) len(X) -> n__len(X) activate(n__fst(X1, X2)) -> fst(X1, X2) activate(n__from(X)) -> from(X) activate(n__add(X1, X2)) -> add(X1, X2) activate(n__len(X)) -> len(X) activate(X) -> X S is empty. Rewrite Strategy: INNERMOST