884.20/291.46 WORST_CASE(Omega(n^1), O(n^1)) 884.20/291.47 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 884.20/291.47 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 884.20/291.47 884.20/291.47 884.20/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 884.20/291.47 884.20/291.47 (0) CpxTRS 884.20/291.47 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 884.20/291.47 (2) CpxTRS 884.20/291.47 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 884.20/291.47 (4) CpxWeightedTrs 884.20/291.47 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 884.20/291.47 (6) CpxTypedWeightedTrs 884.20/291.47 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 884.20/291.47 (8) CpxTypedWeightedCompleteTrs 884.20/291.47 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 2 ms] 884.20/291.47 (10) CpxRNTS 884.20/291.47 (11) CompleteCoflocoProof [FINISHED, 216 ms] 884.20/291.47 (12) BOUNDS(1, n^1) 884.20/291.47 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 884.20/291.47 (14) CpxTRS 884.20/291.47 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 884.20/291.47 (16) typed CpxTrs 884.20/291.47 (17) OrderProof [LOWER BOUND(ID), 0 ms] 884.20/291.47 (18) typed CpxTrs 884.20/291.47 (19) RewriteLemmaProof [LOWER BOUND(ID), 270 ms] 884.20/291.47 (20) BEST 884.20/291.47 (21) proven lower bound 884.20/291.47 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 884.20/291.47 (23) BOUNDS(n^1, INF) 884.20/291.47 (24) typed CpxTrs 884.20/291.47 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (0) 884.20/291.47 Obligation: 884.20/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 884.20/291.47 884.20/291.47 884.20/291.47 The TRS R consists of the following rules: 884.20/291.47 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0, x) -> false 884.20/291.47 gr(s(x), 0) -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 S is empty. 884.20/291.47 Rewrite Strategy: FULL 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 884.20/291.47 Converted rc-obligation to irc-obligation. 884.20/291.47 884.20/291.47 The duplicating contexts are: 884.20/291.47 cond(true, [], y) 884.20/291.47 cond(true, x, []) 884.20/291.47 884.20/291.47 884.20/291.47 The defined contexts are: 884.20/291.47 cond([], x1, x2) 884.20/291.47 884.20/291.47 884.20/291.47 [] just represents basic- or constructor-terms in the following defined contexts: 884.20/291.47 cond([], x1, x2) 884.20/291.47 884.20/291.47 884.20/291.47 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (2) 884.20/291.47 Obligation: 884.20/291.47 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 884.20/291.47 884.20/291.47 884.20/291.47 The TRS R consists of the following rules: 884.20/291.47 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0, x) -> false 884.20/291.47 gr(s(x), 0) -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 S is empty. 884.20/291.47 Rewrite Strategy: INNERMOST 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 884.20/291.47 Transformed relative TRS to weighted TRS 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (4) 884.20/291.47 Obligation: 884.20/291.47 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 884.20/291.47 884.20/291.47 884.20/291.47 The TRS R consists of the following rules: 884.20/291.47 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) [1] 884.20/291.47 gr(0, x) -> false [1] 884.20/291.47 gr(s(x), 0) -> true [1] 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) [1] 884.20/291.47 884.20/291.47 Rewrite Strategy: INNERMOST 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 884.20/291.47 Infered types. 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (6) 884.20/291.47 Obligation: 884.20/291.47 Runtime Complexity Weighted TRS with Types. 884.20/291.47 The TRS R consists of the following rules: 884.20/291.47 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) [1] 884.20/291.47 gr(0, x) -> false [1] 884.20/291.47 gr(s(x), 0) -> true [1] 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) [1] 884.20/291.47 884.20/291.47 The TRS has the following type information: 884.20/291.47 cond :: true:false -> 0:s -> 0:s -> cond 884.20/291.47 true :: true:false 884.20/291.47 gr :: 0:s -> 0:s -> true:false 884.20/291.47 0 :: 0:s 884.20/291.47 false :: true:false 884.20/291.47 s :: 0:s -> 0:s 884.20/291.47 884.20/291.47 Rewrite Strategy: INNERMOST 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (7) CompletionProof (UPPER BOUND(ID)) 884.20/291.47 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 884.20/291.47 884.20/291.47 cond(v0, v1, v2) -> null_cond [0] 884.20/291.47 884.20/291.47 And the following fresh constants: null_cond 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (8) 884.20/291.47 Obligation: 884.20/291.47 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 884.20/291.47 884.20/291.47 Runtime Complexity Weighted TRS with Types. 884.20/291.47 The TRS R consists of the following rules: 884.20/291.47 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) [1] 884.20/291.47 gr(0, x) -> false [1] 884.20/291.47 gr(s(x), 0) -> true [1] 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) [1] 884.20/291.47 cond(v0, v1, v2) -> null_cond [0] 884.20/291.47 884.20/291.47 The TRS has the following type information: 884.20/291.47 cond :: true:false -> 0:s -> 0:s -> null_cond 884.20/291.47 true :: true:false 884.20/291.47 gr :: 0:s -> 0:s -> true:false 884.20/291.47 0 :: 0:s 884.20/291.47 false :: true:false 884.20/291.47 s :: 0:s -> 0:s 884.20/291.47 null_cond :: null_cond 884.20/291.47 884.20/291.47 Rewrite Strategy: INNERMOST 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 884.20/291.47 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 884.20/291.47 The constant constructors are abstracted as follows: 884.20/291.47 884.20/291.47 true => 1 884.20/291.47 0 => 0 884.20/291.47 false => 0 884.20/291.47 null_cond => 0 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (10) 884.20/291.47 Obligation: 884.20/291.47 Complexity RNTS consisting of the following rules: 884.20/291.47 884.20/291.47 cond(z, z', z'') -{ 1 }-> cond(gr(x, y), y, x) :|: z' = x, z'' = y, z = 1, x >= 0, y >= 0 884.20/291.47 cond(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 884.20/291.47 gr(z, z') -{ 1 }-> gr(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 884.20/291.47 gr(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0 884.20/291.47 gr(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = 0 884.20/291.47 884.20/291.47 Only complete derivations are relevant for the runtime complexity. 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (11) CompleteCoflocoProof (FINISHED) 884.20/291.47 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 884.20/291.47 884.20/291.47 eq(start(V1, V, V2),0,[cond(V1, V, V2, Out)],[V1 >= 0,V >= 0,V2 >= 0]). 884.20/291.47 eq(start(V1, V, V2),0,[gr(V1, V, Out)],[V1 >= 0,V >= 0]). 884.20/291.47 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]). 884.20/291.47 eq(gr(V1, V, Out),1,[],[Out = 0,V = V5,V5 >= 0,V1 = 0]). 884.20/291.47 eq(gr(V1, V, Out),1,[],[Out = 1,V6 >= 0,V1 = 1 + V6,V = 0]). 884.20/291.47 eq(gr(V1, V, Out),1,[gr(V7, V8, Ret1)],[Out = Ret1,V = 1 + V8,V7 >= 0,V8 >= 0,V1 = 1 + V7]). 884.20/291.47 eq(cond(V1, V, V2, Out),0,[],[Out = 0,V10 >= 0,V2 = V11,V9 >= 0,V1 = V10,V = V9,V11 >= 0]). 884.20/291.47 input_output_vars(cond(V1,V,V2,Out),[V1,V,V2],[Out]). 884.20/291.47 input_output_vars(gr(V1,V,Out),[V1,V],[Out]). 884.20/291.47 884.20/291.47 884.20/291.47 CoFloCo proof output: 884.20/291.47 Preprocessing Cost Relations 884.20/291.47 ===================================== 884.20/291.47 884.20/291.47 #### Computed strongly connected components 884.20/291.47 0. recursive : [gr/3] 884.20/291.47 1. recursive : [cond/4] 884.20/291.47 2. non_recursive : [start/3] 884.20/291.47 884.20/291.47 #### Obtained direct recursion through partial evaluation 884.20/291.47 0. SCC is partially evaluated into gr/3 884.20/291.47 1. SCC is partially evaluated into cond/4 884.20/291.47 2. SCC is partially evaluated into start/3 884.20/291.47 884.20/291.47 Control-Flow Refinement of Cost Relations 884.20/291.47 ===================================== 884.20/291.47 884.20/291.47 ### Specialization of cost equations gr/3 884.20/291.47 * CE 7 is refined into CE [8] 884.20/291.47 * CE 6 is refined into CE [9] 884.20/291.47 * CE 5 is refined into CE [10] 884.20/291.47 884.20/291.47 884.20/291.47 ### Cost equations --> "Loop" of gr/3 884.20/291.47 * CEs [9] --> Loop 7 884.20/291.47 * CEs [10] --> Loop 8 884.20/291.47 * CEs [8] --> Loop 9 884.20/291.47 884.20/291.47 ### Ranking functions of CR gr(V1,V,Out) 884.20/291.47 * RF of phase [9]: [V,V1] 884.20/291.47 884.20/291.47 #### Partial ranking functions of CR gr(V1,V,Out) 884.20/291.47 * Partial RF of phase [9]: 884.20/291.47 - RF of loop [9:1]: 884.20/291.47 V 884.20/291.47 V1 884.20/291.47 884.20/291.47 884.20/291.47 ### Specialization of cost equations cond/4 884.20/291.47 * CE 4 is refined into CE [11] 884.20/291.47 * CE 3 is refined into CE [12,13,14,15] 884.20/291.47 884.20/291.47 884.20/291.47 ### Cost equations --> "Loop" of cond/4 884.20/291.47 * CEs [15] --> Loop 10 884.20/291.47 * CEs [14] --> Loop 11 884.20/291.47 * CEs [13] --> Loop 12 884.20/291.47 * CEs [12] --> Loop 13 884.20/291.47 * CEs [11] --> Loop 14 884.20/291.47 884.20/291.47 ### Ranking functions of CR cond(V1,V,V2,Out) 884.20/291.47 884.20/291.47 #### Partial ranking functions of CR cond(V1,V,V2,Out) 884.20/291.47 884.20/291.47 884.20/291.47 ### Specialization of cost equations start/3 884.20/291.47 * CE 1 is refined into CE [16,17,18,19] 884.20/291.47 * CE 2 is refined into CE [20,21,22,23] 884.20/291.47 884.20/291.47 884.20/291.47 ### Cost equations --> "Loop" of start/3 884.20/291.47 * CEs [23] --> Loop 15 884.20/291.47 * CEs [21] --> Loop 16 884.20/291.47 * CEs [19] --> Loop 17 884.20/291.47 * CEs [18,22] --> Loop 18 884.20/291.47 * CEs [16,17] --> Loop 19 884.20/291.47 * CEs [20] --> Loop 20 884.20/291.47 884.20/291.47 ### Ranking functions of CR start(V1,V,V2) 884.20/291.47 884.20/291.47 #### Partial ranking functions of CR start(V1,V,V2) 884.20/291.47 884.20/291.47 884.20/291.47 Computing Bounds 884.20/291.47 ===================================== 884.20/291.47 884.20/291.47 #### Cost of chains of gr(V1,V,Out): 884.20/291.47 * Chain [[9],8]: 1*it(9)+1 884.20/291.47 Such that:it(9) =< V1 884.20/291.47 884.20/291.47 with precondition: [Out=0,V1>=1,V>=V1] 884.20/291.47 884.20/291.47 * Chain [[9],7]: 1*it(9)+1 884.20/291.47 Such that:it(9) =< V 884.20/291.47 884.20/291.47 with precondition: [Out=1,V>=1,V1>=V+1] 884.20/291.47 884.20/291.47 * Chain [8]: 1 884.20/291.47 with precondition: [V1=0,Out=0,V>=0] 884.20/291.47 884.20/291.47 * Chain [7]: 1 884.20/291.47 with precondition: [V=0,Out=1,V1>=1] 884.20/291.47 884.20/291.47 884.20/291.47 #### Cost of chains of cond(V1,V,V2,Out): 884.20/291.47 * Chain [14]: 0 884.20/291.47 with precondition: [Out=0,V1>=0,V>=0,V2>=0] 884.20/291.47 884.20/291.47 * Chain [13,14]: 2 884.20/291.47 with precondition: [V1=1,V=0,Out=0,V2>=0] 884.20/291.47 884.20/291.47 * Chain [12,14]: 2 884.20/291.47 with precondition: [V1=1,V2=0,Out=0,V>=1] 884.20/291.47 884.20/291.47 * Chain [12,13,14]: 4 884.20/291.47 with precondition: [V1=1,V2=0,Out=0,V>=1] 884.20/291.47 884.20/291.47 * Chain [11,14]: 1*s(1)+2 884.20/291.47 Such that:s(1) =< V 884.20/291.47 884.20/291.47 with precondition: [V1=1,Out=0,V>=1,V2>=V] 884.20/291.47 884.20/291.47 * Chain [10,14]: 1*s(2)+2 884.20/291.47 Such that:s(2) =< V2 884.20/291.47 884.20/291.47 with precondition: [V1=1,Out=0,V2>=1,V>=V2+1] 884.20/291.47 884.20/291.47 * Chain [10,11,14]: 2*s(1)+4 884.20/291.47 Such that:aux(1) =< V2 884.20/291.47 s(1) =< aux(1) 884.20/291.47 884.20/291.47 with precondition: [V1=1,Out=0,V2>=1,V>=V2+1] 884.20/291.47 884.20/291.47 884.20/291.47 #### Cost of chains of start(V1,V,V2): 884.20/291.47 * Chain [20]: 1 884.20/291.47 with precondition: [V1=0,V>=0] 884.20/291.47 884.20/291.47 * Chain [19]: 4 884.20/291.47 with precondition: [V1>=0,V>=0,V2>=0] 884.20/291.47 884.20/291.47 * Chain [18]: 1*s(6)+1*s(7)+2 884.20/291.47 Such that:s(7) =< V1 884.20/291.47 s(6) =< V 884.20/291.47 884.20/291.47 with precondition: [V1>=1,V>=V1] 884.20/291.47 884.20/291.47 * Chain [17]: 3*s(9)+4 884.20/291.47 Such that:s(8) =< V2 884.20/291.47 s(9) =< s(8) 884.20/291.47 884.20/291.47 with precondition: [V1=1,V2>=1,V>=V2+1] 884.20/291.47 884.20/291.47 * Chain [16]: 1 884.20/291.47 with precondition: [V=0,V1>=1] 884.20/291.47 884.20/291.47 * Chain [15]: 1*s(10)+1 884.20/291.47 Such that:s(10) =< V 884.20/291.47 884.20/291.47 with precondition: [V>=1,V1>=V+1] 884.20/291.47 884.20/291.47 884.20/291.47 Closed-form bounds of start(V1,V,V2): 884.20/291.47 ------------------------------------- 884.20/291.47 * Chain [20] with precondition: [V1=0,V>=0] 884.20/291.47 - Upper bound: 1 884.20/291.47 - Complexity: constant 884.20/291.47 * Chain [19] with precondition: [V1>=0,V>=0,V2>=0] 884.20/291.47 - Upper bound: 4 884.20/291.47 - Complexity: constant 884.20/291.47 * Chain [18] with precondition: [V1>=1,V>=V1] 884.20/291.47 - Upper bound: V1+V+2 884.20/291.47 - Complexity: n 884.20/291.47 * Chain [17] with precondition: [V1=1,V2>=1,V>=V2+1] 884.20/291.47 - Upper bound: 3*V2+4 884.20/291.47 - Complexity: n 884.20/291.47 * Chain [16] with precondition: [V=0,V1>=1] 884.20/291.47 - Upper bound: 1 884.20/291.47 - Complexity: constant 884.20/291.47 * Chain [15] with precondition: [V>=1,V1>=V+1] 884.20/291.47 - Upper bound: V+1 884.20/291.47 - Complexity: n 884.20/291.47 884.20/291.47 ### Maximum cost of start(V1,V,V2): max([V1+V+1,max([3,nat(V2)*3+3])])+1 884.20/291.47 Asymptotic class: n 884.20/291.47 * Total analysis performed in 159 ms. 884.20/291.47 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (12) 884.20/291.47 BOUNDS(1, n^1) 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 884.20/291.47 Renamed function symbols to avoid clashes with predefined symbol. 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (14) 884.20/291.47 Obligation: 884.20/291.47 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 884.20/291.47 884.20/291.47 884.20/291.47 The TRS R consists of the following rules: 884.20/291.47 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0', x) -> false 884.20/291.47 gr(s(x), 0') -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 S is empty. 884.20/291.47 Rewrite Strategy: FULL 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 884.20/291.47 Infered types. 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (16) 884.20/291.47 Obligation: 884.20/291.47 TRS: 884.20/291.47 Rules: 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0', x) -> false 884.20/291.47 gr(s(x), 0') -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 Types: 884.20/291.47 cond :: true:false -> 0':s -> 0':s -> cond 884.20/291.47 true :: true:false 884.20/291.47 gr :: 0':s -> 0':s -> true:false 884.20/291.47 0' :: 0':s 884.20/291.47 false :: true:false 884.20/291.47 s :: 0':s -> 0':s 884.20/291.47 hole_cond1_0 :: cond 884.20/291.47 hole_true:false2_0 :: true:false 884.20/291.47 hole_0':s3_0 :: 0':s 884.20/291.47 gen_0':s4_0 :: Nat -> 0':s 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (17) OrderProof (LOWER BOUND(ID)) 884.20/291.47 Heuristically decided to analyse the following defined symbols: 884.20/291.47 cond, gr 884.20/291.47 884.20/291.47 They will be analysed ascendingly in the following order: 884.20/291.47 gr < cond 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (18) 884.20/291.47 Obligation: 884.20/291.47 TRS: 884.20/291.47 Rules: 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0', x) -> false 884.20/291.47 gr(s(x), 0') -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 Types: 884.20/291.47 cond :: true:false -> 0':s -> 0':s -> cond 884.20/291.47 true :: true:false 884.20/291.47 gr :: 0':s -> 0':s -> true:false 884.20/291.47 0' :: 0':s 884.20/291.47 false :: true:false 884.20/291.47 s :: 0':s -> 0':s 884.20/291.47 hole_cond1_0 :: cond 884.20/291.47 hole_true:false2_0 :: true:false 884.20/291.47 hole_0':s3_0 :: 0':s 884.20/291.47 gen_0':s4_0 :: Nat -> 0':s 884.20/291.47 884.20/291.47 884.20/291.47 Generator Equations: 884.20/291.47 gen_0':s4_0(0) <=> 0' 884.20/291.47 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 884.20/291.47 884.20/291.47 884.20/291.47 The following defined symbols remain to be analysed: 884.20/291.47 gr, cond 884.20/291.47 884.20/291.47 They will be analysed ascendingly in the following order: 884.20/291.47 gr < cond 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (19) RewriteLemmaProof (LOWER BOUND(ID)) 884.20/291.47 Proved the following rewrite lemma: 884.20/291.47 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 884.20/291.47 884.20/291.47 Induction Base: 884.20/291.47 gr(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 884.20/291.47 false 884.20/291.47 884.20/291.47 Induction Step: 884.20/291.47 gr(gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1) 884.20/291.47 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) ->_IH 884.20/291.47 false 884.20/291.47 884.20/291.47 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (20) 884.20/291.47 Complex Obligation (BEST) 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (21) 884.20/291.47 Obligation: 884.20/291.47 Proved the lower bound n^1 for the following obligation: 884.20/291.47 884.20/291.47 TRS: 884.20/291.47 Rules: 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0', x) -> false 884.20/291.47 gr(s(x), 0') -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 Types: 884.20/291.47 cond :: true:false -> 0':s -> 0':s -> cond 884.20/291.47 true :: true:false 884.20/291.47 gr :: 0':s -> 0':s -> true:false 884.20/291.47 0' :: 0':s 884.20/291.47 false :: true:false 884.20/291.47 s :: 0':s -> 0':s 884.20/291.47 hole_cond1_0 :: cond 884.20/291.47 hole_true:false2_0 :: true:false 884.20/291.47 hole_0':s3_0 :: 0':s 884.20/291.47 gen_0':s4_0 :: Nat -> 0':s 884.20/291.47 884.20/291.47 884.20/291.47 Generator Equations: 884.20/291.47 gen_0':s4_0(0) <=> 0' 884.20/291.47 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 884.20/291.47 884.20/291.47 884.20/291.47 The following defined symbols remain to be analysed: 884.20/291.47 gr, cond 884.20/291.47 884.20/291.47 They will be analysed ascendingly in the following order: 884.20/291.47 gr < cond 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (22) LowerBoundPropagationProof (FINISHED) 884.20/291.47 Propagated lower bound. 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (23) 884.20/291.47 BOUNDS(n^1, INF) 884.20/291.47 884.20/291.47 ---------------------------------------- 884.20/291.47 884.20/291.47 (24) 884.20/291.47 Obligation: 884.20/291.47 TRS: 884.20/291.47 Rules: 884.20/291.47 cond(true, x, y) -> cond(gr(x, y), y, x) 884.20/291.47 gr(0', x) -> false 884.20/291.47 gr(s(x), 0') -> true 884.20/291.47 gr(s(x), s(y)) -> gr(x, y) 884.20/291.47 884.20/291.47 Types: 884.20/291.47 cond :: true:false -> 0':s -> 0':s -> cond 884.20/291.47 true :: true:false 884.20/291.47 gr :: 0':s -> 0':s -> true:false 884.20/291.47 0' :: 0':s 884.20/291.47 false :: true:false 884.20/291.47 s :: 0':s -> 0':s 884.20/291.47 hole_cond1_0 :: cond 884.20/291.47 hole_true:false2_0 :: true:false 884.20/291.47 hole_0':s3_0 :: 0':s 884.20/291.47 gen_0':s4_0 :: Nat -> 0':s 884.20/291.47 884.20/291.47 884.20/291.47 Lemmas: 884.20/291.47 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 884.20/291.47 884.20/291.47 884.20/291.47 Generator Equations: 884.20/291.47 gen_0':s4_0(0) <=> 0' 884.20/291.47 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 884.20/291.47 884.20/291.47 884.20/291.47 The following defined symbols remain to be analysed: 884.20/291.47 cond 884.43/291.52 EOF