19.29/6.01 WORST_CASE(Omega(n^2), O(n^2)) 19.41/6.04 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 19.41/6.04 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 19.41/6.04 19.41/6.04 19.41/6.04 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 19.41/6.04 19.41/6.04 (0) CpxTRS 19.41/6.04 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 19.41/6.04 (2) CpxWeightedTrs 19.41/6.04 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 19.41/6.04 (4) CpxTypedWeightedTrs 19.41/6.04 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 19.41/6.04 (6) CpxTypedWeightedCompleteTrs 19.41/6.04 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 19.41/6.04 (8) CpxRNTS 19.41/6.04 (9) CompleteCoflocoProof [FINISHED, 265 ms] 19.41/6.04 (10) BOUNDS(1, n^2) 19.41/6.04 (11) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 19.41/6.04 (12) CpxTRS 19.41/6.04 (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 19.41/6.04 (14) typed CpxTrs 19.41/6.04 (15) OrderProof [LOWER BOUND(ID), 0 ms] 19.41/6.04 (16) typed CpxTrs 19.41/6.04 (17) RewriteLemmaProof [LOWER BOUND(ID), 261 ms] 19.41/6.04 (18) BEST 19.41/6.04 (19) proven lower bound 19.41/6.04 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 19.41/6.04 (21) BOUNDS(n^1, INF) 19.41/6.04 (22) typed CpxTrs 19.41/6.04 (23) RewriteLemmaProof [LOWER BOUND(ID), 80 ms] 19.41/6.04 (24) proven lower bound 19.41/6.04 (25) LowerBoundPropagationProof [FINISHED, 0 ms] 19.41/6.04 (26) BOUNDS(n^2, INF) 19.41/6.04 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (0) 19.41/6.04 Obligation: 19.41/6.04 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). 19.41/6.04 19.41/6.04 19.41/6.04 The TRS R consists of the following rules: 19.41/6.04 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0) -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0) -> 0 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 S is empty. 19.41/6.04 Rewrite Strategy: INNERMOST 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 19.41/6.04 Transformed relative TRS to weighted TRS 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (2) 19.41/6.04 Obligation: 19.41/6.04 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 19.41/6.04 19.41/6.04 19.41/6.04 The TRS R consists of the following rules: 19.41/6.04 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) [1] 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) [1] 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) [1] 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) [1] 19.41/6.04 plus(N, 0) -> N [1] 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) [1] 19.41/6.04 x(N, 0) -> 0 [1] 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) [1] 19.41/6.04 activate(X) -> X [1] 19.41/6.04 19.41/6.04 Rewrite Strategy: INNERMOST 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 19.41/6.04 Infered types. 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (4) 19.41/6.04 Obligation: 19.41/6.04 Runtime Complexity Weighted TRS with Types. 19.41/6.04 The TRS R consists of the following rules: 19.41/6.04 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) [1] 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) [1] 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) [1] 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) [1] 19.41/6.04 plus(N, 0) -> N [1] 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) [1] 19.41/6.04 x(N, 0) -> 0 [1] 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) [1] 19.41/6.04 activate(X) -> X [1] 19.41/6.04 19.41/6.04 The TRS has the following type information: 19.41/6.04 U11 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 activate :: s:0 -> s:0 19.41/6.04 s :: s:0 -> s:0 19.41/6.04 plus :: s:0 -> s:0 -> s:0 19.41/6.04 U21 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 U22 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 x :: s:0 -> s:0 -> s:0 19.41/6.04 0 :: s:0 19.41/6.04 19.41/6.04 Rewrite Strategy: INNERMOST 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (5) CompletionProof (UPPER BOUND(ID)) 19.41/6.04 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 19.41/6.04 none 19.41/6.04 19.41/6.04 And the following fresh constants: none 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (6) 19.41/6.04 Obligation: 19.41/6.04 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 19.41/6.04 19.41/6.04 Runtime Complexity Weighted TRS with Types. 19.41/6.04 The TRS R consists of the following rules: 19.41/6.04 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) [1] 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) [1] 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) [1] 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) [1] 19.41/6.04 plus(N, 0) -> N [1] 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) [1] 19.41/6.04 x(N, 0) -> 0 [1] 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) [1] 19.41/6.04 activate(X) -> X [1] 19.41/6.04 19.41/6.04 The TRS has the following type information: 19.41/6.04 U11 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 activate :: s:0 -> s:0 19.41/6.04 s :: s:0 -> s:0 19.41/6.04 plus :: s:0 -> s:0 -> s:0 19.41/6.04 U21 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 U22 :: tt -> s:0 -> s:0 -> s:0 19.41/6.04 x :: s:0 -> s:0 -> s:0 19.41/6.04 0 :: s:0 19.41/6.04 19.41/6.04 Rewrite Strategy: INNERMOST 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 19.41/6.04 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 19.41/6.04 The constant constructors are abstracted as follows: 19.41/6.04 19.41/6.04 tt => 0 19.41/6.04 0 => 0 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (8) 19.41/6.04 Obligation: 19.41/6.04 Complexity RNTS consisting of the following rules: 19.41/6.04 19.41/6.04 U11(z, z', z'') -{ 1 }-> U12(0, activate(M), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0 19.41/6.04 U12(z, z', z'') -{ 1 }-> 1 + plus(activate(N), activate(M)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0 19.41/6.04 U21(z, z', z'') -{ 1 }-> U22(0, activate(M), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0 19.41/6.04 U22(z, z', z'') -{ 1 }-> plus(x(activate(N), activate(M)), activate(N)) :|: z' = M, z = 0, z'' = N, M >= 0, N >= 0 19.41/6.04 activate(z) -{ 1 }-> X :|: X >= 0, z = X 19.41/6.04 plus(z, z') -{ 1 }-> N :|: z = N, z' = 0, N >= 0 19.41/6.04 plus(z, z') -{ 1 }-> U11(0, M, N) :|: z' = 1 + M, z = N, M >= 0, N >= 0 19.41/6.04 x(z, z') -{ 1 }-> U21(0, M, N) :|: z' = 1 + M, z = N, M >= 0, N >= 0 19.41/6.04 x(z, z') -{ 1 }-> 0 :|: z = N, z' = 0, N >= 0 19.41/6.04 19.41/6.04 Only complete derivations are relevant for the runtime complexity. 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (9) CompleteCoflocoProof (FINISHED) 19.41/6.04 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 19.41/6.04 19.41/6.04 eq(start(V1, V, V2),0,[fun(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). 19.41/6.04 eq(start(V1, V, V2),0,[fun1(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). 19.41/6.04 eq(start(V1, V, V2),0,[fun2(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). 19.41/6.04 eq(start(V1, V, V2),0,[fun3(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). 19.41/6.04 eq(start(V1, V, V2),0,[plus(V1, V, Out)],[V1 >= 0,V >= 0]). 19.41/6.04 eq(start(V1, V, V2),0,[x(V1, V, Out)],[V1 >= 0,V >= 0]). 19.41/6.04 eq(start(V1, V, V2),0,[activate(V1, Out)],[V1 >= 0]). 19.41/6.04 eq(fun(V1, V, V2, Out),1,[activate(M1, Ret1),activate(N1, Ret2),fun1(0, Ret1, Ret2, Ret)],[Out = Ret,V = M1,V1 = 0,V2 = N1,M1 >= 0,N1 >= 0]). 19.41/6.04 eq(fun1(V1, V, V2, Out),1,[activate(N2, Ret10),activate(M2, Ret11),plus(Ret10, Ret11, Ret12)],[Out = 1 + Ret12,V = M2,V1 = 0,V2 = N2,M2 >= 0,N2 >= 0]). 19.41/6.04 eq(fun2(V1, V, V2, Out),1,[activate(M3, Ret13),activate(N3, Ret21),fun3(0, Ret13, Ret21, Ret3)],[Out = Ret3,V = M3,V1 = 0,V2 = N3,M3 >= 0,N3 >= 0]). 19.41/6.04 eq(fun3(V1, V, V2, Out),1,[activate(N4, Ret00),activate(M4, Ret01),x(Ret00, Ret01, Ret0),activate(N4, Ret14),plus(Ret0, Ret14, Ret4)],[Out = Ret4,V = M4,V1 = 0,V2 = N4,M4 >= 0,N4 >= 0]). 19.41/6.04 eq(plus(V1, V, Out),1,[],[Out = N5,V1 = N5,V = 0,N5 >= 0]). 19.41/6.04 eq(plus(V1, V, Out),1,[fun(0, M5, N6, Ret5)],[Out = Ret5,V = 1 + M5,V1 = N6,M5 >= 0,N6 >= 0]). 19.41/6.04 eq(x(V1, V, Out),1,[],[Out = 0,V1 = N7,V = 0,N7 >= 0]). 19.41/6.04 eq(x(V1, V, Out),1,[fun2(0, M6, N8, Ret6)],[Out = Ret6,V = 1 + M6,V1 = N8,M6 >= 0,N8 >= 0]). 19.41/6.04 eq(activate(V1, Out),1,[],[Out = X1,X1 >= 0,V1 = X1]). 19.41/6.04 input_output_vars(fun(V1,V,V2,Out),[V1,V,V2],[Out]). 19.41/6.04 input_output_vars(fun1(V1,V,V2,Out),[V1,V,V2],[Out]). 19.41/6.04 input_output_vars(fun2(V1,V,V2,Out),[V1,V,V2],[Out]). 19.41/6.04 input_output_vars(fun3(V1,V,V2,Out),[V1,V,V2],[Out]). 19.41/6.04 input_output_vars(plus(V1,V,Out),[V1,V],[Out]). 19.41/6.04 input_output_vars(x(V1,V,Out),[V1,V],[Out]). 19.41/6.04 input_output_vars(activate(V1,Out),[V1],[Out]). 19.41/6.04 19.41/6.04 19.41/6.04 CoFloCo proof output: 19.41/6.04 Preprocessing Cost Relations 19.41/6.04 ===================================== 19.41/6.04 19.41/6.04 #### Computed strongly connected components 19.41/6.04 0. non_recursive : [activate/2] 19.41/6.04 1. recursive : [fun/4,fun1/4,plus/3] 19.41/6.04 2. recursive [non_tail] : [fun2/4,fun3/4,x/3] 19.41/6.04 3. non_recursive : [start/3] 19.41/6.04 19.41/6.04 #### Obtained direct recursion through partial evaluation 19.41/6.04 0. SCC is completely evaluated into other SCCs 19.41/6.04 1. SCC is partially evaluated into plus/3 19.41/6.04 2. SCC is partially evaluated into x/3 19.41/6.04 3. SCC is partially evaluated into start/3 19.41/6.04 19.41/6.04 Control-Flow Refinement of Cost Relations 19.41/6.04 ===================================== 19.41/6.04 19.41/6.04 ### Specialization of cost equations plus/3 19.41/6.04 * CE 11 is refined into CE [12] 19.41/6.04 * CE 10 is refined into CE [13] 19.41/6.04 19.41/6.04 19.41/6.04 ### Cost equations --> "Loop" of plus/3 19.41/6.04 * CEs [13] --> Loop 6 19.41/6.04 * CEs [12] --> Loop 7 19.41/6.04 19.41/6.04 ### Ranking functions of CR plus(V1,V,Out) 19.41/6.04 * RF of phase [6]: [V] 19.41/6.04 19.41/6.04 #### Partial ranking functions of CR plus(V1,V,Out) 19.41/6.04 * Partial RF of phase [6]: 19.41/6.04 - RF of loop [6:1]: 19.41/6.04 V 19.41/6.04 19.41/6.04 19.41/6.04 ### Specialization of cost equations x/3 19.41/6.04 * CE 9 is refined into CE [14] 19.41/6.04 * CE 8 is refined into CE [15,16] 19.41/6.04 19.41/6.04 19.41/6.04 ### Cost equations --> "Loop" of x/3 19.41/6.04 * CEs [16] --> Loop 8 19.41/6.04 * CEs [15] --> Loop 9 19.41/6.04 * CEs [14] --> Loop 10 19.41/6.04 19.41/6.04 ### Ranking functions of CR x(V1,V,Out) 19.41/6.04 * RF of phase [8]: [V] 19.41/6.04 * RF of phase [9]: [V] 19.41/6.04 19.41/6.04 #### Partial ranking functions of CR x(V1,V,Out) 19.41/6.04 * Partial RF of phase [8]: 19.41/6.04 - RF of loop [8:1]: 19.41/6.04 V 19.41/6.04 * Partial RF of phase [9]: 19.41/6.04 - RF of loop [9:1]: 19.41/6.04 V 19.41/6.04 19.41/6.04 19.41/6.04 ### Specialization of cost equations start/3 19.41/6.04 * CE 1 is refined into CE [17,18,19,20] 19.41/6.04 * CE 2 is refined into CE [21,22,23,24] 19.41/6.04 * CE 3 is refined into CE [25,26] 19.41/6.04 * CE 4 is refined into CE [27,28] 19.41/6.04 * CE 5 is refined into CE [29,30] 19.41/6.04 * CE 6 is refined into CE [31,32,33] 19.41/6.04 * CE 7 is refined into CE [34] 19.41/6.04 19.41/6.04 19.41/6.04 ### Cost equations --> "Loop" of start/3 19.41/6.04 * CEs [17,20,21,24,26,28,31] --> Loop 11 19.41/6.04 * CEs [18,19,22,23,25,27,29,30,32,33,34] --> Loop 12 19.41/6.04 19.41/6.04 ### Ranking functions of CR start(V1,V,V2) 19.41/6.04 19.41/6.04 #### Partial ranking functions of CR start(V1,V,V2) 19.41/6.04 19.41/6.04 19.41/6.04 Computing Bounds 19.41/6.04 ===================================== 19.41/6.04 19.41/6.04 #### Cost of chains of plus(V1,V,Out): 19.41/6.04 * Chain [[6],7]: 7*it(6)+1 19.41/6.04 Such that:it(6) =< V 19.41/6.04 19.41/6.04 with precondition: [V+V1=Out,V1>=0,V>=1] 19.41/6.04 19.41/6.04 * Chain [7]: 1 19.41/6.04 with precondition: [V=0,V1=Out,V1>=0] 19.41/6.04 19.41/6.04 19.41/6.04 #### Cost of chains of x(V1,V,Out): 19.41/6.04 * Chain [[9],10]: 9*it(9)+1 19.41/6.04 Such that:it(9) =< V 19.41/6.04 19.41/6.04 with precondition: [V1=0,Out=0,V>=1] 19.41/6.04 19.41/6.04 * Chain [[8],10]: 9*it(8)+7*s(3)+1 19.41/6.04 Such that:aux(1) =< V1 19.41/6.04 it(8) =< V 19.41/6.04 s(3) =< it(8)*aux(1) 19.41/6.04 19.41/6.04 with precondition: [V1>=1,V>=1,Out+1>=V+V1] 19.41/6.04 19.41/6.04 * Chain [10]: 1 19.41/6.04 with precondition: [V=0,Out=0,V1>=0] 19.41/6.04 19.41/6.04 19.41/6.04 #### Cost of chains of start(V1,V,V2): 19.41/6.04 * Chain [12]: 14*s(4)+16*s(6)+7*s(9)+9 19.41/6.04 Such that:s(7) =< V1 19.41/6.04 aux(2) =< V 19.41/6.04 aux(3) =< V2 19.41/6.04 s(6) =< aux(2) 19.41/6.04 s(4) =< aux(3) 19.41/6.04 s(9) =< s(6)*s(7) 19.41/6.04 19.41/6.04 with precondition: [V1>=0] 19.41/6.04 19.41/6.04 * Chain [11]: 59*s(10)+14*s(13)+14*s(14)+9 19.41/6.04 Such that:aux(6) =< V 19.41/6.04 aux(7) =< V2 19.41/6.04 s(10) =< aux(6) 19.41/6.04 s(14) =< aux(7) 19.41/6.04 s(13) =< s(10)*aux(7) 19.41/6.04 19.41/6.04 with precondition: [V1=0,V>=1] 19.41/6.04 19.41/6.04 19.41/6.04 Closed-form bounds of start(V1,V,V2): 19.41/6.04 ------------------------------------- 19.41/6.04 * Chain [12] with precondition: [V1>=0] 19.41/6.04 - Upper bound: 7*V1*nat(V)+9+nat(V)*16+nat(V2)*14 19.41/6.04 - Complexity: n^2 19.41/6.04 * Chain [11] with precondition: [V1=0,V>=1] 19.41/6.04 - Upper bound: 59*V+9+14*V*nat(V2)+nat(V2)*14 19.41/6.04 - Complexity: n^2 19.41/6.04 19.41/6.04 ### Maximum cost of start(V1,V,V2): nat(V)*16+9+nat(V2)*14+max([7*V1*nat(V),nat(V)*14*nat(V2)+nat(V)*43]) 19.41/6.04 Asymptotic class: n^2 19.41/6.04 * Total analysis performed in 202 ms. 19.41/6.04 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (10) 19.41/6.04 BOUNDS(1, n^2) 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (11) RenamingProof (BOTH BOUNDS(ID, ID)) 19.41/6.04 Renamed function symbols to avoid clashes with predefined symbol. 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (12) 19.41/6.04 Obligation: 19.41/6.04 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 19.41/6.04 19.41/6.04 19.41/6.04 The TRS R consists of the following rules: 19.41/6.04 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0') -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0') -> 0' 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 S is empty. 19.41/6.04 Rewrite Strategy: INNERMOST 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 19.41/6.04 Infered types. 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (14) 19.41/6.04 Obligation: 19.41/6.04 Innermost TRS: 19.41/6.04 Rules: 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0') -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0') -> 0' 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 Types: 19.41/6.04 U11 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 activate :: s:0' -> s:0' 19.41/6.04 s :: s:0' -> s:0' 19.41/6.04 plus :: s:0' -> s:0' -> s:0' 19.41/6.04 U21 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 U22 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 x :: s:0' -> s:0' -> s:0' 19.41/6.04 0' :: s:0' 19.41/6.04 hole_s:0'1_0 :: s:0' 19.41/6.04 hole_tt2_0 :: tt 19.41/6.04 gen_s:0'3_0 :: Nat -> s:0' 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (15) OrderProof (LOWER BOUND(ID)) 19.41/6.04 Heuristically decided to analyse the following defined symbols: 19.41/6.04 plus, x 19.41/6.04 19.41/6.04 They will be analysed ascendingly in the following order: 19.41/6.04 plus < x 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (16) 19.41/6.04 Obligation: 19.41/6.04 Innermost TRS: 19.41/6.04 Rules: 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0') -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0') -> 0' 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 Types: 19.41/6.04 U11 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 activate :: s:0' -> s:0' 19.41/6.04 s :: s:0' -> s:0' 19.41/6.04 plus :: s:0' -> s:0' -> s:0' 19.41/6.04 U21 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 U22 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 x :: s:0' -> s:0' -> s:0' 19.41/6.04 0' :: s:0' 19.41/6.04 hole_s:0'1_0 :: s:0' 19.41/6.04 hole_tt2_0 :: tt 19.41/6.04 gen_s:0'3_0 :: Nat -> s:0' 19.41/6.04 19.41/6.04 19.41/6.04 Generator Equations: 19.41/6.04 gen_s:0'3_0(0) <=> 0' 19.41/6.04 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 19.41/6.04 19.41/6.04 19.41/6.04 The following defined symbols remain to be analysed: 19.41/6.04 plus, x 19.41/6.04 19.41/6.04 They will be analysed ascendingly in the following order: 19.41/6.04 plus < x 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (17) RewriteLemmaProof (LOWER BOUND(ID)) 19.41/6.04 Proved the following rewrite lemma: 19.41/6.04 plus(gen_s:0'3_0(a), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(+(n5_0, a)), rt in Omega(1 + n5_0) 19.41/6.04 19.41/6.04 Induction Base: 19.41/6.04 plus(gen_s:0'3_0(a), gen_s:0'3_0(0)) ->_R^Omega(1) 19.41/6.04 gen_s:0'3_0(a) 19.41/6.04 19.41/6.04 Induction Step: 19.41/6.04 plus(gen_s:0'3_0(a), gen_s:0'3_0(+(n5_0, 1))) ->_R^Omega(1) 19.41/6.04 U11(tt, gen_s:0'3_0(n5_0), gen_s:0'3_0(a)) ->_R^Omega(1) 19.41/6.04 U12(tt, activate(gen_s:0'3_0(n5_0)), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 U12(tt, gen_s:0'3_0(n5_0), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 U12(tt, gen_s:0'3_0(n5_0), gen_s:0'3_0(a)) ->_R^Omega(1) 19.41/6.04 s(plus(activate(gen_s:0'3_0(a)), activate(gen_s:0'3_0(n5_0)))) ->_R^Omega(1) 19.41/6.04 s(plus(gen_s:0'3_0(a), activate(gen_s:0'3_0(n5_0)))) ->_R^Omega(1) 19.41/6.04 s(plus(gen_s:0'3_0(a), gen_s:0'3_0(n5_0))) ->_IH 19.41/6.04 s(gen_s:0'3_0(+(a, c6_0))) 19.41/6.04 19.41/6.04 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (18) 19.41/6.04 Complex Obligation (BEST) 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (19) 19.41/6.04 Obligation: 19.41/6.04 Proved the lower bound n^1 for the following obligation: 19.41/6.04 19.41/6.04 Innermost TRS: 19.41/6.04 Rules: 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0') -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0') -> 0' 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 Types: 19.41/6.04 U11 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 activate :: s:0' -> s:0' 19.41/6.04 s :: s:0' -> s:0' 19.41/6.04 plus :: s:0' -> s:0' -> s:0' 19.41/6.04 U21 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 U22 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 x :: s:0' -> s:0' -> s:0' 19.41/6.04 0' :: s:0' 19.41/6.04 hole_s:0'1_0 :: s:0' 19.41/6.04 hole_tt2_0 :: tt 19.41/6.04 gen_s:0'3_0 :: Nat -> s:0' 19.41/6.04 19.41/6.04 19.41/6.04 Generator Equations: 19.41/6.04 gen_s:0'3_0(0) <=> 0' 19.41/6.04 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 19.41/6.04 19.41/6.04 19.41/6.04 The following defined symbols remain to be analysed: 19.41/6.04 plus, x 19.41/6.04 19.41/6.04 They will be analysed ascendingly in the following order: 19.41/6.04 plus < x 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (20) LowerBoundPropagationProof (FINISHED) 19.41/6.04 Propagated lower bound. 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (21) 19.41/6.04 BOUNDS(n^1, INF) 19.41/6.04 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (22) 19.41/6.04 Obligation: 19.41/6.04 Innermost TRS: 19.41/6.04 Rules: 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0') -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0') -> 0' 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 Types: 19.41/6.04 U11 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 activate :: s:0' -> s:0' 19.41/6.04 s :: s:0' -> s:0' 19.41/6.04 plus :: s:0' -> s:0' -> s:0' 19.41/6.04 U21 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 U22 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 x :: s:0' -> s:0' -> s:0' 19.41/6.04 0' :: s:0' 19.41/6.04 hole_s:0'1_0 :: s:0' 19.41/6.04 hole_tt2_0 :: tt 19.41/6.04 gen_s:0'3_0 :: Nat -> s:0' 19.41/6.04 19.41/6.04 19.41/6.04 Lemmas: 19.41/6.04 plus(gen_s:0'3_0(a), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(+(n5_0, a)), rt in Omega(1 + n5_0) 19.41/6.04 19.41/6.04 19.41/6.04 Generator Equations: 19.41/6.04 gen_s:0'3_0(0) <=> 0' 19.41/6.04 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 19.41/6.04 19.41/6.04 19.41/6.04 The following defined symbols remain to be analysed: 19.41/6.04 x 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (23) RewriteLemmaProof (LOWER BOUND(ID)) 19.41/6.04 Proved the following rewrite lemma: 19.41/6.04 x(gen_s:0'3_0(a), gen_s:0'3_0(n742_0)) -> gen_s:0'3_0(*(n742_0, a)), rt in Omega(1 + a*n742_0 + n742_0) 19.41/6.04 19.41/6.04 Induction Base: 19.41/6.04 x(gen_s:0'3_0(a), gen_s:0'3_0(0)) ->_R^Omega(1) 19.41/6.04 0' 19.41/6.04 19.41/6.04 Induction Step: 19.41/6.04 x(gen_s:0'3_0(a), gen_s:0'3_0(+(n742_0, 1))) ->_R^Omega(1) 19.41/6.04 U21(tt, gen_s:0'3_0(n742_0), gen_s:0'3_0(a)) ->_R^Omega(1) 19.41/6.04 U22(tt, activate(gen_s:0'3_0(n742_0)), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 U22(tt, gen_s:0'3_0(n742_0), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 U22(tt, gen_s:0'3_0(n742_0), gen_s:0'3_0(a)) ->_R^Omega(1) 19.41/6.04 plus(x(activate(gen_s:0'3_0(a)), activate(gen_s:0'3_0(n742_0))), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 plus(x(gen_s:0'3_0(a), activate(gen_s:0'3_0(n742_0))), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 plus(x(gen_s:0'3_0(a), gen_s:0'3_0(n742_0)), activate(gen_s:0'3_0(a))) ->_IH 19.41/6.04 plus(gen_s:0'3_0(*(c743_0, a)), activate(gen_s:0'3_0(a))) ->_R^Omega(1) 19.41/6.04 plus(gen_s:0'3_0(*(n742_0, a)), gen_s:0'3_0(a)) ->_L^Omega(1 + a) 19.41/6.04 gen_s:0'3_0(+(a, *(n742_0, a))) 19.41/6.04 19.41/6.04 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (24) 19.41/6.04 Obligation: 19.41/6.04 Proved the lower bound n^2 for the following obligation: 19.41/6.04 19.41/6.04 Innermost TRS: 19.41/6.04 Rules: 19.41/6.04 U11(tt, M, N) -> U12(tt, activate(M), activate(N)) 19.41/6.04 U12(tt, M, N) -> s(plus(activate(N), activate(M))) 19.41/6.04 U21(tt, M, N) -> U22(tt, activate(M), activate(N)) 19.41/6.04 U22(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) 19.41/6.04 plus(N, 0') -> N 19.41/6.04 plus(N, s(M)) -> U11(tt, M, N) 19.41/6.04 x(N, 0') -> 0' 19.41/6.04 x(N, s(M)) -> U21(tt, M, N) 19.41/6.04 activate(X) -> X 19.41/6.04 19.41/6.04 Types: 19.41/6.04 U11 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 tt :: tt 19.41/6.04 U12 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 activate :: s:0' -> s:0' 19.41/6.04 s :: s:0' -> s:0' 19.41/6.04 plus :: s:0' -> s:0' -> s:0' 19.41/6.04 U21 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 U22 :: tt -> s:0' -> s:0' -> s:0' 19.41/6.04 x :: s:0' -> s:0' -> s:0' 19.41/6.04 0' :: s:0' 19.41/6.04 hole_s:0'1_0 :: s:0' 19.41/6.04 hole_tt2_0 :: tt 19.41/6.04 gen_s:0'3_0 :: Nat -> s:0' 19.41/6.04 19.41/6.04 19.41/6.04 Lemmas: 19.41/6.04 plus(gen_s:0'3_0(a), gen_s:0'3_0(n5_0)) -> gen_s:0'3_0(+(n5_0, a)), rt in Omega(1 + n5_0) 19.41/6.04 19.41/6.04 19.41/6.04 Generator Equations: 19.41/6.04 gen_s:0'3_0(0) <=> 0' 19.41/6.04 gen_s:0'3_0(+(x, 1)) <=> s(gen_s:0'3_0(x)) 19.41/6.04 19.41/6.04 19.41/6.04 The following defined symbols remain to be analysed: 19.41/6.04 x 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (25) LowerBoundPropagationProof (FINISHED) 19.41/6.04 Propagated lower bound. 19.41/6.04 ---------------------------------------- 19.41/6.04 19.41/6.04 (26) 19.41/6.04 BOUNDS(n^2, INF) 24.08/8.74 EOF