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