46.14/13.83 WORST_CASE(Omega(n^1), O(n^1)) 46.46/13.85 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 46.46/13.85 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 46.46/13.85 46.46/13.85 46.46/13.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 46.46/13.85 46.46/13.85 (0) CpxTRS 46.46/13.85 (1) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] 46.46/13.85 (2) CpxTRS 46.46/13.85 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 46.46/13.85 (4) CpxWeightedTrs 46.46/13.85 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 2 ms] 46.46/13.85 (6) CpxTypedWeightedTrs 46.46/13.85 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 46.46/13.85 (8) CpxTypedWeightedCompleteTrs 46.46/13.85 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 46.46/13.85 (10) CpxRNTS 46.46/13.85 (11) CompleteCoflocoProof [FINISHED, 504 ms] 46.46/13.85 (12) BOUNDS(1, n^1) 46.46/13.85 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 46.46/13.85 (14) CpxTRS 46.46/13.85 (15) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 46.46/13.85 (16) typed CpxTrs 46.46/13.85 (17) OrderProof [LOWER BOUND(ID), 0 ms] 46.46/13.85 (18) typed CpxTrs 46.46/13.85 (19) RewriteLemmaProof [LOWER BOUND(ID), 298 ms] 46.46/13.85 (20) BEST 46.46/13.85 (21) proven lower bound 46.46/13.85 (22) LowerBoundPropagationProof [FINISHED, 0 ms] 46.46/13.85 (23) BOUNDS(n^1, INF) 46.46/13.85 (24) typed CpxTrs 46.46/13.85 (25) RewriteLemmaProof [LOWER BOUND(ID), 84 ms] 46.46/13.85 (26) typed CpxTrs 46.46/13.85 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (0) 46.46/13.85 Obligation: 46.46/13.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 46.46/13.85 46.46/13.85 46.46/13.85 The TRS R consists of the following rules: 46.46/13.85 46.46/13.85 le(0, y) -> true 46.46/13.85 le(s(x), 0) -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0) -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0, y) -> 0 46.46/13.85 mod(s(x), 0) -> 0 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 S is empty. 46.46/13.85 Rewrite Strategy: FULL 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (1) RcToIrcProof (BOTH BOUNDS(ID, ID)) 46.46/13.85 Converted rc-obligation to irc-obligation. 46.46/13.85 46.46/13.85 The duplicating contexts are: 46.46/13.85 mod(s(x), s([])) 46.46/13.85 mod(s([]), s(y)) 46.46/13.85 if_mod(true, x, []) 46.46/13.85 46.46/13.85 46.46/13.85 The defined contexts are: 46.46/13.85 if_mod([], s(x1), s(x2)) 46.46/13.85 mod([], x1) 46.46/13.85 le(x0, []) 46.46/13.85 if_mod(x0, s([]), s(x2)) 46.46/13.85 minus([], x1) 46.46/13.85 46.46/13.85 46.46/13.85 [] just represents basic- or constructor-terms in the following defined contexts: 46.46/13.85 if_mod([], s(x1), s(x2)) 46.46/13.85 mod([], x1) 46.46/13.85 46.46/13.85 46.46/13.85 As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (2) 46.46/13.85 Obligation: 46.46/13.85 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 46.46/13.85 46.46/13.85 46.46/13.85 The TRS R consists of the following rules: 46.46/13.85 46.46/13.85 le(0, y) -> true 46.46/13.85 le(s(x), 0) -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0) -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0, y) -> 0 46.46/13.85 mod(s(x), 0) -> 0 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 S is empty. 46.46/13.85 Rewrite Strategy: INNERMOST 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 46.46/13.85 Transformed relative TRS to weighted TRS 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (4) 46.46/13.85 Obligation: 46.46/13.85 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 46.46/13.85 46.46/13.85 46.46/13.85 The TRS R consists of the following rules: 46.46/13.85 46.46/13.85 le(0, y) -> true [1] 46.46/13.85 le(s(x), 0) -> false [1] 46.46/13.85 le(s(x), s(y)) -> le(x, y) [1] 46.46/13.85 minus(x, 0) -> x [1] 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) [1] 46.46/13.85 mod(0, y) -> 0 [1] 46.46/13.85 mod(s(x), 0) -> 0 [1] 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) [1] 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) [1] 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) [1] 46.46/13.85 46.46/13.85 Rewrite Strategy: INNERMOST 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 46.46/13.85 Infered types. 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (6) 46.46/13.85 Obligation: 46.46/13.85 Runtime Complexity Weighted TRS with Types. 46.46/13.85 The TRS R consists of the following rules: 46.46/13.85 46.46/13.85 le(0, y) -> true [1] 46.46/13.85 le(s(x), 0) -> false [1] 46.46/13.85 le(s(x), s(y)) -> le(x, y) [1] 46.46/13.85 minus(x, 0) -> x [1] 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) [1] 46.46/13.85 mod(0, y) -> 0 [1] 46.46/13.85 mod(s(x), 0) -> 0 [1] 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) [1] 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) [1] 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) [1] 46.46/13.85 46.46/13.85 The TRS has the following type information: 46.46/13.85 le :: 0:s -> 0:s -> true:false 46.46/13.85 0 :: 0:s 46.46/13.85 true :: true:false 46.46/13.85 s :: 0:s -> 0:s 46.46/13.85 false :: true:false 46.46/13.85 minus :: 0:s -> 0:s -> 0:s 46.46/13.85 mod :: 0:s -> 0:s -> 0:s 46.46/13.85 if_mod :: true:false -> 0:s -> 0:s -> 0:s 46.46/13.85 46.46/13.85 Rewrite Strategy: INNERMOST 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (7) CompletionProof (UPPER BOUND(ID)) 46.46/13.85 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 46.46/13.85 46.46/13.85 minus(v0, v1) -> null_minus [0] 46.46/13.85 if_mod(v0, v1, v2) -> null_if_mod [0] 46.46/13.85 le(v0, v1) -> null_le [0] 46.46/13.85 mod(v0, v1) -> null_mod [0] 46.46/13.85 46.46/13.85 And the following fresh constants: null_minus, null_if_mod, null_le, null_mod 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (8) 46.46/13.85 Obligation: 46.46/13.85 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 46.46/13.85 46.46/13.85 Runtime Complexity Weighted TRS with Types. 46.46/13.85 The TRS R consists of the following rules: 46.46/13.85 46.46/13.85 le(0, y) -> true [1] 46.46/13.85 le(s(x), 0) -> false [1] 46.46/13.85 le(s(x), s(y)) -> le(x, y) [1] 46.46/13.85 minus(x, 0) -> x [1] 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) [1] 46.46/13.85 mod(0, y) -> 0 [1] 46.46/13.85 mod(s(x), 0) -> 0 [1] 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) [1] 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) [1] 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) [1] 46.46/13.85 minus(v0, v1) -> null_minus [0] 46.46/13.85 if_mod(v0, v1, v2) -> null_if_mod [0] 46.46/13.85 le(v0, v1) -> null_le [0] 46.46/13.85 mod(v0, v1) -> null_mod [0] 46.46/13.85 46.46/13.85 The TRS has the following type information: 46.46/13.85 le :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> true:false:null_le 46.46/13.85 0 :: 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 true :: true:false:null_le 46.46/13.85 s :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 false :: true:false:null_le 46.46/13.85 minus :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 mod :: 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 if_mod :: true:false:null_le -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod -> 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 null_minus :: 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 null_if_mod :: 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 null_le :: true:false:null_le 46.46/13.85 null_mod :: 0:s:null_minus:null_if_mod:null_mod 46.46/13.85 46.46/13.85 Rewrite Strategy: INNERMOST 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 46.46/13.85 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 46.46/13.85 The constant constructors are abstracted as follows: 46.46/13.85 46.46/13.85 0 => 0 46.46/13.85 true => 2 46.46/13.85 false => 1 46.46/13.85 null_minus => 0 46.46/13.85 null_if_mod => 0 46.46/13.85 null_le => 0 46.46/13.85 null_mod => 0 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (10) 46.46/13.85 Obligation: 46.46/13.85 Complexity RNTS consisting of the following rules: 46.46/13.85 46.46/13.85 if_mod(z, z', z'') -{ 1 }-> mod(minus(x, y), y) :|: z = 2, z' = x, z'' = y, x >= 0, y >= 0 46.46/13.85 if_mod(z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 46.46/13.85 if_mod(z, z', z'') -{ 1 }-> 1 + x :|: z' = 1 + x, z = 1, x >= 0, y >= 0, z'' = 1 + y 46.46/13.85 le(z, z') -{ 1 }-> le(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 46.46/13.85 le(z, z') -{ 1 }-> 2 :|: y >= 0, z = 0, z' = y 46.46/13.85 le(z, z') -{ 1 }-> 1 :|: x >= 0, z = 1 + x, z' = 0 46.46/13.85 le(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 46.46/13.85 minus(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 46.46/13.85 minus(z, z') -{ 1 }-> minus(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 46.46/13.85 minus(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 46.46/13.85 mod(z, z') -{ 1 }-> if_mod(le(y, x), 1 + x, 1 + y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 46.46/13.85 mod(z, z') -{ 1 }-> 0 :|: y >= 0, z = 0, z' = y 46.46/13.85 mod(z, z') -{ 1 }-> 0 :|: x >= 0, z = 1 + x, z' = 0 46.46/13.85 mod(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 46.46/13.85 46.46/13.85 Only complete derivations are relevant for the runtime complexity. 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (11) CompleteCoflocoProof (FINISHED) 46.46/13.85 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 46.46/13.85 46.46/13.85 eq(start(V1, V, V14),0,[le(V1, V, Out)],[V1 >= 0,V >= 0]). 46.46/13.85 eq(start(V1, V, V14),0,[minus(V1, V, Out)],[V1 >= 0,V >= 0]). 46.46/13.85 eq(start(V1, V, V14),0,[mod(V1, V, Out)],[V1 >= 0,V >= 0]). 46.46/13.85 eq(start(V1, V, V14),0,[fun(V1, V, V14, Out)],[V1 >= 0,V >= 0,V14 >= 0]). 46.46/13.85 eq(le(V1, V, Out),1,[],[Out = 2,V2 >= 0,V1 = 0,V = V2]). 46.46/13.85 eq(le(V1, V, Out),1,[],[Out = 1,V3 >= 0,V1 = 1 + V3,V = 0]). 46.46/13.85 eq(le(V1, V, Out),1,[le(V4, V5, Ret)],[Out = Ret,V = 1 + V5,V4 >= 0,V5 >= 0,V1 = 1 + V4]). 46.46/13.85 eq(minus(V1, V, Out),1,[],[Out = V6,V6 >= 0,V1 = V6,V = 0]). 46.46/13.85 eq(minus(V1, V, Out),1,[minus(V7, V8, Ret1)],[Out = Ret1,V = 1 + V8,V7 >= 0,V8 >= 0,V1 = 1 + V7]). 46.46/13.85 eq(mod(V1, V, Out),1,[],[Out = 0,V9 >= 0,V1 = 0,V = V9]). 46.46/13.85 eq(mod(V1, V, Out),1,[],[Out = 0,V10 >= 0,V1 = 1 + V10,V = 0]). 46.46/13.85 eq(mod(V1, V, Out),1,[le(V11, V12, Ret0),fun(Ret0, 1 + V12, 1 + V11, Ret2)],[Out = Ret2,V = 1 + V11,V12 >= 0,V11 >= 0,V1 = 1 + V12]). 46.46/13.85 eq(fun(V1, V, V14, Out),1,[minus(V15, V13, Ret01),mod(Ret01, V13, Ret3)],[Out = Ret3,V1 = 2,V = V15,V14 = V13,V15 >= 0,V13 >= 0]). 46.46/13.85 eq(fun(V1, V, V14, Out),1,[],[Out = 1 + V16,V = 1 + V16,V1 = 1,V16 >= 0,V17 >= 0,V14 = 1 + V17]). 46.46/13.85 eq(minus(V1, V, Out),0,[],[Out = 0,V19 >= 0,V18 >= 0,V1 = V19,V = V18]). 46.46/13.85 eq(fun(V1, V, V14, Out),0,[],[Out = 0,V21 >= 0,V14 = V22,V20 >= 0,V1 = V21,V = V20,V22 >= 0]). 46.46/13.85 eq(le(V1, V, Out),0,[],[Out = 0,V24 >= 0,V23 >= 0,V1 = V24,V = V23]). 46.46/13.85 eq(mod(V1, V, Out),0,[],[Out = 0,V25 >= 0,V26 >= 0,V1 = V25,V = V26]). 46.46/13.85 input_output_vars(le(V1,V,Out),[V1,V],[Out]). 46.46/13.85 input_output_vars(minus(V1,V,Out),[V1,V],[Out]). 46.46/13.85 input_output_vars(mod(V1,V,Out),[V1,V],[Out]). 46.46/13.85 input_output_vars(fun(V1,V,V14,Out),[V1,V,V14],[Out]). 46.46/13.85 46.46/13.85 46.46/13.85 CoFloCo proof output: 46.46/13.85 Preprocessing Cost Relations 46.46/13.85 ===================================== 46.46/13.85 46.46/13.85 #### Computed strongly connected components 46.46/13.85 0. recursive : [minus/3] 46.46/13.85 1. recursive : [le/3] 46.46/13.85 2. recursive : [fun/4,(mod)/3] 46.46/13.85 3. non_recursive : [start/3] 46.46/13.85 46.46/13.85 #### Obtained direct recursion through partial evaluation 46.46/13.85 0. SCC is partially evaluated into minus/3 46.46/13.85 1. SCC is partially evaluated into le/3 46.46/13.85 2. SCC is partially evaluated into (mod)/3 46.46/13.85 3. SCC is partially evaluated into start/3 46.46/13.85 46.46/13.85 Control-Flow Refinement of Cost Relations 46.46/13.85 ===================================== 46.46/13.85 46.46/13.85 ### Specialization of cost equations minus/3 46.46/13.85 * CE 9 is refined into CE [20] 46.46/13.85 * CE 7 is refined into CE [21] 46.46/13.85 * CE 8 is refined into CE [22] 46.46/13.85 46.46/13.85 46.46/13.85 ### Cost equations --> "Loop" of minus/3 46.46/13.85 * CEs [22] --> Loop 14 46.46/13.85 * CEs [20] --> Loop 15 46.46/13.85 * CEs [21] --> Loop 16 46.46/13.85 46.46/13.85 ### Ranking functions of CR minus(V1,V,Out) 46.46/13.85 * RF of phase [14]: [V,V1] 46.46/13.85 46.46/13.85 #### Partial ranking functions of CR minus(V1,V,Out) 46.46/13.85 * Partial RF of phase [14]: 46.46/13.85 - RF of loop [14:1]: 46.46/13.85 V 46.46/13.85 V1 46.46/13.85 46.46/13.85 46.46/13.85 ### Specialization of cost equations le/3 46.46/13.85 * CE 19 is refined into CE [23] 46.46/13.85 * CE 17 is refined into CE [24] 46.46/13.85 * CE 16 is refined into CE [25] 46.46/13.85 * CE 18 is refined into CE [26] 46.46/13.85 46.46/13.85 46.46/13.85 ### Cost equations --> "Loop" of le/3 46.46/13.85 * CEs [26] --> Loop 17 46.46/13.85 * CEs [23] --> Loop 18 46.46/13.85 * CEs [24] --> Loop 19 46.46/13.85 * CEs [25] --> Loop 20 46.46/13.85 46.46/13.85 ### Ranking functions of CR le(V1,V,Out) 46.46/13.85 * RF of phase [17]: [V,V1] 46.46/13.85 46.46/13.85 #### Partial ranking functions of CR le(V1,V,Out) 46.46/13.85 * Partial RF of phase [17]: 46.46/13.85 - RF of loop [17:1]: 46.46/13.85 V 46.46/13.85 V1 46.46/13.85 46.46/13.85 46.46/13.85 ### Specialization of cost equations (mod)/3 46.46/13.85 * CE 11 is refined into CE [27,28] 46.46/13.85 * CE 14 is refined into CE [29] 46.46/13.85 * CE 10 is refined into CE [30,31,32,33,34] 46.46/13.85 * CE 13 is refined into CE [35] 46.46/13.85 * CE 15 is refined into CE [36] 46.46/13.85 * CE 12 is refined into CE [37,38,39,40] 46.46/13.85 46.46/13.85 46.46/13.85 ### Cost equations --> "Loop" of (mod)/3 46.46/13.85 * CEs [40] --> Loop 21 46.46/13.85 * CEs [39] --> Loop 22 46.46/13.85 * CEs [38] --> Loop 23 46.46/13.85 * CEs [37] --> Loop 24 46.46/13.85 * CEs [28] --> Loop 25 46.46/13.85 * CEs [30] --> Loop 26 46.46/13.85 * CEs [29] --> Loop 27 46.46/13.85 * CEs [27] --> Loop 28 46.46/13.85 * CEs [31] --> Loop 29 46.46/13.85 * CEs [32,33,34,35,36] --> Loop 30 46.46/13.85 46.46/13.85 ### Ranking functions of CR mod(V1,V,Out) 46.46/13.85 * RF of phase [21]: [V1-1,V1-V+1] 46.46/13.85 * RF of phase [23]: [V1] 46.46/13.85 46.46/13.85 #### Partial ranking functions of CR mod(V1,V,Out) 46.46/13.85 * Partial RF of phase [21]: 46.46/13.85 - RF of loop [21:1]: 46.46/13.85 V1-1 46.46/13.85 V1-V+1 46.46/13.85 * Partial RF of phase [23]: 46.46/13.85 - RF of loop [23:1]: 46.46/13.85 V1 46.46/13.85 46.46/13.85 46.46/13.85 ### Specialization of cost equations start/3 46.46/13.85 * CE 3 is refined into CE [41,42,43,44,45,46,47,48,49] 46.46/13.85 * CE 1 is refined into CE [50] 46.46/13.85 * CE 2 is refined into CE [51] 46.46/13.85 * CE 4 is refined into CE [52,53,54,55,56] 46.46/13.85 * CE 5 is refined into CE [57,58,59] 46.46/13.85 * CE 6 is refined into CE [60,61,62,63,64,65,66] 46.46/13.85 46.46/13.85 46.46/13.85 ### Cost equations --> "Loop" of start/3 46.46/13.85 * CEs [63] --> Loop 31 46.46/13.85 * CEs [53,57,62] --> Loop 32 46.46/13.85 * CEs [45] --> Loop 33 46.46/13.85 * CEs [46] --> Loop 34 46.46/13.85 * CEs [41,42,43,44,47,48,49] --> Loop 35 46.46/13.85 * CEs [61] --> Loop 36 46.46/13.85 * CEs [51] --> Loop 37 46.46/13.85 * CEs [50,52,54,55,56,58,59,60,64,65,66] --> Loop 38 46.46/13.85 46.46/13.85 ### Ranking functions of CR start(V1,V,V14) 46.46/13.85 46.46/13.85 #### Partial ranking functions of CR start(V1,V,V14) 46.46/13.85 46.46/13.85 46.46/13.85 Computing Bounds 46.46/13.85 ===================================== 46.46/13.85 46.46/13.85 #### Cost of chains of minus(V1,V,Out): 46.46/13.85 * Chain [[14],16]: 1*it(14)+1 46.46/13.85 Such that:it(14) =< V 46.46/13.85 46.46/13.85 with precondition: [V1=Out+V,V>=1,V1>=V] 46.46/13.85 46.46/13.85 * Chain [[14],15]: 1*it(14)+0 46.46/13.85 Such that:it(14) =< V 46.46/13.85 46.46/13.85 with precondition: [Out=0,V1>=1,V>=1] 46.46/13.85 46.46/13.85 * Chain [16]: 1 46.46/13.85 with precondition: [V=0,V1=Out,V1>=0] 46.46/13.85 46.46/13.85 * Chain [15]: 0 46.46/13.85 with precondition: [Out=0,V1>=0,V>=0] 46.46/13.85 46.46/13.85 46.46/13.85 #### Cost of chains of le(V1,V,Out): 46.46/13.85 * Chain [[17],20]: 1*it(17)+1 46.46/13.85 Such that:it(17) =< V1 46.46/13.85 46.46/13.85 with precondition: [Out=2,V1>=1,V>=V1] 46.46/13.85 46.46/13.85 * Chain [[17],19]: 1*it(17)+1 46.46/13.85 Such that:it(17) =< V 46.46/13.85 46.46/13.85 with precondition: [Out=1,V>=1,V1>=V+1] 46.46/13.85 46.46/13.85 * Chain [[17],18]: 1*it(17)+0 46.46/13.85 Such that:it(17) =< V 46.46/13.85 46.46/13.85 with precondition: [Out=0,V1>=1,V>=1] 46.46/13.85 46.46/13.85 * Chain [20]: 1 46.46/13.85 with precondition: [V1=0,Out=2,V>=0] 46.46/13.85 46.46/13.85 * Chain [19]: 1 46.46/13.85 with precondition: [V=0,Out=1,V1>=1] 46.46/13.85 46.46/13.85 * Chain [18]: 0 46.46/13.85 with precondition: [Out=0,V1>=0,V>=0] 46.46/13.85 46.46/13.85 46.46/13.85 #### Cost of chains of mod(V1,V,Out): 46.46/13.85 * Chain [[23],30]: 7*it(23)+1*s(5)+2 46.46/13.85 Such that:s(5) =< 1 46.46/13.85 aux(5) =< V1 46.46/13.85 it(23) =< aux(5) 46.46/13.85 46.46/13.85 with precondition: [V=1,Out=0,V1>=1] 46.46/13.85 46.46/13.85 * Chain [[23],26]: 5*it(23)+2 46.46/13.85 Such that:aux(6) =< V1 46.46/13.85 it(23) =< aux(6) 46.46/13.85 46.46/13.85 with precondition: [V=1,Out=0,V1>=2] 46.46/13.85 46.46/13.85 * Chain [[23],24,30]: 5*it(23)+2*s(5)+5 46.46/13.85 Such that:aux(7) =< 1 46.46/13.85 aux(8) =< V1 46.46/13.85 s(5) =< aux(7) 46.46/13.85 it(23) =< aux(8) 46.46/13.85 46.46/13.85 with precondition: [V=1,Out=0,V1>=2] 46.46/13.85 46.46/13.85 * Chain [[21],30]: 8*it(21)+1*s(5)+2 46.46/13.85 Such that:s(5) =< V 46.46/13.85 aux(12) =< V1 46.46/13.85 it(21) =< aux(12) 46.46/13.85 46.46/13.85 with precondition: [Out=0,V>=2,V1>=V] 46.46/13.85 46.46/13.85 * Chain [[21],29]: 4*it(21)+2*s(14)+2 46.46/13.85 Such that:it(21) =< V1-V+1 46.46/13.85 aux(13) =< V1 46.46/13.85 it(21) =< aux(13) 46.46/13.85 s(14) =< aux(13) 46.46/13.85 46.46/13.85 with precondition: [Out=0,V>=2,V1>=V+1] 46.46/13.85 46.46/13.85 * Chain [[21],28]: 4*it(21)+2*s(14)+3 46.46/13.85 Such that:it(21) =< V1-V+1 46.46/13.85 aux(14) =< V1 46.46/13.85 it(21) =< aux(14) 46.46/13.85 s(14) =< aux(14) 46.46/13.85 46.46/13.85 with precondition: [Out=1,V>=2,V1>=V+1] 46.46/13.85 46.46/13.85 * Chain [[21],25]: 4*it(21)+2*s(14)+1*s(16)+3 46.46/13.85 Such that:aux(10) =< V1 46.46/13.85 it(21) =< V1-V+1 46.46/13.85 aux(11) =< V1-Out 46.46/13.85 s(16) =< Out 46.46/13.85 it(21) =< aux(10) 46.46/13.85 s(15) =< aux(10) 46.46/13.85 it(21) =< aux(11) 46.46/13.85 s(15) =< aux(11) 46.46/13.85 s(14) =< s(15) 46.46/13.85 46.46/13.85 with precondition: [Out>=2,V>=Out+1,V1>=Out+V] 46.46/13.85 46.46/13.85 * Chain [[21],22,30]: 4*it(21)+3*s(5)+2*s(14)+5 46.46/13.85 Such that:aux(10) =< V1 46.46/13.85 aux(16) =< V 46.46/13.85 aux(17) =< V1-V 46.46/13.85 it(21) =< aux(17) 46.46/13.85 s(5) =< aux(16) 46.46/13.85 it(21) =< aux(10) 46.46/13.85 s(15) =< aux(10) 46.46/13.85 s(15) =< aux(17) 46.46/13.85 s(14) =< s(15) 46.46/13.85 46.46/13.85 with precondition: [Out=0,V>=2,V1>=2*V] 46.46/13.85 46.46/13.85 * Chain [30]: 2*s(3)+1*s(5)+2 46.46/13.85 Such that:s(5) =< V 46.46/13.85 aux(1) =< V1 46.46/13.85 s(3) =< aux(1) 46.46/13.85 46.46/13.85 with precondition: [Out=0,V1>=0,V>=0] 46.46/13.85 46.46/13.85 * Chain [29]: 2 46.46/13.85 with precondition: [V1=1,Out=0,V>=2] 46.46/13.85 46.46/13.85 * Chain [28]: 3 46.46/13.85 with precondition: [V1=1,Out=1,V>=2] 46.46/13.85 46.46/13.85 * Chain [27]: 1 46.46/13.85 with precondition: [V=0,Out=0,V1>=1] 46.46/13.85 46.46/13.85 * Chain [26]: 2 46.46/13.85 with precondition: [V=1,Out=0,V1>=1] 46.46/13.85 46.46/13.85 * Chain [25]: 1*s(16)+3 46.46/13.85 Such that:s(16) =< V1 46.46/13.85 46.46/13.85 with precondition: [V1=Out,V1>=2,V>=V1+1] 46.46/13.85 46.46/13.85 * Chain [24,30]: 2*s(5)+5 46.46/13.85 Such that:aux(7) =< 1 46.46/13.85 s(5) =< aux(7) 46.46/13.85 46.46/13.85 with precondition: [V=1,Out=0,V1>=1] 46.46/13.85 46.46/13.85 * Chain [22,30]: 3*s(5)+5 46.46/13.85 Such that:aux(16) =< V 46.46/13.85 s(5) =< aux(16) 46.46/13.85 46.46/13.85 with precondition: [Out=0,V>=2,V1>=V] 46.46/13.85 46.46/13.85 46.46/13.85 #### Cost of chains of start(V1,V,V14): 46.46/13.85 * Chain [38]: 12*s(48)+19*s(50)+12*s(54)+4*s(58)+2*s(60)+5 46.46/13.85 Such that:s(53) =< V1-V 46.46/13.85 aux(23) =< V1 46.46/13.85 aux(24) =< V1-V+1 46.46/13.85 aux(25) =< V 46.46/13.85 s(50) =< aux(23) 46.46/13.85 s(54) =< aux(24) 46.46/13.85 s(48) =< aux(25) 46.46/13.85 s(58) =< s(53) 46.46/13.85 s(58) =< aux(23) 46.46/13.85 s(59) =< aux(23) 46.46/13.85 s(59) =< s(53) 46.46/13.85 s(60) =< s(59) 46.46/13.85 s(54) =< aux(23) 46.46/13.85 46.46/13.85 with precondition: [V1>=0,V>=0] 46.46/13.85 46.46/13.85 * Chain [37]: 1 46.46/13.85 with precondition: [V1=1,V>=1,V14>=1] 46.46/13.85 46.46/13.85 * Chain [36]: 3 46.46/13.85 with precondition: [V1=1,V>=2] 46.46/13.85 46.46/13.85 * Chain [35]: 4*s(73)+18*s(77)+21*s(81)+12*s(93)+4*s(97)+2*s(99)+18*s(100)+7 46.46/13.85 Such that:aux(26) =< V 46.46/13.85 s(73) =< V+1 46.46/13.85 s(92) =< V-2*V14 46.46/13.85 aux(30) =< V-2*V14+1 46.46/13.85 aux(31) =< V-V14 46.46/13.85 aux(32) =< V14 46.46/13.85 s(93) =< aux(30) 46.46/13.85 s(100) =< aux(31) 46.46/13.85 s(81) =< aux(32) 46.46/13.85 s(77) =< aux(26) 46.46/13.85 s(73) =< aux(26) 46.46/13.85 s(97) =< s(92) 46.46/13.85 s(97) =< aux(31) 46.46/13.85 s(98) =< aux(31) 46.46/13.85 s(98) =< s(92) 46.46/13.85 s(99) =< s(98) 46.46/13.85 s(93) =< aux(31) 46.46/13.85 46.46/13.85 with precondition: [V1=2,V>=0,V14>=0] 46.46/13.85 46.46/13.85 * Chain [34]: 6*s(114)+17*s(118)+7 46.46/13.85 Such that:s(116) =< V 46.46/13.85 aux(33) =< 1 46.46/13.85 s(114) =< aux(33) 46.46/13.85 s(118) =< s(116) 46.46/13.85 46.46/13.85 with precondition: [V1=2,V14=1,V>=2] 46.46/13.85 46.46/13.85 * Chain [33]: 1*s(119)+5 46.46/13.85 Such that:s(119) =< V14 46.46/13.85 46.46/13.85 with precondition: [V1=2,V=V14+1,V>=3] 46.46/13.85 46.46/13.85 * Chain [32]: 1 46.46/13.85 with precondition: [V=0,V1>=0] 46.46/13.85 46.46/13.85 * Chain [31]: 5*s(122)+17*s(123)+5 46.46/13.85 Such that:s(120) =< 1 46.46/13.85 s(121) =< V1 46.46/13.85 s(122) =< s(120) 46.46/13.85 s(123) =< s(121) 46.46/13.85 46.46/13.85 with precondition: [V=1,V1>=1] 46.46/13.85 46.46/13.85 46.46/13.85 Closed-form bounds of start(V1,V,V14): 46.46/13.85 ------------------------------------- 46.46/13.85 * Chain [38] with precondition: [V1>=0,V>=0] 46.46/13.85 - Upper bound: 21*V1+12*V+5+nat(V1-V+1)*12+nat(V1-V)*4 46.46/13.85 - Complexity: n 46.46/13.85 * Chain [37] with precondition: [V1=1,V>=1,V14>=1] 46.46/13.85 - Upper bound: 1 46.46/13.85 - Complexity: constant 46.46/13.85 * Chain [36] with precondition: [V1=1,V>=2] 46.46/13.85 - Upper bound: 3 46.46/13.85 - Complexity: constant 46.46/13.85 * Chain [35] with precondition: [V1=2,V>=0,V14>=0] 46.46/13.85 - Upper bound: 22*V+21*V14+11+nat(V-2*V14+1)*12+nat(V-V14)*20+nat(V-2*V14)*4 46.46/13.85 - Complexity: n 46.46/13.85 * Chain [34] with precondition: [V1=2,V14=1,V>=2] 46.46/13.85 - Upper bound: 17*V+13 46.46/13.85 - Complexity: n 46.46/13.85 * Chain [33] with precondition: [V1=2,V=V14+1,V>=3] 46.46/13.85 - Upper bound: V14+5 46.46/13.85 - Complexity: n 46.46/13.85 * Chain [32] with precondition: [V=0,V1>=0] 46.46/13.85 - Upper bound: 1 46.46/13.85 - Complexity: constant 46.46/13.85 * Chain [31] with precondition: [V=1,V1>=1] 46.46/13.85 - Upper bound: 17*V1+10 46.46/13.85 - Complexity: n 46.46/13.85 46.46/13.85 ### Maximum cost of start(V1,V,V14): max([max([17*V1+9,nat(V14)+4]),12*V+4+max([5*V+2+max([6,nat(V14)*21+V+(4*V+4)+nat(V-2*V14+1)*12+nat(V-V14)*20+nat(V-2*V14)*4]),nat(V1-V+1)*12+21*V1+nat(V1-V)*4])])+1 46.46/13.85 Asymptotic class: n 46.46/13.85 * Total analysis performed in 413 ms. 46.46/13.85 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (12) 46.46/13.85 BOUNDS(1, n^1) 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 46.46/13.85 Renamed function symbols to avoid clashes with predefined symbol. 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (14) 46.46/13.85 Obligation: 46.46/13.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 46.46/13.85 46.46/13.85 46.46/13.85 The TRS R consists of the following rules: 46.46/13.85 46.46/13.85 le(0', y) -> true 46.46/13.85 le(s(x), 0') -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0') -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0', y) -> 0' 46.46/13.85 mod(s(x), 0') -> 0' 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 S is empty. 46.46/13.85 Rewrite Strategy: FULL 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (15) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 46.46/13.85 Infered types. 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (16) 46.46/13.85 Obligation: 46.46/13.85 TRS: 46.46/13.85 Rules: 46.46/13.85 le(0', y) -> true 46.46/13.85 le(s(x), 0') -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0') -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0', y) -> 0' 46.46/13.85 mod(s(x), 0') -> 0' 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 Types: 46.46/13.85 le :: 0':s -> 0':s -> true:false 46.46/13.85 0' :: 0':s 46.46/13.85 true :: true:false 46.46/13.85 s :: 0':s -> 0':s 46.46/13.85 false :: true:false 46.46/13.85 minus :: 0':s -> 0':s -> 0':s 46.46/13.85 mod :: 0':s -> 0':s -> 0':s 46.46/13.85 if_mod :: true:false -> 0':s -> 0':s -> 0':s 46.46/13.85 hole_true:false1_0 :: true:false 46.46/13.85 hole_0':s2_0 :: 0':s 46.46/13.85 gen_0':s3_0 :: Nat -> 0':s 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (17) OrderProof (LOWER BOUND(ID)) 46.46/13.85 Heuristically decided to analyse the following defined symbols: 46.46/13.85 le, minus, mod 46.46/13.85 46.46/13.85 They will be analysed ascendingly in the following order: 46.46/13.85 le < mod 46.46/13.85 minus < mod 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (18) 46.46/13.85 Obligation: 46.46/13.85 TRS: 46.46/13.85 Rules: 46.46/13.85 le(0', y) -> true 46.46/13.85 le(s(x), 0') -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0') -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0', y) -> 0' 46.46/13.85 mod(s(x), 0') -> 0' 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 Types: 46.46/13.85 le :: 0':s -> 0':s -> true:false 46.46/13.85 0' :: 0':s 46.46/13.85 true :: true:false 46.46/13.85 s :: 0':s -> 0':s 46.46/13.85 false :: true:false 46.46/13.85 minus :: 0':s -> 0':s -> 0':s 46.46/13.85 mod :: 0':s -> 0':s -> 0':s 46.46/13.85 if_mod :: true:false -> 0':s -> 0':s -> 0':s 46.46/13.85 hole_true:false1_0 :: true:false 46.46/13.85 hole_0':s2_0 :: 0':s 46.46/13.85 gen_0':s3_0 :: Nat -> 0':s 46.46/13.85 46.46/13.85 46.46/13.85 Generator Equations: 46.46/13.85 gen_0':s3_0(0) <=> 0' 46.46/13.85 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 46.46/13.85 46.46/13.85 46.46/13.85 The following defined symbols remain to be analysed: 46.46/13.85 le, minus, mod 46.46/13.85 46.46/13.85 They will be analysed ascendingly in the following order: 46.46/13.85 le < mod 46.46/13.85 minus < mod 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (19) RewriteLemmaProof (LOWER BOUND(ID)) 46.46/13.85 Proved the following rewrite lemma: 46.46/13.85 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 46.46/13.85 46.46/13.85 Induction Base: 46.46/13.85 le(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 46.46/13.85 true 46.46/13.85 46.46/13.85 Induction Step: 46.46/13.85 le(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1) 46.46/13.85 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) ->_IH 46.46/13.85 true 46.46/13.85 46.46/13.85 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (20) 46.46/13.85 Complex Obligation (BEST) 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (21) 46.46/13.85 Obligation: 46.46/13.85 Proved the lower bound n^1 for the following obligation: 46.46/13.85 46.46/13.85 TRS: 46.46/13.85 Rules: 46.46/13.85 le(0', y) -> true 46.46/13.85 le(s(x), 0') -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0') -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0', y) -> 0' 46.46/13.85 mod(s(x), 0') -> 0' 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 Types: 46.46/13.85 le :: 0':s -> 0':s -> true:false 46.46/13.85 0' :: 0':s 46.46/13.85 true :: true:false 46.46/13.85 s :: 0':s -> 0':s 46.46/13.85 false :: true:false 46.46/13.85 minus :: 0':s -> 0':s -> 0':s 46.46/13.85 mod :: 0':s -> 0':s -> 0':s 46.46/13.85 if_mod :: true:false -> 0':s -> 0':s -> 0':s 46.46/13.85 hole_true:false1_0 :: true:false 46.46/13.85 hole_0':s2_0 :: 0':s 46.46/13.85 gen_0':s3_0 :: Nat -> 0':s 46.46/13.85 46.46/13.85 46.46/13.85 Generator Equations: 46.46/13.85 gen_0':s3_0(0) <=> 0' 46.46/13.85 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 46.46/13.85 46.46/13.85 46.46/13.85 The following defined symbols remain to be analysed: 46.46/13.85 le, minus, mod 46.46/13.85 46.46/13.85 They will be analysed ascendingly in the following order: 46.46/13.85 le < mod 46.46/13.85 minus < mod 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (22) LowerBoundPropagationProof (FINISHED) 46.46/13.85 Propagated lower bound. 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (23) 46.46/13.85 BOUNDS(n^1, INF) 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (24) 46.46/13.85 Obligation: 46.46/13.85 TRS: 46.46/13.85 Rules: 46.46/13.85 le(0', y) -> true 46.46/13.85 le(s(x), 0') -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0') -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0', y) -> 0' 46.46/13.85 mod(s(x), 0') -> 0' 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 Types: 46.46/13.85 le :: 0':s -> 0':s -> true:false 46.46/13.85 0' :: 0':s 46.46/13.85 true :: true:false 46.46/13.85 s :: 0':s -> 0':s 46.46/13.85 false :: true:false 46.46/13.85 minus :: 0':s -> 0':s -> 0':s 46.46/13.85 mod :: 0':s -> 0':s -> 0':s 46.46/13.85 if_mod :: true:false -> 0':s -> 0':s -> 0':s 46.46/13.85 hole_true:false1_0 :: true:false 46.46/13.85 hole_0':s2_0 :: 0':s 46.46/13.85 gen_0':s3_0 :: Nat -> 0':s 46.46/13.85 46.46/13.85 46.46/13.85 Lemmas: 46.46/13.85 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 46.46/13.85 46.46/13.85 46.46/13.85 Generator Equations: 46.46/13.85 gen_0':s3_0(0) <=> 0' 46.46/13.85 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 46.46/13.85 46.46/13.85 46.46/13.85 The following defined symbols remain to be analysed: 46.46/13.85 minus, mod 46.46/13.85 46.46/13.85 They will be analysed ascendingly in the following order: 46.46/13.85 minus < mod 46.46/13.85 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (25) RewriteLemmaProof (LOWER BOUND(ID)) 46.46/13.85 Proved the following rewrite lemma: 46.46/13.85 minus(gen_0':s3_0(n252_0), gen_0':s3_0(n252_0)) -> gen_0':s3_0(0), rt in Omega(1 + n252_0) 46.46/13.85 46.46/13.85 Induction Base: 46.46/13.85 minus(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 46.46/13.85 gen_0':s3_0(0) 46.46/13.85 46.46/13.85 Induction Step: 46.46/13.85 minus(gen_0':s3_0(+(n252_0, 1)), gen_0':s3_0(+(n252_0, 1))) ->_R^Omega(1) 46.46/13.85 minus(gen_0':s3_0(n252_0), gen_0':s3_0(n252_0)) ->_IH 46.46/13.85 gen_0':s3_0(0) 46.46/13.85 46.46/13.85 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 46.46/13.85 ---------------------------------------- 46.46/13.85 46.46/13.85 (26) 46.46/13.85 Obligation: 46.46/13.85 TRS: 46.46/13.85 Rules: 46.46/13.85 le(0', y) -> true 46.46/13.85 le(s(x), 0') -> false 46.46/13.85 le(s(x), s(y)) -> le(x, y) 46.46/13.85 minus(x, 0') -> x 46.46/13.85 minus(s(x), s(y)) -> minus(x, y) 46.46/13.85 mod(0', y) -> 0' 46.46/13.85 mod(s(x), 0') -> 0' 46.46/13.85 mod(s(x), s(y)) -> if_mod(le(y, x), s(x), s(y)) 46.46/13.85 if_mod(true, x, y) -> mod(minus(x, y), y) 46.46/13.85 if_mod(false, s(x), s(y)) -> s(x) 46.46/13.85 46.46/13.85 Types: 46.46/13.85 le :: 0':s -> 0':s -> true:false 46.46/13.85 0' :: 0':s 46.46/13.85 true :: true:false 46.46/13.85 s :: 0':s -> 0':s 46.46/13.85 false :: true:false 46.46/13.85 minus :: 0':s -> 0':s -> 0':s 46.46/13.85 mod :: 0':s -> 0':s -> 0':s 46.46/13.85 if_mod :: true:false -> 0':s -> 0':s -> 0':s 46.46/13.85 hole_true:false1_0 :: true:false 46.46/13.85 hole_0':s2_0 :: 0':s 46.46/13.85 gen_0':s3_0 :: Nat -> 0':s 46.46/13.85 46.46/13.85 46.46/13.85 Lemmas: 46.46/13.85 le(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> true, rt in Omega(1 + n5_0) 46.46/13.85 minus(gen_0':s3_0(n252_0), gen_0':s3_0(n252_0)) -> gen_0':s3_0(0), rt in Omega(1 + n252_0) 46.46/13.85 46.46/13.85 46.46/13.85 Generator Equations: 46.46/13.85 gen_0':s3_0(0) <=> 0' 46.46/13.85 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 46.46/13.85 46.46/13.85 46.46/13.85 The following defined symbols remain to be analysed: 46.46/13.85 mod 46.53/13.89 EOF