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