20.87/6.24 WORST_CASE(Omega(n^1), O(n^1)) 20.87/6.25 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 20.87/6.25 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 20.87/6.25 20.87/6.25 20.87/6.25 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.87/6.25 20.87/6.25 (0) CpxTRS 20.87/6.25 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 20.87/6.25 (2) CpxTRS 20.87/6.25 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 20.87/6.25 (4) CpxWeightedTrs 20.87/6.25 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 20.87/6.25 (6) CpxTypedWeightedTrs 20.87/6.25 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 20.87/6.25 (8) CpxTypedWeightedCompleteTrs 20.87/6.25 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 20.87/6.25 (10) CpxRNTS 20.87/6.25 (11) CompleteCoflocoProof [FINISHED, 128 ms] 20.87/6.25 (12) BOUNDS(1, n^1) 20.87/6.25 (13) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 20.87/6.25 (14) TRS for Loop Detection 20.87/6.25 (15) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 20.87/6.25 (16) BEST 20.87/6.25 (17) proven lower bound 20.87/6.25 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 20.87/6.25 (19) BOUNDS(n^1, INF) 20.87/6.25 (20) TRS for Loop Detection 20.87/6.25 20.87/6.25 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (0) 20.87/6.25 Obligation: 20.87/6.25 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.87/6.25 20.87/6.25 20.87/6.25 The TRS R consists of the following rules: 20.87/6.25 20.87/6.25 half(0) -> 0 20.87/6.25 half(s(s(x))) -> s(half(x)) 20.87/6.25 log(s(0)) -> 0 20.87/6.25 log(s(s(x))) -> s(log(s(half(x)))) 20.87/6.25 20.87/6.25 S is empty. 20.87/6.25 Rewrite Strategy: FULL 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 20.87/6.25 Converted rc-obligation to irc-obligation. 20.87/6.25 20.87/6.25 As the TRS is a non-duplicating overlay system, we have rc = irc. 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (2) 20.87/6.25 Obligation: 20.87/6.25 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 20.87/6.25 20.87/6.25 20.87/6.25 The TRS R consists of the following rules: 20.87/6.25 20.87/6.25 half(0) -> 0 20.87/6.25 half(s(s(x))) -> s(half(x)) 20.87/6.25 log(s(0)) -> 0 20.87/6.25 log(s(s(x))) -> s(log(s(half(x)))) 20.87/6.25 20.87/6.25 S is empty. 20.87/6.25 Rewrite Strategy: INNERMOST 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 20.87/6.25 Transformed relative TRS to weighted TRS 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (4) 20.87/6.25 Obligation: 20.87/6.25 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 20.87/6.25 20.87/6.25 20.87/6.25 The TRS R consists of the following rules: 20.87/6.25 20.87/6.25 half(0) -> 0 [1] 20.87/6.25 half(s(s(x))) -> s(half(x)) [1] 20.87/6.25 log(s(0)) -> 0 [1] 20.87/6.25 log(s(s(x))) -> s(log(s(half(x)))) [1] 20.87/6.25 20.87/6.25 Rewrite Strategy: INNERMOST 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 20.87/6.25 Infered types. 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (6) 20.87/6.25 Obligation: 20.87/6.25 Runtime Complexity Weighted TRS with Types. 20.87/6.25 The TRS R consists of the following rules: 20.87/6.25 20.87/6.25 half(0) -> 0 [1] 20.87/6.25 half(s(s(x))) -> s(half(x)) [1] 20.87/6.25 log(s(0)) -> 0 [1] 20.87/6.25 log(s(s(x))) -> s(log(s(half(x)))) [1] 20.87/6.25 20.87/6.25 The TRS has the following type information: 20.87/6.25 half :: 0:s -> 0:s 20.87/6.25 0 :: 0:s 20.87/6.25 s :: 0:s -> 0:s 20.87/6.25 log :: 0:s -> 0:s 20.87/6.25 20.87/6.25 Rewrite Strategy: INNERMOST 20.87/6.25 ---------------------------------------- 20.87/6.25 20.87/6.25 (7) CompletionProof (UPPER BOUND(ID)) 20.87/6.25 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 20.87/6.26 20.87/6.26 half(v0) -> null_half [0] 20.87/6.26 log(v0) -> null_log [0] 20.87/6.26 20.87/6.26 And the following fresh constants: null_half, null_log 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (8) 20.87/6.26 Obligation: 20.87/6.26 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 20.87/6.26 20.87/6.26 Runtime Complexity Weighted TRS with Types. 20.87/6.26 The TRS R consists of the following rules: 20.87/6.26 20.87/6.26 half(0) -> 0 [1] 20.87/6.26 half(s(s(x))) -> s(half(x)) [1] 20.87/6.26 log(s(0)) -> 0 [1] 20.87/6.26 log(s(s(x))) -> s(log(s(half(x)))) [1] 20.87/6.26 half(v0) -> null_half [0] 20.87/6.26 log(v0) -> null_log [0] 20.87/6.26 20.87/6.26 The TRS has the following type information: 20.87/6.26 half :: 0:s:null_half:null_log -> 0:s:null_half:null_log 20.87/6.26 0 :: 0:s:null_half:null_log 20.87/6.26 s :: 0:s:null_half:null_log -> 0:s:null_half:null_log 20.87/6.26 log :: 0:s:null_half:null_log -> 0:s:null_half:null_log 20.87/6.26 null_half :: 0:s:null_half:null_log 20.87/6.26 null_log :: 0:s:null_half:null_log 20.87/6.26 20.87/6.26 Rewrite Strategy: INNERMOST 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 20.87/6.26 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 20.87/6.26 The constant constructors are abstracted as follows: 20.87/6.26 20.87/6.26 0 => 0 20.87/6.26 null_half => 0 20.87/6.26 null_log => 0 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (10) 20.87/6.26 Obligation: 20.87/6.26 Complexity RNTS consisting of the following rules: 20.87/6.26 20.87/6.26 half(z) -{ 1 }-> 0 :|: z = 0 20.87/6.26 half(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 20.87/6.26 half(z) -{ 1 }-> 1 + half(x) :|: x >= 0, z = 1 + (1 + x) 20.87/6.26 log(z) -{ 1 }-> 0 :|: z = 1 + 0 20.87/6.26 log(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 20.87/6.26 log(z) -{ 1 }-> 1 + log(1 + half(x)) :|: x >= 0, z = 1 + (1 + x) 20.87/6.26 20.87/6.26 Only complete derivations are relevant for the runtime complexity. 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (11) CompleteCoflocoProof (FINISHED) 20.87/6.26 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 20.87/6.26 20.87/6.26 eq(start(V),0,[half(V, Out)],[V >= 0]). 20.87/6.26 eq(start(V),0,[log(V, Out)],[V >= 0]). 20.87/6.26 eq(half(V, Out),1,[],[Out = 0,V = 0]). 20.87/6.26 eq(half(V, Out),1,[half(V1, Ret1)],[Out = 1 + Ret1,V1 >= 0,V = 2 + V1]). 20.87/6.26 eq(log(V, Out),1,[],[Out = 0,V = 1]). 20.87/6.26 eq(log(V, Out),1,[half(V2, Ret101),log(1 + Ret101, Ret11)],[Out = 1 + Ret11,V2 >= 0,V = 2 + V2]). 20.87/6.26 eq(half(V, Out),0,[],[Out = 0,V3 >= 0,V = V3]). 20.87/6.26 eq(log(V, Out),0,[],[Out = 0,V4 >= 0,V = V4]). 20.87/6.26 input_output_vars(half(V,Out),[V],[Out]). 20.87/6.26 input_output_vars(log(V,Out),[V],[Out]). 20.87/6.26 20.87/6.26 20.87/6.26 CoFloCo proof output: 20.87/6.26 Preprocessing Cost Relations 20.87/6.26 ===================================== 20.87/6.26 20.87/6.26 #### Computed strongly connected components 20.87/6.26 0. recursive : [half/2] 20.87/6.26 1. recursive : [log/2] 20.87/6.26 2. non_recursive : [start/1] 20.87/6.26 20.87/6.26 #### Obtained direct recursion through partial evaluation 20.87/6.26 0. SCC is partially evaluated into half/2 20.87/6.26 1. SCC is partially evaluated into log/2 20.87/6.26 2. SCC is partially evaluated into start/1 20.87/6.26 20.87/6.26 Control-Flow Refinement of Cost Relations 20.87/6.26 ===================================== 20.87/6.26 20.87/6.26 ### Specialization of cost equations half/2 20.87/6.26 * CE 3 is refined into CE [9] 20.87/6.26 * CE 5 is refined into CE [10] 20.87/6.26 * CE 4 is refined into CE [11] 20.87/6.26 20.87/6.26 20.87/6.26 ### Cost equations --> "Loop" of half/2 20.87/6.26 * CEs [11] --> Loop 6 20.87/6.26 * CEs [9,10] --> Loop 7 20.87/6.26 20.87/6.26 ### Ranking functions of CR half(V,Out) 20.87/6.26 * RF of phase [6]: [V-1] 20.87/6.26 20.87/6.26 #### Partial ranking functions of CR half(V,Out) 20.87/6.26 * Partial RF of phase [6]: 20.87/6.26 - RF of loop [6:1]: 20.87/6.26 V-1 20.87/6.26 20.87/6.26 20.87/6.26 ### Specialization of cost equations log/2 20.87/6.26 * CE 6 is refined into CE [12] 20.87/6.26 * CE 8 is refined into CE [13] 20.87/6.26 * CE 7 is refined into CE [14,15] 20.87/6.26 20.87/6.26 20.87/6.26 ### Cost equations --> "Loop" of log/2 20.87/6.26 * CEs [15] --> Loop 8 20.87/6.26 * CEs [14] --> Loop 9 20.87/6.26 * CEs [12,13] --> Loop 10 20.87/6.26 20.87/6.26 ### Ranking functions of CR log(V,Out) 20.87/6.26 * RF of phase [8]: [V-3] 20.87/6.26 20.87/6.26 #### Partial ranking functions of CR log(V,Out) 20.87/6.26 * Partial RF of phase [8]: 20.87/6.26 - RF of loop [8:1]: 20.87/6.26 V-3 20.87/6.26 20.87/6.26 20.87/6.26 ### Specialization of cost equations start/1 20.87/6.26 * CE 1 is refined into CE [16,17] 20.87/6.26 * CE 2 is refined into CE [18,19,20,21] 20.87/6.26 20.87/6.26 20.87/6.26 ### Cost equations --> "Loop" of start/1 20.87/6.26 * CEs [16,17,18,19,20,21] --> Loop 11 20.87/6.26 20.87/6.26 ### Ranking functions of CR start(V) 20.87/6.26 20.87/6.26 #### Partial ranking functions of CR start(V) 20.87/6.26 20.87/6.26 20.87/6.26 Computing Bounds 20.87/6.26 ===================================== 20.87/6.26 20.87/6.26 #### Cost of chains of half(V,Out): 20.87/6.26 * Chain [[6],7]: 1*it(6)+1 20.87/6.26 Such that:it(6) =< 2*Out 20.87/6.26 20.87/6.26 with precondition: [Out>=1,V>=2*Out] 20.87/6.26 20.87/6.26 * Chain [7]: 1 20.87/6.26 with precondition: [Out=0,V>=0] 20.87/6.26 20.87/6.26 20.87/6.26 #### Cost of chains of log(V,Out): 20.87/6.26 * Chain [[8],10]: 2*it(8)+1*s(3)+1 20.87/6.26 Such that:it(8) =< V 20.87/6.26 s(3) =< 2*V 20.87/6.26 20.87/6.26 with precondition: [Out>=1,V>=4*Out] 20.87/6.26 20.87/6.26 * Chain [[8],9,10]: 2*it(8)+1*s(3)+3 20.87/6.26 Such that:it(8) =< V 20.87/6.26 s(3) =< 2*V 20.87/6.26 20.87/6.26 with precondition: [Out>=2,V+4>=4*Out] 20.87/6.26 20.87/6.26 * Chain [10]: 1 20.87/6.26 with precondition: [Out=0,V>=0] 20.87/6.26 20.87/6.26 * Chain [9,10]: 3 20.87/6.26 with precondition: [Out=1,V>=2] 20.87/6.26 20.87/6.26 20.87/6.26 #### Cost of chains of start(V): 20.87/6.26 * Chain [11]: 5*s(4)+2*s(6)+3 20.87/6.26 Such that:aux(1) =< V 20.87/6.26 aux(2) =< 2*V 20.87/6.26 s(4) =< aux(1) 20.87/6.26 s(6) =< aux(2) 20.87/6.26 20.87/6.26 with precondition: [V>=0] 20.87/6.26 20.87/6.26 20.87/6.26 Closed-form bounds of start(V): 20.87/6.26 ------------------------------------- 20.87/6.26 * Chain [11] with precondition: [V>=0] 20.87/6.26 - Upper bound: 9*V+3 20.87/6.26 - Complexity: n 20.87/6.26 20.87/6.26 ### Maximum cost of start(V): 9*V+3 20.87/6.26 Asymptotic class: n 20.87/6.26 * Total analysis performed in 83 ms. 20.87/6.26 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (12) 20.87/6.26 BOUNDS(1, n^1) 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (13) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 20.87/6.26 Transformed a relative TRS into a decreasing-loop problem. 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (14) 20.87/6.26 Obligation: 20.87/6.26 Analyzing the following TRS for decreasing loops: 20.87/6.26 20.87/6.26 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.87/6.26 20.87/6.26 20.87/6.26 The TRS R consists of the following rules: 20.87/6.26 20.87/6.26 half(0) -> 0 20.87/6.26 half(s(s(x))) -> s(half(x)) 20.87/6.26 log(s(0)) -> 0 20.87/6.26 log(s(s(x))) -> s(log(s(half(x)))) 20.87/6.26 20.87/6.26 S is empty. 20.87/6.26 Rewrite Strategy: FULL 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (15) DecreasingLoopProof (LOWER BOUND(ID)) 20.87/6.26 The following loop(s) give(s) rise to the lower bound Omega(n^1): 20.87/6.26 20.87/6.26 The rewrite sequence 20.87/6.26 20.87/6.26 half(s(s(x))) ->^+ s(half(x)) 20.87/6.26 20.87/6.26 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 20.87/6.26 20.87/6.26 The pumping substitution is [x / s(s(x))]. 20.87/6.26 20.87/6.26 The result substitution is [ ]. 20.87/6.26 20.87/6.26 20.87/6.26 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (16) 20.87/6.26 Complex Obligation (BEST) 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (17) 20.87/6.26 Obligation: 20.87/6.26 Proved the lower bound n^1 for the following obligation: 20.87/6.26 20.87/6.26 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.87/6.26 20.87/6.26 20.87/6.26 The TRS R consists of the following rules: 20.87/6.26 20.87/6.26 half(0) -> 0 20.87/6.26 half(s(s(x))) -> s(half(x)) 20.87/6.26 log(s(0)) -> 0 20.87/6.26 log(s(s(x))) -> s(log(s(half(x)))) 20.87/6.26 20.87/6.26 S is empty. 20.87/6.26 Rewrite Strategy: FULL 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (18) LowerBoundPropagationProof (FINISHED) 20.87/6.26 Propagated lower bound. 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (19) 20.87/6.26 BOUNDS(n^1, INF) 20.87/6.26 20.87/6.26 ---------------------------------------- 20.87/6.26 20.87/6.26 (20) 20.87/6.26 Obligation: 20.87/6.26 Analyzing the following TRS for decreasing loops: 20.87/6.26 20.87/6.26 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 20.87/6.26 20.87/6.26 20.87/6.26 The TRS R consists of the following rules: 20.87/6.26 20.87/6.26 half(0) -> 0 20.87/6.26 half(s(s(x))) -> s(half(x)) 20.87/6.26 log(s(0)) -> 0 20.87/6.26 log(s(s(x))) -> s(log(s(half(x)))) 20.87/6.26 20.87/6.26 S is empty. 20.87/6.26 Rewrite Strategy: FULL 20.87/6.30 EOF