33.62/9.55 WORST_CASE(Omega(n^1), O(n^1)) 33.62/9.56 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 33.62/9.56 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 33.62/9.56 33.62/9.56 33.62/9.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.62/9.56 33.62/9.56 (0) CpxTRS 33.62/9.56 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 33.62/9.56 (2) CpxWeightedTrs 33.62/9.56 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 33.62/9.56 (4) CpxTypedWeightedTrs 33.62/9.56 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 33.62/9.56 (6) CpxTypedWeightedCompleteTrs 33.62/9.56 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 33.62/9.56 (8) CpxRNTS 33.62/9.56 (9) CompleteCoflocoProof [FINISHED, 740 ms] 33.62/9.56 (10) BOUNDS(1, n^1) 33.62/9.56 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 33.62/9.56 (12) TRS for Loop Detection 33.62/9.56 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 33.62/9.56 (14) BEST 33.62/9.56 (15) proven lower bound 33.62/9.56 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 33.62/9.56 (17) BOUNDS(n^1, INF) 33.62/9.56 (18) TRS for Loop Detection 33.62/9.56 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (0) 33.62/9.56 Obligation: 33.62/9.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.62/9.56 33.62/9.56 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) 33.62/9.56 double(0) -> 0 33.62/9.56 double(s(x)) -> s(s(double(x))) 33.62/9.56 plus(0, y) -> y 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) 33.62/9.56 33.62/9.56 S is empty. 33.62/9.56 Rewrite Strategy: INNERMOST 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 33.62/9.56 Transformed relative TRS to weighted TRS 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (2) 33.62/9.56 Obligation: 33.62/9.56 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 33.62/9.56 33.62/9.56 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x [1] 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) [1] 33.62/9.56 double(0) -> 0 [1] 33.62/9.56 double(s(x)) -> s(s(double(x))) [1] 33.62/9.56 plus(0, y) -> y [1] 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) [1] 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) [1] 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) [1] 33.62/9.56 33.62/9.56 Rewrite Strategy: INNERMOST 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 33.62/9.56 Infered types. 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (4) 33.62/9.56 Obligation: 33.62/9.56 Runtime Complexity Weighted TRS with Types. 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x [1] 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) [1] 33.62/9.56 double(0) -> 0 [1] 33.62/9.56 double(s(x)) -> s(s(double(x))) [1] 33.62/9.56 plus(0, y) -> y [1] 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) [1] 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) [1] 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) [1] 33.62/9.56 33.62/9.56 The TRS has the following type information: 33.62/9.56 minus :: 0:s -> 0:s -> 0:s 33.62/9.56 0 :: 0:s 33.62/9.56 s :: 0:s -> 0:s 33.62/9.56 double :: 0:s -> 0:s 33.62/9.56 plus :: 0:s -> 0:s -> 0:s 33.62/9.56 33.62/9.56 Rewrite Strategy: INNERMOST 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (5) CompletionProof (UPPER BOUND(ID)) 33.62/9.56 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 33.62/9.56 33.62/9.56 minus(v0, v1) -> null_minus [0] 33.62/9.56 double(v0) -> null_double [0] 33.62/9.56 plus(v0, v1) -> null_plus [0] 33.62/9.56 33.62/9.56 And the following fresh constants: null_minus, null_double, null_plus 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (6) 33.62/9.56 Obligation: 33.62/9.56 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 33.62/9.56 33.62/9.56 Runtime Complexity Weighted TRS with Types. 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x [1] 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) [1] 33.62/9.56 double(0) -> 0 [1] 33.62/9.56 double(s(x)) -> s(s(double(x))) [1] 33.62/9.56 plus(0, y) -> y [1] 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) [1] 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) [1] 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) [1] 33.62/9.56 minus(v0, v1) -> null_minus [0] 33.62/9.56 double(v0) -> null_double [0] 33.62/9.56 plus(v0, v1) -> null_plus [0] 33.62/9.56 33.62/9.56 The TRS has the following type information: 33.62/9.56 minus :: 0:s:null_minus:null_double:null_plus -> 0:s:null_minus:null_double:null_plus -> 0:s:null_minus:null_double:null_plus 33.62/9.56 0 :: 0:s:null_minus:null_double:null_plus 33.62/9.56 s :: 0:s:null_minus:null_double:null_plus -> 0:s:null_minus:null_double:null_plus 33.62/9.56 double :: 0:s:null_minus:null_double:null_plus -> 0:s:null_minus:null_double:null_plus 33.62/9.56 plus :: 0:s:null_minus:null_double:null_plus -> 0:s:null_minus:null_double:null_plus -> 0:s:null_minus:null_double:null_plus 33.62/9.56 null_minus :: 0:s:null_minus:null_double:null_plus 33.62/9.56 null_double :: 0:s:null_minus:null_double:null_plus 33.62/9.56 null_plus :: 0:s:null_minus:null_double:null_plus 33.62/9.56 33.62/9.56 Rewrite Strategy: INNERMOST 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 33.62/9.56 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 33.62/9.56 The constant constructors are abstracted as follows: 33.62/9.56 33.62/9.56 0 => 0 33.62/9.56 null_minus => 0 33.62/9.56 null_double => 0 33.62/9.56 null_plus => 0 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (8) 33.62/9.56 Obligation: 33.62/9.56 Complexity RNTS consisting of the following rules: 33.62/9.56 33.62/9.56 double(z) -{ 1 }-> 0 :|: z = 0 33.62/9.56 double(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 33.62/9.56 double(z) -{ 1 }-> 1 + (1 + double(x)) :|: x >= 0, z = 1 + x 33.62/9.56 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 33.62/9.56 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 33.62/9.56 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 33.62/9.56 plus(z, z') -{ 1 }-> y :|: y >= 0, z = 0, z' = y 33.62/9.56 plus(z, z') -{ 1 }-> plus(x, 1 + y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 33.62/9.56 plus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 33.62/9.56 plus(z, z') -{ 1 }-> 1 + plus(x, y) :|: x >= 0, y >= 0, z = 1 + x, z' = y 33.62/9.56 plus(z, z') -{ 1 }-> 1 + plus(minus(x, y), double(y)) :|: x >= 0, y >= 0, z = 1 + x, z' = y 33.62/9.56 33.62/9.56 Only complete derivations are relevant for the runtime complexity. 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (9) CompleteCoflocoProof (FINISHED) 33.62/9.56 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 33.62/9.56 33.62/9.56 eq(start(V1, V),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 33.62/9.56 eq(start(V1, V),0,[double(V1, Out)],[V1 >= 0]). 33.62/9.56 eq(start(V1, V),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]). 33.62/9.56 eq(minus(V1, V, Out),1,[],[Out = V2,V2 >= 0,V1 = V2,V = 0]). 33.62/9.56 eq(minus(V1, V, Out),1,[minus(V3, V4, Ret)],[Out = Ret,V = 1 + V4,V3 >= 0,V4 >= 0,V1 = 1 + V3]). 33.62/9.56 eq(double(V1, Out),1,[],[Out = 0,V1 = 0]). 33.62/9.56 eq(double(V1, Out),1,[double(V5, Ret11)],[Out = 2 + Ret11,V5 >= 0,V1 = 1 + V5]). 33.62/9.56 eq(plus(V1, V, Out),1,[],[Out = V6,V6 >= 0,V1 = 0,V = V6]). 33.62/9.56 eq(plus(V1, V, Out),1,[plus(V7, V8, Ret1)],[Out = 1 + Ret1,V7 >= 0,V8 >= 0,V1 = 1 + V7,V = V8]). 33.62/9.56 eq(plus(V1, V, Out),1,[plus(V9, 1 + V10, Ret2)],[Out = Ret2,V9 >= 0,V10 >= 0,V1 = 1 + V9,V = V10]). 33.62/9.56 eq(plus(V1, V, Out),1,[minus(V12, V11, Ret10),double(V11, Ret111),plus(Ret10, Ret111, Ret12)],[Out = 1 + Ret12,V12 >= 0,V11 >= 0,V1 = 1 + V12,V = V11]). 33.62/9.56 eq(minus(V1, V, Out),0,[],[Out = 0,V14 >= 0,V13 >= 0,V1 = V14,V = V13]). 33.62/9.56 eq(double(V1, Out),0,[],[Out = 0,V15 >= 0,V1 = V15]). 33.62/9.56 eq(plus(V1, V, Out),0,[],[Out = 0,V17 >= 0,V16 >= 0,V1 = V17,V = V16]). 33.62/9.56 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 33.62/9.56 input_output_vars(double(V1,Out),[V1],[Out]). 33.62/9.56 input_output_vars(plus(V1,V,Out),[V1,V],[Out]). 33.62/9.56 33.62/9.56 33.62/9.56 CoFloCo proof output: 33.62/9.56 Preprocessing Cost Relations 33.62/9.56 ===================================== 33.62/9.56 33.62/9.56 #### Computed strongly connected components 33.62/9.56 0. recursive : [double/2] 33.62/9.56 1. recursive : [minus/3] 33.62/9.56 2. recursive : [plus/3] 33.62/9.56 3. non_recursive : [start/2] 33.62/9.56 33.62/9.56 #### Obtained direct recursion through partial evaluation 33.62/9.56 0. SCC is partially evaluated into double/2 33.62/9.56 1. SCC is partially evaluated into minus/3 33.62/9.56 2. SCC is partially evaluated into plus/3 33.62/9.56 3. SCC is partially evaluated into start/2 33.62/9.56 33.62/9.56 Control-Flow Refinement of Cost Relations 33.62/9.56 ===================================== 33.62/9.56 33.62/9.56 ### Specialization of cost equations double/2 33.62/9.56 * CE 7 is refined into CE [15] 33.62/9.56 * CE 9 is refined into CE [16] 33.62/9.56 * CE 8 is refined into CE [17] 33.62/9.56 33.62/9.56 33.62/9.56 ### Cost equations --> "Loop" of double/2 33.62/9.56 * CEs [17] --> Loop 11 33.62/9.56 * CEs [15,16] --> Loop 12 33.62/9.56 33.62/9.56 ### Ranking functions of CR double(V1,Out) 33.62/9.56 * RF of phase [11]: [V1] 33.62/9.56 33.62/9.56 #### Partial ranking functions of CR double(V1,Out) 33.62/9.56 * Partial RF of phase [11]: 33.62/9.56 - RF of loop [11:1]: 33.62/9.56 V1 33.62/9.56 33.62/9.56 33.62/9.56 ### Specialization of cost equations minus/3 33.62/9.56 * CE 6 is refined into CE [18] 33.62/9.56 * CE 4 is refined into CE [19] 33.62/9.56 * CE 5 is refined into CE [20] 33.62/9.56 33.62/9.56 33.62/9.56 ### Cost equations --> "Loop" of minus/3 33.62/9.56 * CEs [20] --> Loop 13 33.62/9.56 * CEs [18] --> Loop 14 33.62/9.56 * CEs [19] --> Loop 15 33.62/9.56 33.62/9.56 ### Ranking functions of CR minus(V1,V,Out) 33.62/9.56 * RF of phase [13]: [V,V1] 33.62/9.56 33.62/9.56 #### Partial ranking functions of CR minus(V1,V,Out) 33.62/9.56 * Partial RF of phase [13]: 33.62/9.56 - RF of loop [13:1]: 33.62/9.56 V 33.62/9.56 V1 33.62/9.56 33.62/9.56 33.62/9.56 ### Specialization of cost equations plus/3 33.62/9.56 * CE 14 is refined into CE [21] 33.62/9.56 * CE 10 is refined into CE [22] 33.62/9.56 * CE 11 is refined into CE [23] 33.62/9.56 * CE 13 is refined into CE [24,25,26,27,28] 33.62/9.56 * CE 12 is refined into CE [29] 33.62/9.56 33.62/9.56 33.62/9.56 ### Cost equations --> "Loop" of plus/3 33.62/9.56 * CEs [28] --> Loop 16 33.62/9.56 * CEs [29] --> Loop 17 33.62/9.56 * CEs [27] --> Loop 18 33.62/9.56 * CEs [26] --> Loop 19 33.62/9.56 * CEs [25] --> Loop 20 33.62/9.56 * CEs [23,24] --> Loop 21 33.62/9.56 * CEs [21] --> Loop 22 33.62/9.56 * CEs [22] --> Loop 23 33.62/9.56 33.62/9.56 ### Ranking functions of CR plus(V1,V,Out) 33.62/9.56 * RF of phase [16,17,18,21]: [V1,2*V1-1] 33.62/9.56 33.62/9.56 #### Partial ranking functions of CR plus(V1,V,Out) 33.62/9.56 * Partial RF of phase [16,17,18,21]: 33.62/9.56 - RF of loop [16:1]: 33.62/9.56 V1+V-2 33.62/9.56 V1/3-V/3 33.62/9.56 - RF of loop [16:1,18:1]: 33.62/9.56 V1/2-1/2 33.62/9.56 - RF of loop [17:1,21:1]: 33.62/9.56 V1 33.62/9.56 - RF of loop [18:1]: 33.62/9.56 V depends on loops [16:1,17:1] 33.62/9.56 V1-V 33.62/9.56 33.62/9.56 33.62/9.56 ### Specialization of cost equations start/2 33.62/9.56 * CE 1 is refined into CE [30,31,32] 33.62/9.56 * CE 2 is refined into CE [33,34] 33.62/9.56 * CE 3 is refined into CE [35,36,37,38,39,40] 33.62/9.56 33.62/9.56 33.62/9.56 ### Cost equations --> "Loop" of start/2 33.62/9.56 * CEs [30] --> Loop 24 33.62/9.56 * CEs [31,32,33,34,35,36,37,38,39,40] --> Loop 25 33.62/9.56 33.62/9.56 ### Ranking functions of CR start(V1,V) 33.62/9.56 33.62/9.56 #### Partial ranking functions of CR start(V1,V) 33.62/9.56 33.62/9.56 33.62/9.56 Computing Bounds 33.62/9.56 ===================================== 33.62/9.56 33.62/9.56 #### Cost of chains of double(V1,Out): 33.62/9.56 * Chain [[11],12]: 1*it(11)+1 33.62/9.56 Such that:it(11) =< Out/2 33.62/9.56 33.62/9.56 with precondition: [Out>=2,2*V1>=Out] 33.62/9.56 33.62/9.56 * Chain [12]: 1 33.62/9.56 with precondition: [Out=0,V1>=0] 33.62/9.56 33.62/9.56 33.62/9.56 #### Cost of chains of minus(V1,V,Out): 33.62/9.56 * Chain [[13],15]: 1*it(13)+1 33.62/9.56 Such that:it(13) =< V 33.62/9.56 33.62/9.56 with precondition: [V1=Out+V,V>=1,V1>=V] 33.62/9.56 33.62/9.56 * Chain [[13],14]: 1*it(13)+0 33.62/9.56 Such that:it(13) =< V 33.62/9.56 33.62/9.56 with precondition: [Out=0,V1>=1,V>=1] 33.62/9.56 33.62/9.56 * Chain [15]: 1 33.62/9.56 with precondition: [V=0,V1=Out,V1>=0] 33.62/9.56 33.62/9.56 * Chain [14]: 0 33.62/9.56 with precondition: [Out=0,V1>=0,V>=0] 33.62/9.56 33.62/9.56 33.62/9.56 #### Cost of chains of plus(V1,V,Out): 33.62/9.56 * Chain [[16,17,18,21],23]: 3*it(16)+4*it(17)+3*it(18)+2*s(8)+1*s(10)+1 33.62/9.56 Such that:it(18) =< V1-V 33.62/9.56 aux(15) =< V1+V 33.62/9.56 it(16) =< V1/3-V/3 33.62/9.56 aux(22) =< V1 33.62/9.56 aux(23) =< 2*V1 33.62/9.56 aux(24) =< V1/2 33.62/9.56 aux(25) =< V 33.62/9.56 aux(26) =< 2*V 33.62/9.56 it(16) =< aux(23) 33.62/9.56 it(16) =< aux(22) 33.62/9.56 it(17) =< aux(22) 33.62/9.56 it(18) =< aux(22) 33.62/9.56 s(8) =< aux(22) 33.62/9.56 it(18) =< aux(23) 33.62/9.56 it(17) =< aux(23) 33.62/9.56 it(16) =< aux(15) 33.62/9.56 it(18) =< aux(15) 33.62/9.56 it(16) =< aux(24) 33.62/9.56 it(18) =< aux(24) 33.62/9.56 aux(6) =< aux(22)*2 33.62/9.56 it(18) =< it(17)+aux(22)+aux(25) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(26) 33.62/9.56 s(10) =< it(18)*aux(15) 33.62/9.56 33.62/9.56 with precondition: [V>=0,Out>=1,Out+V1>=V+2,V+V1>=Out] 33.62/9.56 33.62/9.56 * Chain [[16,17,18,21],22]: 3*it(16)+4*it(17)+3*it(18)+2*s(8)+1*s(10)+0 33.62/9.56 Such that:it(18) =< V1-V 33.62/9.56 aux(15) =< V1+V 33.62/9.56 it(16) =< V1/3-V/3 33.62/9.56 aux(27) =< V1 33.62/9.56 aux(28) =< 2*V1 33.62/9.56 aux(29) =< V1/2 33.62/9.56 aux(30) =< V 33.62/9.56 aux(31) =< 2*V 33.62/9.56 it(16) =< aux(28) 33.62/9.56 it(16) =< aux(27) 33.62/9.56 it(17) =< aux(27) 33.62/9.56 it(18) =< aux(27) 33.62/9.56 s(8) =< aux(27) 33.62/9.56 it(18) =< aux(28) 33.62/9.56 it(17) =< aux(28) 33.62/9.56 it(16) =< aux(15) 33.62/9.56 it(18) =< aux(15) 33.62/9.56 it(16) =< aux(29) 33.62/9.56 it(18) =< aux(29) 33.62/9.56 aux(6) =< aux(27)*2 33.62/9.56 it(18) =< it(17)+aux(27)+aux(30) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(31) 33.62/9.56 s(10) =< it(18)*aux(15) 33.62/9.56 33.62/9.56 with precondition: [V1>=1,V>=0,Out>=0,V1>=Out] 33.62/9.56 33.62/9.56 * Chain [[16,17,18,21],20,23]: 3*it(16)+1*it(17)+3*it(18)+3*it(21)+2*s(8)+1*s(10)+1*s(11)+3 33.62/9.56 Such that:it(18) =< V1-V 33.62/9.56 it(16) =< V1/3-V/3 33.62/9.56 aux(32) =< V1 33.62/9.56 aux(33) =< V1+V 33.62/9.56 aux(34) =< 2*V1 33.62/9.56 aux(35) =< V1/2 33.62/9.56 aux(36) =< V 33.62/9.56 aux(37) =< 2*V 33.62/9.56 s(11) =< aux(33) 33.62/9.56 it(16) =< aux(34) 33.62/9.56 it(16) =< aux(32) 33.62/9.56 it(17) =< aux(32) 33.62/9.56 it(18) =< aux(32) 33.62/9.56 it(21) =< aux(32) 33.62/9.56 s(8) =< aux(32) 33.62/9.56 it(18) =< aux(34) 33.62/9.56 it(21) =< aux(34) 33.62/9.56 it(16) =< aux(33) 33.62/9.56 it(18) =< aux(33) 33.62/9.56 it(21) =< aux(33) 33.62/9.56 it(17) =< aux(34) 33.62/9.56 it(16) =< aux(35) 33.62/9.56 it(18) =< aux(35) 33.62/9.56 aux(6) =< aux(32)*2 33.62/9.56 it(18) =< it(17)+aux(32)+aux(36) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(37) 33.62/9.56 s(10) =< it(18)*aux(33) 33.62/9.56 33.62/9.56 with precondition: [V1>=2,V>=0,Out>=1,V1>=Out] 33.62/9.56 33.62/9.56 * Chain [[16,17,18,21],20,22]: 3*it(16)+1*it(17)+3*it(18)+3*it(21)+2*s(8)+1*s(10)+1*s(11)+2 33.62/9.56 Such that:it(18) =< V1-V 33.62/9.56 it(16) =< V1/3-V/3 33.62/9.56 aux(38) =< V1 33.62/9.56 aux(39) =< V1+V 33.62/9.56 aux(40) =< 2*V1 33.62/9.56 aux(41) =< V1/2 33.62/9.56 aux(42) =< V 33.62/9.56 aux(43) =< 2*V 33.62/9.56 s(11) =< aux(39) 33.62/9.56 it(16) =< aux(40) 33.62/9.56 it(16) =< aux(38) 33.62/9.56 it(17) =< aux(38) 33.62/9.56 it(18) =< aux(38) 33.62/9.56 it(21) =< aux(38) 33.62/9.56 s(8) =< aux(38) 33.62/9.56 it(18) =< aux(40) 33.62/9.56 it(21) =< aux(40) 33.62/9.56 it(16) =< aux(39) 33.62/9.56 it(18) =< aux(39) 33.62/9.56 it(21) =< aux(39) 33.62/9.56 it(17) =< aux(40) 33.62/9.56 it(16) =< aux(41) 33.62/9.56 it(18) =< aux(41) 33.62/9.56 aux(6) =< aux(38)*2 33.62/9.56 it(18) =< it(17)+aux(38)+aux(42) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(43) 33.62/9.56 s(10) =< it(18)*aux(39) 33.62/9.56 33.62/9.56 with precondition: [V1>=2,V>=0,Out>=1,V1>=Out] 33.62/9.56 33.62/9.56 * Chain [[16,17,18,21],19,23]: 3*it(16)+4*it(17)+3*it(18)+2*s(8)+1*s(10)+2*s(12)+3 33.62/9.56 Such that:it(18) =< V1-V 33.62/9.56 it(16) =< V1/3-V/3 33.62/9.56 aux(2) =< V 33.62/9.56 aux(7) =< 2*V 33.62/9.56 aux(44) =< V1 33.62/9.56 aux(45) =< V1+V 33.62/9.56 aux(46) =< 2*V1 33.62/9.56 aux(47) =< V1/2 33.62/9.56 s(12) =< aux(45) 33.62/9.56 it(16) =< aux(46) 33.62/9.56 it(16) =< aux(44) 33.62/9.56 it(17) =< aux(44) 33.62/9.56 it(18) =< aux(44) 33.62/9.56 s(8) =< aux(44) 33.62/9.56 it(18) =< aux(46) 33.62/9.56 it(17) =< aux(46) 33.62/9.56 it(16) =< aux(45) 33.62/9.56 it(18) =< aux(45) 33.62/9.56 it(16) =< aux(47) 33.62/9.56 it(18) =< aux(47) 33.62/9.56 aux(6) =< aux(44)*2 33.62/9.56 it(18) =< it(17)+aux(44)+aux(2) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(46) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(7) 33.62/9.56 it(18) =< it(17)+aux(44)+aux(44) 33.62/9.56 s(10) =< it(18)*aux(45) 33.62/9.56 33.62/9.56 with precondition: [V1>=2,V>=0,Out>=3,2*V+2*V1>=Out+1] 33.62/9.56 33.62/9.56 * Chain [[16,17,18,21],19,22]: 3*it(16)+1*it(17)+3*it(18)+3*it(21)+2*s(8)+1*s(10)+2*s(12)+2 33.62/9.56 Such that:it(18) =< V1-V 33.62/9.56 aux(4) =< V1-Out 33.62/9.56 aux(9) =< 2*V1-2*Out 33.62/9.56 it(16) =< V1/3-V/3 33.62/9.56 aux(2) =< V 33.62/9.56 aux(7) =< 2*V 33.62/9.56 aux(49) =< V1 33.62/9.56 aux(50) =< V1+V 33.62/9.56 aux(51) =< 2*V1 33.62/9.56 aux(52) =< V1/2 33.62/9.56 it(16) =< aux(51) 33.62/9.56 s(12) =< aux(50) 33.62/9.56 it(16) =< aux(49) 33.62/9.56 it(17) =< aux(49) 33.62/9.56 it(18) =< aux(49) 33.62/9.56 it(21) =< aux(49) 33.62/9.56 s(8) =< aux(49) 33.62/9.56 it(18) =< aux(51) 33.62/9.56 it(21) =< aux(51) 33.62/9.56 it(16) =< aux(50) 33.62/9.56 it(18) =< aux(50) 33.62/9.56 it(21) =< aux(50) 33.62/9.56 it(17) =< aux(51) 33.62/9.56 it(16) =< aux(52) 33.62/9.56 it(18) =< aux(52) 33.62/9.56 aux(6) =< aux(49)*2 33.62/9.56 it(18) =< it(17)+aux(49)+aux(2) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(9) 33.62/9.56 s(10) =< it(17)*2+aux(6)+aux(7) 33.62/9.56 it(18) =< it(17)+aux(49)+aux(4) 33.62/9.56 s(10) =< it(18)*aux(50) 33.62/9.56 33.62/9.56 with precondition: [V1>=2,V>=0,Out>=1,V1>=Out,V+V1>=Out+1] 33.62/9.56 33.62/9.56 * Chain [23]: 1 33.62/9.56 with precondition: [V1=0,V=Out,V>=0] 33.62/9.56 33.62/9.56 * Chain [22]: 0 33.62/9.56 with precondition: [Out=0,V1>=0,V>=0] 33.62/9.56 33.62/9.56 * Chain [20,23]: 1*s(11)+3 33.62/9.56 Such that:s(11) =< V 33.62/9.56 33.62/9.56 with precondition: [Out=1,V1>=1,V>=0] 33.62/9.56 33.62/9.56 * Chain [20,22]: 1*s(11)+2 33.62/9.56 Such that:s(11) =< V 33.62/9.56 33.62/9.56 with precondition: [Out=1,V1>=1,V>=0] 33.62/9.56 33.62/9.56 * Chain [19,23]: 1*s(12)+1*s(13)+3 33.62/9.56 Such that:s(12) =< V 33.62/9.56 s(13) =< Out/2 33.62/9.56 33.62/9.56 with precondition: [V1>=1,Out>=3,2*V+1>=Out] 33.62/9.56 33.62/9.56 * Chain [19,22]: 2*s(12)+2 33.62/9.56 Such that:aux(48) =< V 33.62/9.56 s(12) =< aux(48) 33.62/9.56 33.62/9.56 with precondition: [Out=1,V1>=1,V>=1] 33.62/9.56 33.62/9.56 33.62/9.56 #### Cost of chains of start(V1,V): 33.62/9.56 * Chain [25]: 7*s(74)+13*s(76)+6*s(87)+12*s(88)+18*s(89)+6*s(91)+15*s(92)+9*s(93)+2*s(96)+4*s(97)+1*s(99)+3 33.62/9.56 Such that:s(99) =< V+1/2 33.62/9.56 aux(63) =< V1 33.62/9.56 aux(64) =< V1-V 33.62/9.56 aux(65) =< V1+V 33.62/9.56 aux(66) =< 2*V1 33.62/9.56 aux(67) =< V1/2 33.62/9.56 aux(68) =< V1/3-V/3 33.62/9.56 aux(69) =< V 33.62/9.56 aux(70) =< 2*V 33.62/9.56 s(76) =< aux(63) 33.62/9.56 s(87) =< aux(64) 33.62/9.56 s(88) =< aux(64) 33.62/9.56 s(89) =< aux(68) 33.62/9.56 s(74) =< aux(69) 33.62/9.56 s(91) =< aux(65) 33.62/9.56 s(89) =< aux(66) 33.62/9.56 s(89) =< aux(63) 33.62/9.56 s(92) =< aux(63) 33.62/9.56 s(87) =< aux(63) 33.62/9.56 s(87) =< aux(66) 33.62/9.56 s(92) =< aux(66) 33.62/9.56 s(89) =< aux(65) 33.62/9.56 s(87) =< aux(65) 33.62/9.56 s(89) =< aux(67) 33.62/9.56 s(87) =< aux(67) 33.62/9.56 s(95) =< aux(63)*2 33.62/9.56 s(87) =< s(92)+aux(63)+aux(69) 33.62/9.56 s(96) =< s(92)*2+s(95)+aux(66) 33.62/9.56 s(96) =< s(92)*2+s(95)+aux(70) 33.62/9.56 s(87) =< s(92)+aux(63)+aux(63) 33.62/9.56 s(96) =< s(87)*aux(65) 33.62/9.56 s(88) =< aux(63) 33.62/9.56 s(88) =< aux(66) 33.62/9.56 s(88) =< aux(65) 33.62/9.56 s(88) =< aux(67) 33.62/9.56 s(88) =< s(92)+aux(63)+aux(69) 33.62/9.56 s(97) =< s(92)*2+s(95)+aux(70) 33.62/9.56 s(97) =< s(88)*aux(65) 33.62/9.56 s(93) =< aux(63) 33.62/9.56 s(93) =< aux(66) 33.62/9.56 s(93) =< aux(65) 33.62/9.56 33.62/9.56 with precondition: [V1>=0] 33.62/9.56 33.62/9.56 * Chain [24]: 1 33.62/9.56 with precondition: [V=0,V1>=0] 33.62/9.56 33.62/9.56 33.62/9.56 Closed-form bounds of start(V1,V): 33.62/9.56 ------------------------------------- 33.62/9.56 * Chain [25] with precondition: [V1>=0] 33.62/9.56 - Upper bound: 61*V1+3+nat(V)*7+4*V1+nat(2*V)*4+nat(V1+V)*6+nat(V+1/2)+nat(V1-V)*18+nat(V1/3-V/3)*18 33.62/9.56 - Complexity: n 33.62/9.56 * Chain [24] with precondition: [V=0,V1>=0] 33.62/9.56 - Upper bound: 1 33.62/9.56 - Complexity: constant 33.62/9.56 33.62/9.56 ### Maximum cost of start(V1,V): 61*V1+2+nat(V)*7+4*V1+nat(2*V)*4+nat(V1+V)*6+nat(V+1/2)+nat(V1-V)*18+nat(V1/3-V/3)*18+1 33.62/9.56 Asymptotic class: n 33.62/9.56 * Total analysis performed in 622 ms. 33.62/9.56 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (10) 33.62/9.56 BOUNDS(1, n^1) 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 33.62/9.56 Transformed a relative TRS into a decreasing-loop problem. 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (12) 33.62/9.56 Obligation: 33.62/9.56 Analyzing the following TRS for decreasing loops: 33.62/9.56 33.62/9.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.62/9.56 33.62/9.56 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) 33.62/9.56 double(0) -> 0 33.62/9.56 double(s(x)) -> s(s(double(x))) 33.62/9.56 plus(0, y) -> y 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) 33.62/9.56 33.62/9.56 S is empty. 33.62/9.56 Rewrite Strategy: INNERMOST 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (13) DecreasingLoopProof (LOWER BOUND(ID)) 33.62/9.56 The following loop(s) give(s) rise to the lower bound Omega(n^1): 33.62/9.56 33.62/9.56 The rewrite sequence 33.62/9.56 33.62/9.56 minus(s(x), s(y)) ->^+ minus(x, y) 33.62/9.56 33.62/9.56 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 33.62/9.56 33.62/9.56 The pumping substitution is [x / s(x), y / s(y)]. 33.62/9.56 33.62/9.56 The result substitution is [ ]. 33.62/9.56 33.62/9.56 33.62/9.56 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (14) 33.62/9.56 Complex Obligation (BEST) 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (15) 33.62/9.56 Obligation: 33.62/9.56 Proved the lower bound n^1 for the following obligation: 33.62/9.56 33.62/9.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.62/9.56 33.62/9.56 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) 33.62/9.56 double(0) -> 0 33.62/9.56 double(s(x)) -> s(s(double(x))) 33.62/9.56 plus(0, y) -> y 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) 33.62/9.56 33.62/9.56 S is empty. 33.62/9.56 Rewrite Strategy: INNERMOST 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (16) LowerBoundPropagationProof (FINISHED) 33.62/9.56 Propagated lower bound. 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (17) 33.62/9.56 BOUNDS(n^1, INF) 33.62/9.56 33.62/9.56 ---------------------------------------- 33.62/9.56 33.62/9.56 (18) 33.62/9.56 Obligation: 33.62/9.56 Analyzing the following TRS for decreasing loops: 33.62/9.56 33.62/9.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 33.62/9.56 33.62/9.56 33.62/9.56 The TRS R consists of the following rules: 33.62/9.56 33.62/9.56 minus(x, 0) -> x 33.62/9.56 minus(s(x), s(y)) -> minus(x, y) 33.62/9.56 double(0) -> 0 33.62/9.56 double(s(x)) -> s(s(double(x))) 33.62/9.56 plus(0, y) -> y 33.62/9.56 plus(s(x), y) -> s(plus(x, y)) 33.62/9.56 plus(s(x), y) -> plus(x, s(y)) 33.62/9.56 plus(s(x), y) -> s(plus(minus(x, y), double(y))) 33.62/9.56 33.62/9.56 S is empty. 33.62/9.56 Rewrite Strategy: INNERMOST 33.89/9.62 EOF