20.58/7.66 WORST_CASE(Omega(n^2), O(n^2)) 20.58/7.67 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 20.58/7.67 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 20.58/7.67 20.58/7.67 20.58/7.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 20.58/7.67 20.58/7.67 (0) CpxTRS 20.58/7.67 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 20.58/7.67 (2) CpxTRS 20.58/7.67 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 20.58/7.67 (4) CpxWeightedTrs 20.58/7.67 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 20.58/7.67 (6) CpxTypedWeightedTrs 20.58/7.67 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 20.58/7.67 (8) CpxTypedWeightedCompleteTrs 20.58/7.67 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 20.58/7.67 (10) CpxRNTS 20.58/7.67 (11) CompleteCoflocoProof [FINISHED, 232 ms] 20.58/7.67 (12) BOUNDS(1, n^2) 20.58/7.67 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 20.58/7.67 (14) CpxTRS 20.58/7.67 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 20.58/7.67 (16) typed CpxTrs 20.58/7.67 (17) OrderProof [LOWER BOUND(ID), 0 ms] 20.58/7.67 (18) typed CpxTrs 20.58/7.67 (19) RewriteLemmaProof [LOWER BOUND(ID), 311 ms] 20.58/7.67 (20) BEST 20.58/7.67 (21) proven lower bound 20.58/7.67 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 20.58/7.67 (23) BOUNDS(n^1, INF) 20.58/7.67 (24) typed CpxTrs 20.58/7.67 (25) RewriteLemmaProof [LOWER BOUND(ID), 30 ms] 20.58/7.67 (26) proven lower bound 20.58/7.67 (27) LowerBoundPropagationProof [FINISHED, 0 ms] 20.58/7.67 (28) BOUNDS(n^2, INF) 20.58/7.67 20.58/7.67 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (0) 20.58/7.67 Obligation: 20.58/7.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 20.58/7.67 20.58/7.67 20.58/7.67 The TRS R consists of the following rules: 20.58/7.67 20.58/7.67 rev(nil) -> nil 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.67 car(.(x, y)) -> x 20.58/7.67 cdr(.(x, y)) -> y 20.58/7.67 null(nil) -> true 20.58/7.67 null(.(x, y)) -> false 20.58/7.67 ++(nil, y) -> y 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.67 20.58/7.67 S is empty. 20.58/7.67 Rewrite Strategy: FULL 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 20.58/7.67 Converted rc-obligation to irc-obligation. 20.58/7.67 20.58/7.67 As the TRS is a non-duplicating overlay system, we have rc = irc. 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (2) 20.58/7.67 Obligation: 20.58/7.67 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). 20.58/7.67 20.58/7.67 20.58/7.67 The TRS R consists of the following rules: 20.58/7.67 20.58/7.67 rev(nil) -> nil 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.67 car(.(x, y)) -> x 20.58/7.67 cdr(.(x, y)) -> y 20.58/7.67 null(nil) -> true 20.58/7.67 null(.(x, y)) -> false 20.58/7.67 ++(nil, y) -> y 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.67 20.58/7.67 S is empty. 20.58/7.67 Rewrite Strategy: INNERMOST 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 20.58/7.67 Transformed relative TRS to weighted TRS 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (4) 20.58/7.67 Obligation: 20.58/7.67 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 20.58/7.67 20.58/7.67 20.58/7.67 The TRS R consists of the following rules: 20.58/7.67 20.58/7.67 rev(nil) -> nil [1] 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1] 20.58/7.67 car(.(x, y)) -> x [1] 20.58/7.67 cdr(.(x, y)) -> y [1] 20.58/7.67 null(nil) -> true [1] 20.58/7.67 null(.(x, y)) -> false [1] 20.58/7.67 ++(nil, y) -> y [1] 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) [1] 20.58/7.67 20.58/7.67 Rewrite Strategy: INNERMOST 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 20.58/7.67 Infered types. 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (6) 20.58/7.67 Obligation: 20.58/7.67 Runtime Complexity Weighted TRS with Types. 20.58/7.67 The TRS R consists of the following rules: 20.58/7.67 20.58/7.67 rev(nil) -> nil [1] 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1] 20.58/7.67 car(.(x, y)) -> x [1] 20.58/7.67 cdr(.(x, y)) -> y [1] 20.58/7.67 null(nil) -> true [1] 20.58/7.67 null(.(x, y)) -> false [1] 20.58/7.67 ++(nil, y) -> y [1] 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) [1] 20.58/7.67 20.58/7.67 The TRS has the following type information: 20.58/7.67 rev :: nil:. -> nil:. 20.58/7.67 nil :: nil:. 20.58/7.67 . :: car -> nil:. -> nil:. 20.58/7.67 ++ :: nil:. -> nil:. -> nil:. 20.58/7.67 car :: nil:. -> car 20.58/7.67 cdr :: nil:. -> nil:. 20.58/7.67 null :: nil:. -> true:false 20.58/7.67 true :: true:false 20.58/7.67 false :: true:false 20.58/7.67 20.58/7.67 Rewrite Strategy: INNERMOST 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (7) CompletionProof (UPPER BOUND(ID)) 20.58/7.67 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 20.58/7.67 20.58/7.67 car(v0) -> null_car [0] 20.58/7.67 cdr(v0) -> null_cdr [0] 20.58/7.67 rev(v0) -> null_rev [0] 20.58/7.67 null(v0) -> null_null [0] 20.58/7.67 ++(v0, v1) -> null_++ [0] 20.58/7.67 20.58/7.67 And the following fresh constants: null_car, null_cdr, null_rev, null_null, null_++ 20.58/7.67 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (8) 20.58/7.67 Obligation: 20.58/7.67 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 20.58/7.67 20.58/7.67 Runtime Complexity Weighted TRS with Types. 20.58/7.67 The TRS R consists of the following rules: 20.58/7.67 20.58/7.67 rev(nil) -> nil [1] 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) [1] 20.58/7.67 car(.(x, y)) -> x [1] 20.58/7.67 cdr(.(x, y)) -> y [1] 20.58/7.67 null(nil) -> true [1] 20.58/7.67 null(.(x, y)) -> false [1] 20.58/7.67 ++(nil, y) -> y [1] 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) [1] 20.58/7.67 car(v0) -> null_car [0] 20.58/7.67 cdr(v0) -> null_cdr [0] 20.58/7.67 rev(v0) -> null_rev [0] 20.58/7.67 null(v0) -> null_null [0] 20.58/7.67 ++(v0, v1) -> null_++ [0] 20.58/7.67 20.58/7.67 The TRS has the following type information: 20.58/7.67 rev :: nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++ 20.58/7.67 nil :: nil:.:null_cdr:null_rev:null_++ 20.58/7.67 . :: null_car -> nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++ 20.58/7.67 ++ :: nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++ 20.58/7.67 car :: nil:.:null_cdr:null_rev:null_++ -> null_car 20.58/7.67 cdr :: nil:.:null_cdr:null_rev:null_++ -> nil:.:null_cdr:null_rev:null_++ 20.58/7.67 null :: nil:.:null_cdr:null_rev:null_++ -> true:false:null_null 20.58/7.67 true :: true:false:null_null 20.58/7.67 false :: true:false:null_null 20.58/7.67 null_car :: null_car 20.58/7.67 null_cdr :: nil:.:null_cdr:null_rev:null_++ 20.58/7.67 null_rev :: nil:.:null_cdr:null_rev:null_++ 20.58/7.67 null_null :: true:false:null_null 20.58/7.67 null_++ :: nil:.:null_cdr:null_rev:null_++ 20.58/7.67 20.58/7.67 Rewrite Strategy: INNERMOST 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 20.58/7.67 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 20.58/7.67 The constant constructors are abstracted as follows: 20.58/7.67 20.58/7.67 nil => 0 20.58/7.67 true => 2 20.58/7.67 false => 1 20.58/7.67 null_car => 0 20.58/7.67 null_cdr => 0 20.58/7.67 null_rev => 0 20.58/7.67 null_null => 0 20.58/7.67 null_++ => 0 20.58/7.67 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (10) 20.58/7.67 Obligation: 20.58/7.67 Complexity RNTS consisting of the following rules: 20.58/7.67 20.58/7.67 ++(z', z'') -{ 1 }-> y :|: z'' = y, y >= 0, z' = 0 20.58/7.67 ++(z', z'') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z'' = v1, z' = v0 20.58/7.67 ++(z', z'') -{ 1 }-> 1 + x + ++(y, z) :|: z'' = z, z >= 0, z' = 1 + x + y, x >= 0, y >= 0 20.58/7.67 car(z') -{ 1 }-> x :|: z' = 1 + x + y, x >= 0, y >= 0 20.58/7.67 car(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 20.58/7.67 cdr(z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0 20.58/7.67 cdr(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 20.58/7.67 null(z') -{ 1 }-> 2 :|: z' = 0 20.58/7.67 null(z') -{ 1 }-> 1 :|: z' = 1 + x + y, x >= 0, y >= 0 20.58/7.67 null(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 20.58/7.67 rev(z') -{ 1 }-> 0 :|: z' = 0 20.58/7.67 rev(z') -{ 0 }-> 0 :|: v0 >= 0, z' = v0 20.58/7.67 rev(z') -{ 1 }-> ++(rev(y), 1 + x + 0) :|: z' = 1 + x + y, x >= 0, y >= 0 20.58/7.67 20.58/7.67 Only complete derivations are relevant for the runtime complexity. 20.58/7.67 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (11) CompleteCoflocoProof (FINISHED) 20.58/7.67 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 20.58/7.67 20.58/7.67 eq(start(V, V10),0,[rev(V, Out)],[V >= 0]). 20.58/7.67 eq(start(V, V10),0,[car(V, Out)],[V >= 0]). 20.58/7.67 eq(start(V, V10),0,[cdr(V, Out)],[V >= 0]). 20.58/7.67 eq(start(V, V10),0,[null(V, Out)],[V >= 0]). 20.58/7.67 eq(start(V, V10),0,[fun(V, V10, Out)],[V >= 0,V10 >= 0]). 20.58/7.67 eq(rev(V, Out),1,[],[Out = 0,V = 0]). 20.58/7.67 eq(rev(V, Out),1,[rev(V1, Ret0),fun(Ret0, 1 + V2 + 0, Ret)],[Out = Ret,V = 1 + V1 + V2,V2 >= 0,V1 >= 0]). 20.58/7.67 eq(car(V, Out),1,[],[Out = V3,V = 1 + V3 + V4,V3 >= 0,V4 >= 0]). 20.58/7.67 eq(cdr(V, Out),1,[],[Out = V5,V = 1 + V5 + V6,V6 >= 0,V5 >= 0]). 20.58/7.67 eq(null(V, Out),1,[],[Out = 2,V = 0]). 20.58/7.67 eq(null(V, Out),1,[],[Out = 1,V = 1 + V7 + V8,V7 >= 0,V8 >= 0]). 20.58/7.67 eq(fun(V, V10, Out),1,[],[Out = V9,V10 = V9,V9 >= 0,V = 0]). 20.58/7.67 eq(fun(V, V10, Out),1,[fun(V12, V13, Ret1)],[Out = 1 + Ret1 + V11,V10 = V13,V13 >= 0,V = 1 + V11 + V12,V11 >= 0,V12 >= 0]). 20.58/7.67 eq(car(V, Out),0,[],[Out = 0,V14 >= 0,V = V14]). 20.58/7.67 eq(cdr(V, Out),0,[],[Out = 0,V15 >= 0,V = V15]). 20.58/7.67 eq(rev(V, Out),0,[],[Out = 0,V16 >= 0,V = V16]). 20.58/7.67 eq(null(V, Out),0,[],[Out = 0,V17 >= 0,V = V17]). 20.58/7.67 eq(fun(V, V10, Out),0,[],[Out = 0,V18 >= 0,V19 >= 0,V10 = V19,V = V18]). 20.58/7.67 input_output_vars(rev(V,Out),[V],[Out]). 20.58/7.67 input_output_vars(car(V,Out),[V],[Out]). 20.58/7.67 input_output_vars(cdr(V,Out),[V],[Out]). 20.58/7.67 input_output_vars(null(V,Out),[V],[Out]). 20.58/7.67 input_output_vars(fun(V,V10,Out),[V,V10],[Out]). 20.58/7.67 20.58/7.67 20.58/7.67 CoFloCo proof output: 20.58/7.67 Preprocessing Cost Relations 20.58/7.67 ===================================== 20.58/7.67 20.58/7.67 #### Computed strongly connected components 20.58/7.67 0. non_recursive : [car/2] 20.58/7.67 1. non_recursive : [cdr/2] 20.58/7.67 2. recursive : [fun/3] 20.58/7.67 3. non_recursive : [null/2] 20.58/7.67 4. recursive [non_tail] : [rev/2] 20.58/7.67 5. non_recursive : [start/2] 20.58/7.67 20.58/7.67 #### Obtained direct recursion through partial evaluation 20.58/7.67 0. SCC is partially evaluated into car/2 20.58/7.67 1. SCC is partially evaluated into cdr/2 20.58/7.67 2. SCC is partially evaluated into fun/3 20.58/7.67 3. SCC is partially evaluated into null/2 20.58/7.67 4. SCC is partially evaluated into rev/2 20.58/7.67 5. SCC is partially evaluated into start/2 20.58/7.67 20.58/7.67 Control-Flow Refinement of Cost Relations 20.58/7.67 ===================================== 20.58/7.67 20.58/7.67 ### Specialization of cost equations car/2 20.58/7.67 * CE 9 is refined into CE [19] 20.58/7.67 * CE 10 is refined into CE [20] 20.58/7.67 20.58/7.67 20.58/7.67 ### Cost equations --> "Loop" of car/2 20.58/7.67 * CEs [19] --> Loop 14 20.58/7.67 * CEs [20] --> Loop 15 20.58/7.67 20.58/7.67 ### Ranking functions of CR car(V,Out) 20.58/7.67 20.58/7.67 #### Partial ranking functions of CR car(V,Out) 20.58/7.67 20.58/7.67 20.58/7.67 ### Specialization of cost equations cdr/2 20.58/7.67 * CE 11 is refined into CE [21] 20.58/7.67 * CE 12 is refined into CE [22] 20.58/7.67 20.58/7.67 20.58/7.67 ### Cost equations --> "Loop" of cdr/2 20.58/7.67 * CEs [21] --> Loop 16 20.58/7.67 * CEs [22] --> Loop 17 20.58/7.67 20.58/7.67 ### Ranking functions of CR cdr(V,Out) 20.58/7.67 20.58/7.67 #### Partial ranking functions of CR cdr(V,Out) 20.58/7.67 20.58/7.67 20.58/7.67 ### Specialization of cost equations fun/3 20.58/7.67 * CE 18 is refined into CE [23] 20.58/7.67 * CE 16 is refined into CE [24] 20.58/7.67 * CE 17 is refined into CE [25] 20.58/7.67 20.58/7.67 20.58/7.67 ### Cost equations --> "Loop" of fun/3 20.58/7.67 * CEs [25] --> Loop 18 20.58/7.67 * CEs [23] --> Loop 19 20.58/7.67 * CEs [24] --> Loop 20 20.58/7.67 20.58/7.67 ### Ranking functions of CR fun(V,V10,Out) 20.58/7.67 * RF of phase [18]: [V] 20.58/7.67 20.58/7.67 #### Partial ranking functions of CR fun(V,V10,Out) 20.58/7.67 * Partial RF of phase [18]: 20.58/7.67 - RF of loop [18:1]: 20.58/7.67 V 20.58/7.67 20.58/7.67 20.58/7.67 ### Specialization of cost equations null/2 20.58/7.67 * CE 14 is refined into CE [26] 20.58/7.67 * CE 15 is refined into CE [27] 20.58/7.67 * CE 13 is refined into CE [28] 20.58/7.67 20.58/7.67 20.58/7.67 ### Cost equations --> "Loop" of null/2 20.58/7.67 * CEs [26] --> Loop 21 20.58/7.67 * CEs [27] --> Loop 22 20.58/7.67 * CEs [28] --> Loop 23 20.58/7.67 20.58/7.67 ### Ranking functions of CR null(V,Out) 20.58/7.67 20.58/7.67 #### Partial ranking functions of CR null(V,Out) 20.58/7.67 20.58/7.67 20.58/7.67 ### Specialization of cost equations rev/2 20.58/7.67 * CE 6 is refined into CE [29] 20.58/7.67 * CE 8 is refined into CE [30] 20.58/7.67 * CE 7 is refined into CE [31,32,33,34] 20.58/7.67 20.58/7.67 20.58/7.67 ### Cost equations --> "Loop" of rev/2 20.58/7.67 * CEs [34] --> Loop 24 20.58/7.67 * CEs [33] --> Loop 25 20.58/7.67 * CEs [31] --> Loop 26 20.58/7.67 * CEs [32] --> Loop 27 20.58/7.67 * CEs [29,30] --> Loop 28 20.58/7.67 20.58/7.67 ### Ranking functions of CR rev(V,Out) 20.58/7.67 * RF of phase [24,25,26,27]: [V] 20.58/7.67 20.58/7.67 #### Partial ranking functions of CR rev(V,Out) 20.58/7.67 * Partial RF of phase [24,25,26,27]: 20.58/7.67 - RF of loop [24:1,25:1,26:1,27:1]: 20.58/7.67 V 20.58/7.67 20.58/7.67 20.58/7.67 ### Specialization of cost equations start/2 20.58/7.67 * CE 1 is refined into CE [35,36] 20.58/7.67 * CE 2 is refined into CE [37,38] 20.58/7.67 * CE 3 is refined into CE [39,40] 20.58/7.67 * CE 4 is refined into CE [41,42,43] 20.58/7.67 * CE 5 is refined into CE [44,45,46,47] 20.58/7.67 20.58/7.67 20.58/7.67 ### Cost equations --> "Loop" of start/2 20.58/7.67 * CEs [35,36,37,38,39,40,41,42,43,44,45,46,47] --> Loop 29 20.58/7.67 20.58/7.67 ### Ranking functions of CR start(V,V10) 20.58/7.67 20.58/7.67 #### Partial ranking functions of CR start(V,V10) 20.58/7.67 20.58/7.67 20.58/7.67 Computing Bounds 20.58/7.67 ===================================== 20.58/7.67 20.58/7.67 #### Cost of chains of car(V,Out): 20.58/7.67 * Chain [15]: 0 20.58/7.67 with precondition: [Out=0,V>=0] 20.58/7.67 20.58/7.67 * Chain [14]: 1 20.58/7.67 with precondition: [Out>=0,V>=Out+1] 20.58/7.67 20.58/7.67 20.58/7.67 #### Cost of chains of cdr(V,Out): 20.58/7.67 * Chain [17]: 0 20.58/7.67 with precondition: [Out=0,V>=0] 20.58/7.67 20.58/7.67 * Chain [16]: 1 20.58/7.67 with precondition: [Out>=0,V>=Out+1] 20.58/7.67 20.58/7.67 20.58/7.67 #### Cost of chains of fun(V,V10,Out): 20.58/7.67 * Chain [[18],20]: 1*it(18)+1 20.58/7.67 Such that:it(18) =< -V10+Out 20.58/7.67 20.58/7.67 with precondition: [V+V10=Out,V>=1,V10>=0] 20.58/7.67 20.58/7.67 * Chain [[18],19]: 1*it(18)+0 20.58/7.67 Such that:it(18) =< Out 20.58/7.67 20.58/7.67 with precondition: [V10>=0,Out>=1,V>=Out] 20.58/7.67 20.58/7.67 * Chain [20]: 1 20.58/7.67 with precondition: [V=0,V10=Out,V10>=0] 20.58/7.67 20.58/7.67 * Chain [19]: 0 20.58/7.67 with precondition: [Out=0,V>=0,V10>=0] 20.58/7.67 20.58/7.67 20.58/7.67 #### Cost of chains of null(V,Out): 20.58/7.67 * Chain [23]: 1 20.58/7.67 with precondition: [V=0,Out=2] 20.58/7.67 20.58/7.67 * Chain [22]: 0 20.58/7.67 with precondition: [Out=0,V>=0] 20.58/7.67 20.58/7.67 * Chain [21]: 1 20.58/7.67 with precondition: [Out=1,V>=1] 20.58/7.67 20.58/7.67 20.58/7.67 #### Cost of chains of rev(V,Out): 20.58/7.67 * Chain [[24,25,26,27],28]: 6*it(24)+1*s(5)+1*s(6)+1 20.58/7.67 Such that:aux(5) =< V 20.58/7.67 it(24) =< aux(5) 20.58/7.67 aux(2) =< aux(5) 20.58/7.67 s(5) =< it(24)*aux(5) 20.58/7.67 s(6) =< it(24)*aux(2) 20.58/7.67 20.58/7.67 with precondition: [V>=1,Out>=0,V>=Out] 20.58/7.67 20.58/7.67 * Chain [28]: 1 20.58/7.67 with precondition: [Out=0,V>=0] 20.58/7.67 20.58/7.67 20.58/7.67 #### Cost of chains of start(V,V10): 20.58/7.67 * Chain [29]: 8*s(8)+1*s(10)+1*s(11)+1 20.58/7.67 Such that:aux(6) =< V 20.58/7.67 s(8) =< aux(6) 20.58/7.67 s(9) =< aux(6) 20.58/7.67 s(10) =< s(8)*aux(6) 20.58/7.67 s(11) =< s(8)*s(9) 20.58/7.67 20.58/7.67 with precondition: [V>=0] 20.58/7.67 20.58/7.67 20.58/7.67 Closed-form bounds of start(V,V10): 20.58/7.67 ------------------------------------- 20.58/7.67 * Chain [29] with precondition: [V>=0] 20.58/7.67 - Upper bound: 8*V+1+2*V*V 20.58/7.67 - Complexity: n^2 20.58/7.67 20.58/7.67 ### Maximum cost of start(V,V10): 8*V+1+2*V*V 20.58/7.67 Asymptotic class: n^2 20.58/7.67 * Total analysis performed in 162 ms. 20.58/7.67 20.58/7.67 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (12) 20.58/7.67 BOUNDS(1, n^2) 20.58/7.67 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 20.58/7.67 Renamed function symbols to avoid clashes with predefined symbol. 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (14) 20.58/7.67 Obligation: 20.58/7.67 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 20.58/7.67 20.58/7.67 20.58/7.67 The TRS R consists of the following rules: 20.58/7.67 20.58/7.67 rev(nil) -> nil 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.67 car(.(x, y)) -> x 20.58/7.67 cdr(.(x, y)) -> y 20.58/7.67 null(nil) -> true 20.58/7.67 null(.(x, y)) -> false 20.58/7.67 ++(nil, y) -> y 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.67 20.58/7.67 S is empty. 20.58/7.67 Rewrite Strategy: FULL 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 20.58/7.67 Infered types. 20.58/7.67 ---------------------------------------- 20.58/7.67 20.58/7.67 (16) 20.58/7.67 Obligation: 20.58/7.67 TRS: 20.58/7.67 Rules: 20.58/7.67 rev(nil) -> nil 20.58/7.67 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.67 car(.(x, y)) -> x 20.58/7.67 cdr(.(x, y)) -> y 20.58/7.67 null(nil) -> true 20.58/7.67 null(.(x, y)) -> false 20.58/7.67 ++(nil, y) -> y 20.58/7.67 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.67 20.58/7.67 Types: 20.58/7.67 rev :: nil:. -> nil:. 20.58/7.67 nil :: nil:. 20.58/7.67 . :: car -> nil:. -> nil:. 20.58/7.67 ++ :: nil:. -> nil:. -> nil:. 20.58/7.67 car :: nil:. -> car 20.58/7.67 cdr :: nil:. -> nil:. 20.58/7.67 null :: nil:. -> true:false 20.58/7.67 true :: true:false 20.58/7.67 false :: true:false 20.58/7.67 hole_nil:.1_0 :: nil:. 20.58/7.67 hole_car2_0 :: car 20.58/7.67 hole_true:false3_0 :: true:false 20.58/7.68 gen_nil:.4_0 :: Nat -> nil:. 20.58/7.68 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (17) OrderProof (LOWER BOUND(ID)) 20.58/7.68 Heuristically decided to analyse the following defined symbols: 20.58/7.68 rev, ++ 20.58/7.68 20.58/7.68 They will be analysed ascendingly in the following order: 20.58/7.68 ++ < rev 20.58/7.68 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (18) 20.58/7.68 Obligation: 20.58/7.68 TRS: 20.58/7.68 Rules: 20.58/7.68 rev(nil) -> nil 20.58/7.68 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.68 car(.(x, y)) -> x 20.58/7.68 cdr(.(x, y)) -> y 20.58/7.68 null(nil) -> true 20.58/7.68 null(.(x, y)) -> false 20.58/7.68 ++(nil, y) -> y 20.58/7.68 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.68 20.58/7.68 Types: 20.58/7.68 rev :: nil:. -> nil:. 20.58/7.68 nil :: nil:. 20.58/7.68 . :: car -> nil:. -> nil:. 20.58/7.68 ++ :: nil:. -> nil:. -> nil:. 20.58/7.68 car :: nil:. -> car 20.58/7.68 cdr :: nil:. -> nil:. 20.58/7.68 null :: nil:. -> true:false 20.58/7.68 true :: true:false 20.58/7.68 false :: true:false 20.58/7.68 hole_nil:.1_0 :: nil:. 20.58/7.68 hole_car2_0 :: car 20.58/7.68 hole_true:false3_0 :: true:false 20.58/7.68 gen_nil:.4_0 :: Nat -> nil:. 20.58/7.68 20.58/7.68 20.58/7.68 Generator Equations: 20.58/7.68 gen_nil:.4_0(0) <=> nil 20.58/7.68 gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x)) 20.58/7.68 20.58/7.68 20.58/7.68 The following defined symbols remain to be analysed: 20.58/7.68 ++, rev 20.58/7.68 20.58/7.68 They will be analysed ascendingly in the following order: 20.58/7.68 ++ < rev 20.58/7.68 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (19) RewriteLemmaProof (LOWER BOUND(ID)) 20.58/7.68 Proved the following rewrite lemma: 20.58/7.68 ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 20.58/7.68 20.58/7.68 Induction Base: 20.58/7.68 ++(gen_nil:.4_0(0), gen_nil:.4_0(b)) ->_R^Omega(1) 20.58/7.68 gen_nil:.4_0(b) 20.58/7.68 20.58/7.68 Induction Step: 20.58/7.68 ++(gen_nil:.4_0(+(n6_0, 1)), gen_nil:.4_0(b)) ->_R^Omega(1) 20.58/7.68 .(hole_car2_0, ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b))) ->_IH 20.58/7.68 .(hole_car2_0, gen_nil:.4_0(+(b, c7_0))) 20.58/7.68 20.58/7.68 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (20) 20.58/7.68 Complex Obligation (BEST) 20.58/7.68 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (21) 20.58/7.68 Obligation: 20.58/7.68 Proved the lower bound n^1 for the following obligation: 20.58/7.68 20.58/7.68 TRS: 20.58/7.68 Rules: 20.58/7.68 rev(nil) -> nil 20.58/7.68 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.68 car(.(x, y)) -> x 20.58/7.68 cdr(.(x, y)) -> y 20.58/7.68 null(nil) -> true 20.58/7.68 null(.(x, y)) -> false 20.58/7.68 ++(nil, y) -> y 20.58/7.68 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.68 20.58/7.68 Types: 20.58/7.68 rev :: nil:. -> nil:. 20.58/7.68 nil :: nil:. 20.58/7.68 . :: car -> nil:. -> nil:. 20.58/7.68 ++ :: nil:. -> nil:. -> nil:. 20.58/7.68 car :: nil:. -> car 20.58/7.68 cdr :: nil:. -> nil:. 20.58/7.68 null :: nil:. -> true:false 20.58/7.68 true :: true:false 20.58/7.68 false :: true:false 20.58/7.68 hole_nil:.1_0 :: nil:. 20.58/7.68 hole_car2_0 :: car 20.58/7.68 hole_true:false3_0 :: true:false 20.58/7.68 gen_nil:.4_0 :: Nat -> nil:. 20.58/7.68 20.58/7.68 20.58/7.68 Generator Equations: 20.58/7.68 gen_nil:.4_0(0) <=> nil 20.58/7.68 gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x)) 20.58/7.68 20.58/7.68 20.58/7.68 The following defined symbols remain to be analysed: 20.58/7.68 ++, rev 20.58/7.68 20.58/7.68 They will be analysed ascendingly in the following order: 20.58/7.68 ++ < rev 20.58/7.68 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (22) LowerBoundPropagationProof (FINISHED) 20.58/7.68 Propagated lower bound. 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (23) 20.58/7.68 BOUNDS(n^1, INF) 20.58/7.68 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (24) 20.58/7.68 Obligation: 20.58/7.68 TRS: 20.58/7.68 Rules: 20.58/7.68 rev(nil) -> nil 20.58/7.68 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.68 car(.(x, y)) -> x 20.58/7.68 cdr(.(x, y)) -> y 20.58/7.68 null(nil) -> true 20.58/7.68 null(.(x, y)) -> false 20.58/7.68 ++(nil, y) -> y 20.58/7.68 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.68 20.58/7.68 Types: 20.58/7.68 rev :: nil:. -> nil:. 20.58/7.68 nil :: nil:. 20.58/7.68 . :: car -> nil:. -> nil:. 20.58/7.68 ++ :: nil:. -> nil:. -> nil:. 20.58/7.68 car :: nil:. -> car 20.58/7.68 cdr :: nil:. -> nil:. 20.58/7.68 null :: nil:. -> true:false 20.58/7.68 true :: true:false 20.58/7.68 false :: true:false 20.58/7.68 hole_nil:.1_0 :: nil:. 20.58/7.68 hole_car2_0 :: car 20.58/7.68 hole_true:false3_0 :: true:false 20.58/7.68 gen_nil:.4_0 :: Nat -> nil:. 20.58/7.68 20.58/7.68 20.58/7.68 Lemmas: 20.58/7.68 ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 20.58/7.68 20.58/7.68 20.58/7.68 Generator Equations: 20.58/7.68 gen_nil:.4_0(0) <=> nil 20.58/7.68 gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x)) 20.58/7.68 20.58/7.68 20.58/7.68 The following defined symbols remain to be analysed: 20.58/7.68 rev 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (25) RewriteLemmaProof (LOWER BOUND(ID)) 20.58/7.68 Proved the following rewrite lemma: 20.58/7.68 rev(gen_nil:.4_0(n495_0)) -> gen_nil:.4_0(n495_0), rt in Omega(1 + n495_0 + n495_0^2) 20.58/7.68 20.58/7.68 Induction Base: 20.58/7.68 rev(gen_nil:.4_0(0)) ->_R^Omega(1) 20.58/7.68 nil 20.58/7.68 20.58/7.68 Induction Step: 20.58/7.68 rev(gen_nil:.4_0(+(n495_0, 1))) ->_R^Omega(1) 20.58/7.68 ++(rev(gen_nil:.4_0(n495_0)), .(hole_car2_0, nil)) ->_IH 20.58/7.68 ++(gen_nil:.4_0(c496_0), .(hole_car2_0, nil)) ->_L^Omega(1 + n495_0) 20.58/7.68 gen_nil:.4_0(+(n495_0, +(0, 1))) 20.58/7.68 20.58/7.68 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (26) 20.58/7.68 Obligation: 20.58/7.68 Proved the lower bound n^2 for the following obligation: 20.58/7.68 20.58/7.68 TRS: 20.58/7.68 Rules: 20.58/7.68 rev(nil) -> nil 20.58/7.68 rev(.(x, y)) -> ++(rev(y), .(x, nil)) 20.58/7.68 car(.(x, y)) -> x 20.58/7.68 cdr(.(x, y)) -> y 20.58/7.68 null(nil) -> true 20.58/7.68 null(.(x, y)) -> false 20.58/7.68 ++(nil, y) -> y 20.58/7.68 ++(.(x, y), z) -> .(x, ++(y, z)) 20.58/7.68 20.58/7.68 Types: 20.58/7.68 rev :: nil:. -> nil:. 20.58/7.68 nil :: nil:. 20.58/7.68 . :: car -> nil:. -> nil:. 20.58/7.68 ++ :: nil:. -> nil:. -> nil:. 20.58/7.68 car :: nil:. -> car 20.58/7.68 cdr :: nil:. -> nil:. 20.58/7.68 null :: nil:. -> true:false 20.58/7.68 true :: true:false 20.58/7.68 false :: true:false 20.58/7.68 hole_nil:.1_0 :: nil:. 20.58/7.68 hole_car2_0 :: car 20.58/7.68 hole_true:false3_0 :: true:false 20.58/7.68 gen_nil:.4_0 :: Nat -> nil:. 20.58/7.68 20.58/7.68 20.58/7.68 Lemmas: 20.58/7.68 ++(gen_nil:.4_0(n6_0), gen_nil:.4_0(b)) -> gen_nil:.4_0(+(n6_0, b)), rt in Omega(1 + n6_0) 20.58/7.68 20.58/7.68 20.58/7.68 Generator Equations: 20.58/7.68 gen_nil:.4_0(0) <=> nil 20.58/7.68 gen_nil:.4_0(+(x, 1)) <=> .(hole_car2_0, gen_nil:.4_0(x)) 20.58/7.68 20.58/7.68 20.58/7.68 The following defined symbols remain to be analysed: 20.58/7.68 rev 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (27) LowerBoundPropagationProof (FINISHED) 20.58/7.68 Propagated lower bound. 20.58/7.68 ---------------------------------------- 20.58/7.68 20.58/7.68 (28) 20.58/7.68 BOUNDS(n^2, INF) 20.80/7.72 EOF