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