WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 37 ms] (4) CpxRelTRS (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxWeightedTrs (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxTypedWeightedTrs (11) CompletionProof [UPPER BOUND(ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (14) CpxRNTS (15) CompleteCoflocoProof [FINISHED, 288 ms] (16) BOUNDS(1, n^2) (17) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CpxRelTRS (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (20) typed CpxTrs (21) OrderProof [LOWER BOUND(ID), 0 ms] (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 234 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^1, INF) (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 62 ms] (30) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: g(s(x)) -> f(x) f(0) -> s(0) f(s(x)) -> s(s(g(x))) g(0) -> 0 S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: g(s(x)) -> f(x) f(0) -> s(0) f(s(x)) -> s(s(g(x))) g(0) -> 0 The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 Rewrite Strategy: FULL ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: g(s(x)) -> f(x) f(0) -> s(0) f(s(x)) -> s(s(g(x))) g(0) -> 0 The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 Rewrite Strategy: FULL ---------------------------------------- (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, we have rc = irc. ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: g(s(x)) -> f(x) f(0) -> s(0) f(s(x)) -> s(s(g(x))) g(0) -> 0 The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 Rewrite Strategy: INNERMOST ---------------------------------------- (7) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (8) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: g(s(x)) -> f(x) [1] f(0) -> s(0) [1] f(s(x)) -> s(s(g(x))) [1] g(0) -> 0 [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_g(x_1)) -> g(encArg(x_1)) [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encode_g(x_1) -> g(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0 [0] Rewrite Strategy: INNERMOST ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: g(s(x)) -> f(x) [1] f(0) -> s(0) [1] f(s(x)) -> s(s(g(x))) [1] g(0) -> 0 [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_g(x_1)) -> g(encArg(x_1)) [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encode_g(x_1) -> g(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0 [0] The TRS has the following type information: g :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f s :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f f :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f 0 :: s:0:cons_g:cons_f encArg :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f cons_g :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f cons_f :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f encode_g :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f encode_s :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f encode_f :: s:0:cons_g:cons_f -> s:0:cons_g:cons_f encode_0 :: s:0:cons_g:cons_f Rewrite Strategy: INNERMOST ---------------------------------------- (11) 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: encArg(v0) -> null_encArg [0] encode_g(v0) -> null_encode_g [0] encode_s(v0) -> null_encode_s [0] encode_f(v0) -> null_encode_f [0] encode_0 -> null_encode_0 [0] g(v0) -> null_g [0] f(v0) -> null_f [0] And the following fresh constants: null_encArg, null_encode_g, null_encode_s, null_encode_f, null_encode_0, null_g, null_f ---------------------------------------- (12) 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: g(s(x)) -> f(x) [1] f(0) -> s(0) [1] f(s(x)) -> s(s(g(x))) [1] g(0) -> 0 [1] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(0) -> 0 [0] encArg(cons_g(x_1)) -> g(encArg(x_1)) [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encode_g(x_1) -> g(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0 [0] encArg(v0) -> null_encArg [0] encode_g(v0) -> null_encode_g [0] encode_s(v0) -> null_encode_s [0] encode_f(v0) -> null_encode_f [0] encode_0 -> null_encode_0 [0] g(v0) -> null_g [0] f(v0) -> null_f [0] The TRS has the following type information: g :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f s :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f f :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f 0 :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f encArg :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f cons_g :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f cons_f :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f encode_g :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f encode_s :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f encode_f :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f -> s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f encode_0 :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_encArg :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_encode_g :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_encode_s :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_encode_f :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_encode_0 :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_g :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f null_f :: s:0:cons_g:cons_f:null_encArg:null_encode_g:null_encode_s:null_encode_f:null_encode_0:null_g:null_f Rewrite Strategy: INNERMOST ---------------------------------------- (13) 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 null_encArg => 0 null_encode_g => 0 null_encode_s => 0 null_encode_f => 0 null_encode_0 => 0 null_g => 0 null_f => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: encArg(z) -{ 0 }-> g(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> f(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encode_0 -{ 0 }-> 0 :|: encode_f(z) -{ 0 }-> f(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_g(z) -{ 0 }-> g(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_g(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 f(z) -{ 1 }-> 1 + 0 :|: z = 0 f(z) -{ 1 }-> 1 + (1 + g(x)) :|: x >= 0, z = 1 + x g(z) -{ 1 }-> f(x) :|: x >= 0, z = 1 + x g(z) -{ 1 }-> 0 :|: z = 0 g(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (15) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V),0,[g(V, Out)],[V >= 0]). eq(start(V),0,[f(V, Out)],[V >= 0]). eq(start(V),0,[encArg(V, Out)],[V >= 0]). eq(start(V),0,[fun(V, Out)],[V >= 0]). eq(start(V),0,[fun1(V, Out)],[V >= 0]). eq(start(V),0,[fun2(V, Out)],[V >= 0]). eq(start(V),0,[fun3(Out)],[]). eq(g(V, Out),1,[f(V1, Ret)],[Out = Ret,V1 >= 0,V = 1 + V1]). eq(f(V, Out),1,[],[Out = 1,V = 0]). eq(f(V, Out),1,[g(V2, Ret11)],[Out = 2 + Ret11,V2 >= 0,V = 1 + V2]). eq(g(V, Out),1,[],[Out = 0,V = 0]). eq(encArg(V, Out),0,[encArg(V3, Ret1)],[Out = 1 + Ret1,V = 1 + V3,V3 >= 0]). eq(encArg(V, Out),0,[],[Out = 0,V = 0]). eq(encArg(V, Out),0,[encArg(V4, Ret0),g(Ret0, Ret2)],[Out = Ret2,V = 1 + V4,V4 >= 0]). eq(encArg(V, Out),0,[encArg(V5, Ret01),f(Ret01, Ret3)],[Out = Ret3,V = 1 + V5,V5 >= 0]). eq(fun(V, Out),0,[encArg(V6, Ret02),g(Ret02, Ret4)],[Out = Ret4,V6 >= 0,V = V6]). eq(fun1(V, Out),0,[encArg(V7, Ret12)],[Out = 1 + Ret12,V7 >= 0,V = V7]). eq(fun2(V, Out),0,[encArg(V8, Ret03),f(Ret03, Ret5)],[Out = Ret5,V8 >= 0,V = V8]). eq(fun3(Out),0,[],[Out = 0]). eq(encArg(V, Out),0,[],[Out = 0,V9 >= 0,V = V9]). eq(fun(V, Out),0,[],[Out = 0,V10 >= 0,V = V10]). eq(fun1(V, Out),0,[],[Out = 0,V11 >= 0,V = V11]). eq(fun2(V, Out),0,[],[Out = 0,V12 >= 0,V = V12]). eq(g(V, Out),0,[],[Out = 0,V13 >= 0,V = V13]). eq(f(V, Out),0,[],[Out = 0,V14 >= 0,V = V14]). input_output_vars(g(V,Out),[V],[Out]). input_output_vars(f(V,Out),[V],[Out]). input_output_vars(encArg(V,Out),[V],[Out]). input_output_vars(fun(V,Out),[V],[Out]). input_output_vars(fun1(V,Out),[V],[Out]). input_output_vars(fun2(V,Out),[V],[Out]). input_output_vars(fun3(Out),[],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [f/2,g/2] 1. recursive [non_tail] : [encArg/2] 2. non_recursive : [fun/2] 3. non_recursive : [fun1/2] 4. non_recursive : [fun2/2] 5. non_recursive : [fun3/1] 6. non_recursive : [start/1] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into g/2 1. SCC is partially evaluated into encArg/2 2. SCC is partially evaluated into fun/2 3. SCC is partially evaluated into fun1/2 4. SCC is partially evaluated into fun2/2 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into start/1 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations g/2 * CE 11 is refined into CE [28] * CE 9 is refined into CE [29] * CE 12 is refined into CE [30] * CE 13 is refined into CE [31] * CE 10 is refined into CE [32] ### Cost equations --> "Loop" of g/2 * CEs [32] --> Loop 12 * CEs [28] --> Loop 13 * CEs [29,30,31] --> Loop 14 ### Ranking functions of CR g(V,Out) * RF of phase [12]: [V-1] #### Partial ranking functions of CR g(V,Out) * Partial RF of phase [12]: - RF of loop [12:1]: V-1 ### Specialization of cost equations encArg/2 * CE 18 is refined into CE [33] * CE 16 is refined into CE [34] * CE 17 is refined into CE [35] * CE 14 is refined into CE [36] * CE 15 is refined into CE [37,38,39] * CE 19 is refined into CE [40,41,42] ### Cost equations --> "Loop" of encArg/2 * CEs [39] --> Loop 15 * CEs [42] --> Loop 16 * CEs [37] --> Loop 17 * CEs [38] --> Loop 18 * CEs [40] --> Loop 19 * CEs [34,35] --> Loop 20 * CEs [36,41] --> Loop 21 * CEs [33] --> Loop 22 ### Ranking functions of CR encArg(V,Out) * RF of phase [15,16,17,18,19,20,21]: [V] #### Partial ranking functions of CR encArg(V,Out) * Partial RF of phase [15,16,17,18,19,20,21]: - RF of loop [15:1,16:1,17:1,18:1,19:1,20:1,21:1]: V ### Specialization of cost equations fun/2 * CE 20 is refined into CE [43,44,45,46] * CE 21 is refined into CE [47] ### Cost equations --> "Loop" of fun/2 * CEs [46] --> Loop 23 * CEs [44] --> Loop 24 * CEs [43,45,47] --> Loop 25 ### Ranking functions of CR fun(V,Out) #### Partial ranking functions of CR fun(V,Out) ### Specialization of cost equations fun1/2 * CE 22 is refined into CE [48,49] * CE 23 is refined into CE [50] ### Cost equations --> "Loop" of fun1/2 * CEs [49] --> Loop 26 * CEs [48] --> Loop 27 * CEs [50] --> Loop 28 ### Ranking functions of CR fun1(V,Out) #### Partial ranking functions of CR fun1(V,Out) ### Specialization of cost equations fun2/2 * CE 26 is refined into CE [51,52] * CE 24 is refined into CE [53,54] * CE 25 is refined into CE [55,56,57] * CE 27 is refined into CE [58] ### Cost equations --> "Loop" of fun2/2 * CEs [57] --> Loop 29 * CEs [55] --> Loop 30 * CEs [56] --> Loop 31 * CEs [51,52] --> Loop 32 * CEs [53,54,58] --> Loop 33 ### Ranking functions of CR fun2(V,Out) #### Partial ranking functions of CR fun2(V,Out) ### Specialization of cost equations start/1 * CE 1 is refined into CE [59] * CE 2 is refined into CE [60,61,62] * CE 3 is refined into CE [63] * CE 4 is refined into CE [64,65,66] * CE 5 is refined into CE [67,68] * CE 6 is refined into CE [69,70,71] * CE 7 is refined into CE [72,73,74] * CE 8 is refined into CE [75,76,77,78,79] ### Cost equations --> "Loop" of start/1 * CEs [59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79] --> Loop 34 ### Ranking functions of CR start(V) #### Partial ranking functions of CR start(V) Computing Bounds ===================================== #### Cost of chains of g(V,Out): * Chain [[12],14]: 2*it(12)+1 Such that:it(12) =< Out with precondition: [Out>=2,V>=Out] * Chain [[12],13]: 2*it(12)+2 Such that:it(12) =< Out with precondition: [V=Out,V>=3] * Chain [14]: 1 with precondition: [Out=0,V>=0] * Chain [13]: 2 with precondition: [V=1,Out=1] #### Cost of chains of encArg(V,Out): * Chain [[15,16,17,18,19,20,21],22]: 14*it(15)+4*s(11)+4*s(13)+0 Such that:aux(6) =< V it(15) =< aux(6) aux(3) =< aux(6) s(12) =< it(15)*aux(6) s(14) =< it(15)*aux(3) s(13) =< s(14) s(11) =< s(12) with precondition: [V>=1,Out>=0,V>=Out] * Chain [22]: 0 with precondition: [Out=0,V>=0] #### Cost of chains of fun(V,Out): * Chain [25]: 14*s(16)+4*s(20)+4*s(21)+1 Such that:s(15) =< V s(16) =< s(15) s(17) =< s(15) s(18) =< s(16)*s(15) s(19) =< s(16)*s(17) s(20) =< s(19) s(21) =< s(18) with precondition: [Out=0,V>=0] * Chain [24]: 14*s(23)+4*s(27)+4*s(28)+2 Such that:s(22) =< V s(23) =< s(22) s(24) =< s(22) s(25) =< s(23)*s(22) s(26) =< s(23)*s(24) s(27) =< s(26) s(28) =< s(25) with precondition: [Out=1,V>=1] * Chain [23]: 18*s(30)+4*s(34)+4*s(35)+2 Such that:aux(7) =< V s(30) =< aux(7) s(31) =< aux(7) s(32) =< s(30)*aux(7) s(33) =< s(30)*s(31) s(34) =< s(33) s(35) =< s(32) with precondition: [Out>=2,V>=Out] #### Cost of chains of fun1(V,Out): * Chain [28]: 0 with precondition: [Out=0,V>=0] * Chain [27]: 0 with precondition: [Out=1,V>=0] * Chain [26]: 14*s(39)+4*s(43)+4*s(44)+0 Such that:s(38) =< V s(39) =< s(38) s(40) =< s(38) s(41) =< s(39)*s(38) s(42) =< s(39)*s(40) s(43) =< s(42) s(44) =< s(41) with precondition: [V>=1,Out>=1,V+1>=Out] #### Cost of chains of fun2(V,Out): * Chain [33]: 14*s(46)+4*s(50)+4*s(51)+0 Such that:s(45) =< V s(46) =< s(45) s(47) =< s(45) s(48) =< s(46)*s(45) s(49) =< s(46)*s(47) s(50) =< s(49) s(51) =< s(48) with precondition: [Out=0,V>=0] * Chain [32]: 14*s(53)+4*s(57)+4*s(58)+1 Such that:s(52) =< V s(53) =< s(52) s(54) =< s(52) s(55) =< s(53)*s(52) s(56) =< s(53)*s(54) s(57) =< s(56) s(58) =< s(55) with precondition: [Out=1,V>=0] * Chain [31]: 14*s(60)+4*s(64)+4*s(65)+2 Such that:s(59) =< V s(60) =< s(59) s(61) =< s(59) s(62) =< s(60)*s(59) s(63) =< s(60)*s(61) s(64) =< s(63) s(65) =< s(62) with precondition: [Out=2,V>=1] * Chain [30]: 14*s(67)+4*s(71)+4*s(72)+3 Such that:s(66) =< V s(67) =< s(66) s(68) =< s(66) s(69) =< s(67)*s(66) s(70) =< s(67)*s(68) s(71) =< s(70) s(72) =< s(69) with precondition: [Out=3,V>=2] * Chain [29]: 18*s(74)+4*s(78)+4*s(79)+3 Such that:aux(8) =< V s(74) =< aux(8) s(75) =< aux(8) s(76) =< s(74)*aux(8) s(77) =< s(74)*s(75) s(78) =< s(77) s(79) =< s(76) with precondition: [Out>=4,V+1>=Out] #### Cost of chains of start(V): * Chain [34]: 156*s(83)+40*s(91)+40*s(92)+3 Such that:aux(9) =< V s(83) =< aux(9) s(88) =< aux(9) s(89) =< s(83)*aux(9) s(90) =< s(83)*s(88) s(91) =< s(90) s(92) =< s(89) with precondition: [] Closed-form bounds of start(V): ------------------------------------- * Chain [34] with precondition: [] - Upper bound: nat(V)*156+3+nat(V)*80*nat(V) - Complexity: n^2 ### Maximum cost of start(V): nat(V)*156+3+nat(V)*80*nat(V) Asymptotic class: n^2 * Total analysis performed in 269 ms. ---------------------------------------- (16) BOUNDS(1, n^2) ---------------------------------------- (17) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (18) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: g(s(x)) -> f(x) f(0') -> s(0') f(s(x)) -> s(s(g(x))) g(0') -> 0' The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0' Rewrite Strategy: FULL ---------------------------------------- (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (20) Obligation: TRS: Rules: g(s(x)) -> f(x) f(0') -> s(0') f(s(x)) -> s(s(g(x))) g(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0' Types: g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f 0' :: s:0':cons_g:cons_f encArg :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_0 :: s:0':cons_g:cons_f hole_s:0':cons_g:cons_f1_2 :: s:0':cons_g:cons_f gen_s:0':cons_g:cons_f2_2 :: Nat -> s:0':cons_g:cons_f ---------------------------------------- (21) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: g, f, encArg They will be analysed ascendingly in the following order: g = f g < encArg f < encArg ---------------------------------------- (22) Obligation: TRS: Rules: g(s(x)) -> f(x) f(0') -> s(0') f(s(x)) -> s(s(g(x))) g(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0' Types: g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f 0' :: s:0':cons_g:cons_f encArg :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_0 :: s:0':cons_g:cons_f hole_s:0':cons_g:cons_f1_2 :: s:0':cons_g:cons_f gen_s:0':cons_g:cons_f2_2 :: Nat -> s:0':cons_g:cons_f Generator Equations: gen_s:0':cons_g:cons_f2_2(0) <=> 0' gen_s:0':cons_g:cons_f2_2(+(x, 1)) <=> s(gen_s:0':cons_g:cons_f2_2(x)) The following defined symbols remain to be analysed: f, g, encArg They will be analysed ascendingly in the following order: g = f g < encArg f < encArg ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: f(gen_s:0':cons_g:cons_f2_2(*(2, n4_2))) -> gen_s:0':cons_g:cons_f2_2(+(1, *(2, n4_2))), rt in Omega(1 + n4_2) Induction Base: f(gen_s:0':cons_g:cons_f2_2(*(2, 0))) ->_R^Omega(1) s(0') Induction Step: f(gen_s:0':cons_g:cons_f2_2(*(2, +(n4_2, 1)))) ->_R^Omega(1) s(s(g(gen_s:0':cons_g:cons_f2_2(+(1, *(2, n4_2)))))) ->_R^Omega(1) s(s(f(gen_s:0':cons_g:cons_f2_2(*(2, n4_2))))) ->_IH s(s(gen_s:0':cons_g:cons_f2_2(+(1, *(2, c5_2))))) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: g(s(x)) -> f(x) f(0') -> s(0') f(s(x)) -> s(s(g(x))) g(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0' Types: g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f 0' :: s:0':cons_g:cons_f encArg :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_0 :: s:0':cons_g:cons_f hole_s:0':cons_g:cons_f1_2 :: s:0':cons_g:cons_f gen_s:0':cons_g:cons_f2_2 :: Nat -> s:0':cons_g:cons_f Generator Equations: gen_s:0':cons_g:cons_f2_2(0) <=> 0' gen_s:0':cons_g:cons_f2_2(+(x, 1)) <=> s(gen_s:0':cons_g:cons_f2_2(x)) The following defined symbols remain to be analysed: f, g, encArg They will be analysed ascendingly in the following order: g = f g < encArg f < encArg ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) Obligation: TRS: Rules: g(s(x)) -> f(x) f(0') -> s(0') f(s(x)) -> s(s(g(x))) g(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(0') -> 0' encArg(cons_g(x_1)) -> g(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encode_g(x_1) -> g(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0' Types: g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f 0' :: s:0':cons_g:cons_f encArg :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f cons_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_g :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_s :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_f :: s:0':cons_g:cons_f -> s:0':cons_g:cons_f encode_0 :: s:0':cons_g:cons_f hole_s:0':cons_g:cons_f1_2 :: s:0':cons_g:cons_f gen_s:0':cons_g:cons_f2_2 :: Nat -> s:0':cons_g:cons_f Lemmas: f(gen_s:0':cons_g:cons_f2_2(*(2, n4_2))) -> gen_s:0':cons_g:cons_f2_2(+(1, *(2, n4_2))), rt in Omega(1 + n4_2) Generator Equations: gen_s:0':cons_g:cons_f2_2(0) <=> 0' gen_s:0':cons_g:cons_f2_2(+(x, 1)) <=> s(gen_s:0':cons_g:cons_f2_2(x)) The following defined symbols remain to be analysed: g, encArg They will be analysed ascendingly in the following order: g = f g < encArg f < encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_s:0':cons_g:cons_f2_2(n237_2)) -> gen_s:0':cons_g:cons_f2_2(n237_2), rt in Omega(0) Induction Base: encArg(gen_s:0':cons_g:cons_f2_2(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_s:0':cons_g:cons_f2_2(+(n237_2, 1))) ->_R^Omega(0) s(encArg(gen_s:0':cons_g:cons_f2_2(n237_2))) ->_IH s(gen_s:0':cons_g:cons_f2_2(c238_2)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (30) BOUNDS(1, INF)