1146.33/291.54 WORST_CASE(Omega(n^1), O(n^2)) 1146.33/291.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1146.33/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1146.33/291.55 1146.33/291.55 1146.33/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1146.33/291.55 1146.33/291.55 (0) CpxTRS 1146.33/291.55 (1) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 1146.33/291.55 (2) CpxWeightedTrs 1146.33/291.55 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1146.33/291.55 (4) CpxTypedWeightedTrs 1146.33/291.55 (5) CompletionProof [UPPER BOUND(ID), 0 ms] 1146.33/291.55 (6) CpxTypedWeightedCompleteTrs 1146.33/291.55 (7) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 1146.33/291.55 (8) CpxRNTS 1146.33/291.55 (9) CompleteCoflocoProof [FINISHED, 1454 ms] 1146.33/291.55 (10) BOUNDS(1, n^2) 1146.33/291.55 (11) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1146.33/291.55 (12) TRS for Loop Detection 1146.33/291.55 (13) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1146.33/291.55 (14) BEST 1146.33/291.55 (15) proven lower bound 1146.33/291.55 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1146.33/291.55 (17) BOUNDS(n^1, INF) 1146.33/291.55 (18) TRS for Loop Detection 1146.33/291.55 1146.33/291.55 1146.33/291.55 ---------------------------------------- 1146.33/291.55 1146.33/291.55 (0) 1146.33/291.55 Obligation: 1146.33/291.55 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1146.33/291.55 1146.33/291.55 1146.33/291.55 The TRS R consists of the following rules: 1146.33/291.55 1146.33/291.55 f(true, x, y, z) -> g(gt(x, y), x, y, z) 1146.33/291.55 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) 1146.33/291.55 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) 1146.33/291.55 gt(0, v) -> false 1146.33/291.55 gt(s(u), 0) -> true 1146.33/291.55 gt(s(u), s(v)) -> gt(u, v) 1146.33/291.55 1146.33/291.55 S is empty. 1146.33/291.55 Rewrite Strategy: INNERMOST 1146.33/291.55 ---------------------------------------- 1146.33/291.55 1146.33/291.55 (1) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 1146.33/291.55 Transformed relative TRS to weighted TRS 1146.33/291.55 ---------------------------------------- 1146.33/291.55 1146.33/291.55 (2) 1146.33/291.55 Obligation: 1146.33/291.55 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). 1146.33/291.55 1146.33/291.55 1146.33/291.55 The TRS R consists of the following rules: 1146.33/291.55 1146.33/291.55 f(true, x, y, z) -> g(gt(x, y), x, y, z) [1] 1146.33/291.55 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) [1] 1146.33/291.55 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) [1] 1146.33/291.55 gt(0, v) -> false [1] 1146.33/291.55 gt(s(u), 0) -> true [1] 1146.33/291.55 gt(s(u), s(v)) -> gt(u, v) [1] 1146.33/291.55 1146.33/291.55 Rewrite Strategy: INNERMOST 1146.33/291.55 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1146.33/291.56 Infered types. 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (4) 1146.33/291.56 Obligation: 1146.33/291.56 Runtime Complexity Weighted TRS with Types. 1146.33/291.56 The TRS R consists of the following rules: 1146.33/291.56 1146.33/291.56 f(true, x, y, z) -> g(gt(x, y), x, y, z) [1] 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) [1] 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) [1] 1146.33/291.56 gt(0, v) -> false [1] 1146.33/291.56 gt(s(u), 0) -> true [1] 1146.33/291.56 gt(s(u), s(v)) -> gt(u, v) [1] 1146.33/291.56 1146.33/291.56 The TRS has the following type information: 1146.33/291.56 f :: true:false -> s:0 -> s:0 -> s:0 -> f:g 1146.33/291.56 true :: true:false 1146.33/291.56 g :: true:false -> s:0 -> s:0 -> s:0 -> f:g 1146.33/291.56 gt :: s:0 -> s:0 -> true:false 1146.33/291.56 s :: s:0 -> s:0 1146.33/291.56 0 :: s:0 1146.33/291.56 false :: true:false 1146.33/291.56 1146.33/291.56 Rewrite Strategy: INNERMOST 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (5) CompletionProof (UPPER BOUND(ID)) 1146.33/291.56 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 1146.33/291.56 1146.33/291.56 f(v0, v1, v2, v3) -> null_f [0] 1146.33/291.56 g(v0, v1, v2, v3) -> null_g [0] 1146.33/291.56 1146.33/291.56 And the following fresh constants: null_f, null_g 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (6) 1146.33/291.56 Obligation: 1146.33/291.56 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 1146.33/291.56 1146.33/291.56 Runtime Complexity Weighted TRS with Types. 1146.33/291.56 The TRS R consists of the following rules: 1146.33/291.56 1146.33/291.56 f(true, x, y, z) -> g(gt(x, y), x, y, z) [1] 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) [1] 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) [1] 1146.33/291.56 gt(0, v) -> false [1] 1146.33/291.56 gt(s(u), 0) -> true [1] 1146.33/291.56 gt(s(u), s(v)) -> gt(u, v) [1] 1146.33/291.56 f(v0, v1, v2, v3) -> null_f [0] 1146.33/291.56 g(v0, v1, v2, v3) -> null_g [0] 1146.33/291.56 1146.33/291.56 The TRS has the following type information: 1146.33/291.56 f :: true:false -> s:0 -> s:0 -> s:0 -> null_f:null_g 1146.33/291.56 true :: true:false 1146.33/291.56 g :: true:false -> s:0 -> s:0 -> s:0 -> null_f:null_g 1146.33/291.56 gt :: s:0 -> s:0 -> true:false 1146.33/291.56 s :: s:0 -> s:0 1146.33/291.56 0 :: s:0 1146.33/291.56 false :: true:false 1146.33/291.56 null_f :: null_f:null_g 1146.33/291.56 null_g :: null_f:null_g 1146.33/291.56 1146.33/291.56 Rewrite Strategy: INNERMOST 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (7) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 1146.33/291.56 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 1146.33/291.56 The constant constructors are abstracted as follows: 1146.33/291.56 1146.33/291.56 true => 1 1146.33/291.56 0 => 0 1146.33/291.56 false => 0 1146.33/291.56 null_f => 0 1146.33/291.56 null_g => 0 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (8) 1146.33/291.56 Obligation: 1146.33/291.56 Complexity RNTS consisting of the following rules: 1146.33/291.56 1146.33/291.56 f(z', z'', z1, z2) -{ 1 }-> g(gt(x, y), x, y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 1146.33/291.56 f(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0 1146.33/291.56 g(z', z'', z1, z2) -{ 1 }-> f(gt(x, z), x, y, 1 + z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 1146.33/291.56 g(z', z'', z1, z2) -{ 1 }-> f(gt(x, z), x, 1 + y, z) :|: z1 = y, z >= 0, z2 = z, x >= 0, y >= 0, z'' = x, z' = 1 1146.33/291.56 g(z', z'', z1, z2) -{ 0 }-> 0 :|: z2 = v3, v0 >= 0, z1 = v2, v1 >= 0, z'' = v1, v2 >= 0, v3 >= 0, z' = v0 1146.33/291.56 gt(z', z'') -{ 1 }-> gt(u, v) :|: v >= 0, z' = 1 + u, z'' = 1 + v, u >= 0 1146.33/291.56 gt(z', z'') -{ 1 }-> 1 :|: z'' = 0, z' = 1 + u, u >= 0 1146.33/291.56 gt(z', z'') -{ 1 }-> 0 :|: z'' = v, v >= 0, z' = 0 1146.33/291.56 1146.33/291.56 Only complete derivations are relevant for the runtime complexity. 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (9) CompleteCoflocoProof (FINISHED) 1146.33/291.56 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 1146.33/291.56 1146.33/291.56 eq(start(V, V1, V6, V2),0,[f(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]). 1146.33/291.56 eq(start(V, V1, V6, V2),0,[g(V, V1, V6, V2, Out)],[V >= 0,V1 >= 0,V6 >= 0,V2 >= 0]). 1146.33/291.56 eq(start(V, V1, V6, V2),0,[gt(V, V1, Out)],[V >= 0,V1 >= 0]). 1146.33/291.56 eq(f(V, V1, V6, V2, Out),1,[gt(V4, V3, Ret0),g(Ret0, V4, V3, V5, Ret)],[Out = Ret,V6 = V3,V5 >= 0,V2 = V5,V4 >= 0,V3 >= 0,V1 = V4,V = 1]). 1146.33/291.56 eq(g(V, V1, V6, V2, Out),1,[gt(V7, V8, Ret01),f(Ret01, V7, 1 + V9, V8, Ret1)],[Out = Ret1,V6 = V9,V8 >= 0,V2 = V8,V7 >= 0,V9 >= 0,V1 = V7,V = 1]). 1146.33/291.56 eq(g(V, V1, V6, V2, Out),1,[gt(V11, V12, Ret02),f(Ret02, V11, V10, 1 + V12, Ret2)],[Out = Ret2,V6 = V10,V12 >= 0,V2 = V12,V11 >= 0,V10 >= 0,V1 = V11,V = 1]). 1146.33/291.56 eq(gt(V, V1, Out),1,[],[Out = 0,V1 = V13,V13 >= 0,V = 0]). 1146.33/291.56 eq(gt(V, V1, Out),1,[],[Out = 1,V1 = 0,V = 1 + V14,V14 >= 0]). 1146.33/291.56 eq(gt(V, V1, Out),1,[gt(V15, V16, Ret3)],[Out = Ret3,V16 >= 0,V = 1 + V15,V1 = 1 + V16,V15 >= 0]). 1146.33/291.56 eq(f(V, V1, V6, V2, Out),0,[],[Out = 0,V2 = V19,V18 >= 0,V6 = V20,V17 >= 0,V1 = V17,V20 >= 0,V19 >= 0,V = V18]). 1146.33/291.56 eq(g(V, V1, V6, V2, Out),0,[],[Out = 0,V2 = V24,V23 >= 0,V6 = V21,V22 >= 0,V1 = V22,V21 >= 0,V24 >= 0,V = V23]). 1146.33/291.56 input_output_vars(f(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]). 1146.33/291.56 input_output_vars(g(V,V1,V6,V2,Out),[V,V1,V6,V2],[Out]). 1146.33/291.56 input_output_vars(gt(V,V1,Out),[V,V1],[Out]). 1146.33/291.56 1146.33/291.56 1146.33/291.56 CoFloCo proof output: 1146.33/291.56 Preprocessing Cost Relations 1146.33/291.56 ===================================== 1146.33/291.56 1146.33/291.56 #### Computed strongly connected components 1146.33/291.56 0. recursive : [gt/3] 1146.33/291.56 1. recursive : [f/5,g/5] 1146.33/291.56 2. non_recursive : [start/4] 1146.33/291.56 1146.33/291.56 #### Obtained direct recursion through partial evaluation 1146.33/291.56 0. SCC is partially evaluated into gt/3 1146.33/291.56 1. SCC is partially evaluated into g/5 1146.33/291.56 2. SCC is partially evaluated into start/4 1146.33/291.56 1146.33/291.56 Control-Flow Refinement of Cost Relations 1146.33/291.56 ===================================== 1146.33/291.56 1146.33/291.56 ### Specialization of cost equations gt/3 1146.33/291.56 * CE 7 is refined into CE [12] 1146.33/291.56 * CE 6 is refined into CE [13] 1146.33/291.56 * CE 5 is refined into CE [14] 1146.33/291.56 1146.33/291.56 1146.33/291.56 ### Cost equations --> "Loop" of gt/3 1146.33/291.56 * CEs [13] --> Loop 8 1146.33/291.56 * CEs [14] --> Loop 9 1146.33/291.56 * CEs [12] --> Loop 10 1146.33/291.56 1146.33/291.56 ### Ranking functions of CR gt(V,V1,Out) 1146.33/291.56 * RF of phase [10]: [V,V1] 1146.33/291.56 1146.33/291.56 #### Partial ranking functions of CR gt(V,V1,Out) 1146.33/291.56 * Partial RF of phase [10]: 1146.33/291.56 - RF of loop [10:1]: 1146.33/291.56 V 1146.33/291.56 V1 1146.33/291.56 1146.33/291.56 1146.33/291.56 ### Specialization of cost equations g/5 1146.33/291.56 * CE 8 is refined into CE [15,16,17,18] 1146.33/291.56 * CE 11 is refined into CE [19] 1146.33/291.56 * CE 9 is refined into CE [20,21,22,23,24,25] 1146.33/291.56 * CE 10 is refined into CE [26,27,28,29] 1146.33/291.56 1146.33/291.56 1146.33/291.56 ### Cost equations --> "Loop" of g/5 1146.33/291.56 * CEs [25] --> Loop 11 1146.33/291.56 * CEs [29] --> Loop 12 1146.33/291.56 * CEs [24] --> Loop 13 1146.33/291.56 * CEs [28] --> Loop 14 1146.33/291.56 * CEs [22] --> Loop 15 1146.33/291.56 * CEs [27] --> Loop 16 1146.33/291.56 * CEs [21] --> Loop 17 1146.33/291.56 * CEs [26] --> Loop 18 1146.33/291.56 * CEs [23] --> Loop 19 1146.33/291.56 * CEs [20] --> Loop 20 1146.33/291.56 * CEs [18] --> Loop 21 1146.33/291.56 * CEs [17] --> Loop 22 1146.33/291.56 * CEs [16] --> Loop 23 1146.33/291.56 * CEs [15,19] --> Loop 24 1146.33/291.56 1146.33/291.56 ### Ranking functions of CR g(V,V1,V6,V2,Out) 1146.33/291.56 * RF of phase [11,12]: [2*V1-V6-V2-1] 1146.33/291.56 * RF of phase [16]: [V1-V6-1] 1146.33/291.56 * RF of phase [19]: [V1-V2] 1146.33/291.56 1146.33/291.56 #### Partial ranking functions of CR g(V,V1,V6,V2,Out) 1146.33/291.56 * Partial RF of phase [11,12]: 1146.33/291.56 - RF of loop [11:1]: 1146.33/291.56 V1-V2 1146.33/291.56 - RF of loop [12:1]: 1146.33/291.56 V1-V6-1 1146.33/291.56 * Partial RF of phase [16]: 1146.33/291.56 - RF of loop [16:1]: 1146.33/291.56 V1-V6-1 1146.33/291.56 * Partial RF of phase [19]: 1146.33/291.56 - RF of loop [19:1]: 1146.33/291.56 V1-V2 1146.33/291.56 1146.33/291.56 1146.33/291.56 ### Specialization of cost equations start/4 1146.33/291.56 * CE 1 is refined into CE [30] 1146.33/291.56 * CE 2 is refined into CE [31,32,33,34,35,36,37,38,39] 1146.33/291.56 * CE 3 is refined into CE [40,41,42,43] 1146.33/291.56 * CE 4 is refined into CE [44,45,46,47] 1146.33/291.56 1146.33/291.56 1146.33/291.56 ### Cost equations --> "Loop" of start/4 1146.33/291.56 * CEs [47] --> Loop 25 1146.33/291.56 * CEs [41] --> Loop 26 1146.33/291.56 * CEs [35] --> Loop 27 1146.33/291.56 * CEs [43] --> Loop 28 1146.33/291.56 * CEs [36,37,38,39,42,46] --> Loop 29 1146.33/291.56 * CEs [30,32,33,34,40] --> Loop 30 1146.33/291.56 * CEs [31,45] --> Loop 31 1146.33/291.56 * CEs [44] --> Loop 32 1146.33/291.56 1146.33/291.56 ### Ranking functions of CR start(V,V1,V6,V2) 1146.33/291.56 1146.33/291.56 #### Partial ranking functions of CR start(V,V1,V6,V2) 1146.33/291.56 1146.33/291.56 1146.33/291.56 Computing Bounds 1146.33/291.56 ===================================== 1146.33/291.56 1146.33/291.56 #### Cost of chains of gt(V,V1,Out): 1146.33/291.56 * Chain [[10],9]: 1*it(10)+1 1146.33/291.56 Such that:it(10) =< V 1146.33/291.56 1146.33/291.56 with precondition: [Out=0,V>=1,V1>=V] 1146.33/291.56 1146.33/291.56 * Chain [[10],8]: 1*it(10)+1 1146.33/291.56 Such that:it(10) =< V1 1146.33/291.56 1146.33/291.56 with precondition: [Out=1,V1>=1,V>=V1+1] 1146.33/291.56 1146.33/291.56 * Chain [9]: 1 1146.33/291.56 with precondition: [V=0,Out=0,V1>=0] 1146.33/291.56 1146.33/291.56 * Chain [8]: 1 1146.33/291.56 with precondition: [V1=0,Out=1,V>=1] 1146.33/291.56 1146.33/291.56 1146.33/291.56 #### Cost of chains of g(V,V1,V6,V2,Out): 1146.33/291.56 * Chain [[19],[11,12],24]: 4*it(11)+4*it(12)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+2 1146.33/291.56 Such that:it(11) =< V1-V2 1146.33/291.56 aux(10) =< V1 1146.33/291.56 aux(11) =< 2*V1-V2 1146.33/291.56 it(12) =< aux(10) 1146.33/291.56 it(19) =< aux(11) 1146.33/291.56 it(11) =< aux(11) 1146.33/291.56 it(12) =< aux(11) 1146.33/291.56 aux(4) =< aux(10)-1 1146.33/291.56 aux(3) =< aux(10)+1 1146.33/291.56 s(9) =< it(11)*aux(10) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(10) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+2] 1146.33/291.56 1146.33/291.56 * Chain [[19],[11,12],22]: 4*it(11)+4*it(12)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+1*s(16)+2 1146.33/291.56 Such that:it(11) =< V1-V2 1146.33/291.56 aux(14) =< V1 1146.33/291.56 aux(15) =< 2*V1-V2 1146.33/291.56 it(12) =< aux(14) 1146.33/291.56 it(19) =< aux(15) 1146.33/291.56 s(16) =< aux(14) 1146.33/291.56 it(11) =< aux(15) 1146.33/291.56 it(12) =< aux(15) 1146.33/291.56 aux(4) =< aux(14)-1 1146.33/291.56 aux(3) =< aux(14)+1 1146.33/291.56 s(9) =< it(11)*aux(14) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(14) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+2] 1146.33/291.56 1146.33/291.56 * Chain [[19],[11,12],21]: 4*it(11)+4*it(12)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+1*s(17)+2 1146.33/291.56 Such that:it(11) =< V1-V2 1146.33/291.56 aux(18) =< V1 1146.33/291.56 aux(19) =< 2*V1-V2 1146.33/291.56 it(12) =< aux(18) 1146.33/291.56 it(19) =< aux(19) 1146.33/291.56 s(17) =< aux(18) 1146.33/291.56 it(11) =< aux(19) 1146.33/291.56 it(12) =< aux(19) 1146.33/291.56 aux(4) =< aux(18)-1 1146.33/291.56 aux(3) =< aux(18)+1 1146.33/291.56 s(9) =< it(11)*aux(18) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(18) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+2] 1146.33/291.56 1146.33/291.56 * Chain [[19],[11,12],14,24]: 4*it(11)+4*it(12)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+2*s(18)+6 1146.33/291.56 Such that:it(11) =< V1-V2 1146.33/291.56 aux(22) =< V1 1146.33/291.56 aux(23) =< 2*V1-V2 1146.33/291.56 it(12) =< aux(22) 1146.33/291.56 it(19) =< aux(23) 1146.33/291.56 s(18) =< aux(22) 1146.33/291.56 it(11) =< aux(23) 1146.33/291.56 it(12) =< aux(23) 1146.33/291.56 aux(4) =< aux(22)-1 1146.33/291.56 aux(3) =< aux(22)+1 1146.33/291.56 s(9) =< it(11)*aux(22) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(22) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+2] 1146.33/291.56 1146.33/291.56 * Chain [[19],24]: 4*it(19)+1*s(15)+2 1146.33/291.56 Such that:aux(9) =< V1 1146.33/291.56 it(19) =< V1-V2 1146.33/291.56 s(15) =< it(19)*aux(9) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [[19],22]: 4*it(19)+1*s(15)+1*s(16)+2 1146.33/291.56 Such that:it(19) =< V1-V2 1146.33/291.56 aux(24) =< V1 1146.33/291.56 s(16) =< aux(24) 1146.33/291.56 s(15) =< it(19)*aux(24) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [[19],21]: 4*it(19)+1*s(15)+1*s(17)+2 1146.33/291.56 Such that:it(19) =< V1-V2 1146.33/291.56 aux(25) =< V1 1146.33/291.56 s(17) =< aux(25) 1146.33/291.56 s(15) =< it(19)*aux(25) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,Out=0,V2>=1,V1>=V2+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],24]: 4*it(16)+1*s(22)+2 1146.33/291.56 Such that:aux(26) =< V1 1146.33/291.56 it(16) =< V1-V6 1146.33/291.56 s(22) =< it(16)*aux(26) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],23]: 4*it(16)+1*s(22)+2 1146.33/291.56 Such that:aux(26) =< V1 1146.33/291.56 it(16) =< V1-V6 1146.33/291.56 s(22) =< it(16)*aux(26) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],18,24]: 4*it(16)+1*s(22)+1*s(23)+6 1146.33/291.56 Such that:it(16) =< V1-V6 1146.33/291.56 aux(27) =< V1 1146.33/291.56 s(23) =< aux(27) 1146.33/291.56 s(22) =< it(16)*aux(27) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,[11,12],24]: 8*it(11)+4*it(16)+2*s(9)+1*s(11)+1*s(12)+1*s(22)+1*s(24)+6 1146.33/291.56 Such that:aux(8) =< 2*V1 1146.33/291.56 it(16) =< 2*V1-V6 1146.33/291.56 aux(29) =< V1 1146.33/291.56 it(11) =< aux(29) 1146.33/291.56 s(24) =< aux(29) 1146.33/291.56 it(11) =< aux(8) 1146.33/291.56 aux(4) =< aux(29)-1 1146.33/291.56 aux(3) =< aux(29)+1 1146.33/291.56 s(9) =< it(11)*aux(29) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(22) =< it(16)*aux(29) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,[11,12],22]: 8*it(11)+4*it(16)+2*s(9)+1*s(11)+1*s(12)+2*s(16)+1*s(22)+6 1146.33/291.56 Such that:aux(13) =< 2*V1 1146.33/291.56 it(16) =< 2*V1-V6 1146.33/291.56 aux(31) =< V1 1146.33/291.56 it(11) =< aux(31) 1146.33/291.56 s(16) =< aux(31) 1146.33/291.56 it(11) =< aux(13) 1146.33/291.56 aux(4) =< aux(31)-1 1146.33/291.56 aux(3) =< aux(31)+1 1146.33/291.56 s(9) =< it(11)*aux(31) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(22) =< it(16)*aux(31) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,[11,12],21]: 8*it(11)+4*it(16)+2*s(9)+1*s(11)+1*s(12)+2*s(17)+1*s(22)+6 1146.33/291.56 Such that:aux(17) =< 2*V1 1146.33/291.56 it(16) =< 2*V1-V6 1146.33/291.56 aux(33) =< V1 1146.33/291.56 it(11) =< aux(33) 1146.33/291.56 s(17) =< aux(33) 1146.33/291.56 it(11) =< aux(17) 1146.33/291.56 aux(4) =< aux(33)-1 1146.33/291.56 aux(3) =< aux(33)+1 1146.33/291.56 s(9) =< it(11)*aux(33) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(22) =< it(16)*aux(33) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2,2*V1>=V6+5] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,[11,12],14,24]: 8*it(11)+4*it(16)+2*s(9)+1*s(11)+1*s(12)+3*s(18)+1*s(22)+10 1146.33/291.56 Such that:aux(21) =< 2*V1 1146.33/291.56 it(16) =< 2*V1-V6 1146.33/291.56 aux(35) =< V1 1146.33/291.56 it(11) =< aux(35) 1146.33/291.56 s(18) =< aux(35) 1146.33/291.56 it(11) =< aux(21) 1146.33/291.56 aux(4) =< aux(35)-1 1146.33/291.56 aux(3) =< aux(35)+1 1146.33/291.56 s(9) =< it(11)*aux(35) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(22) =< it(16)*aux(35) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2,2*V1>=V6+5] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,24]: 4*it(16)+1*s(22)+1*s(24)+6 1146.33/291.56 Such that:it(16) =< V1-V6 1146.33/291.56 aux(36) =< V1 1146.33/291.56 s(24) =< aux(36) 1146.33/291.56 s(22) =< it(16)*aux(36) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,21]: 4*it(16)+1*s(17)+1*s(22)+1*s(24)+6 1146.33/291.56 Such that:s(17) =< 1 1146.33/291.56 it(16) =< V1-V6 1146.33/291.56 aux(37) =< V1 1146.33/291.56 s(24) =< aux(37) 1146.33/291.56 s(22) =< it(16)*aux(37) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[16],15,14,24]: 4*it(16)+1*s(18)+2*s(19)+1*s(22)+10 1146.33/291.56 Such that:s(18) =< 1 1146.33/291.56 it(16) =< V1-V6 1146.33/291.56 aux(38) =< V1 1146.33/291.56 s(19) =< aux(38) 1146.33/291.56 s(22) =< it(16)*aux(38) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=0,V1>=V6+2] 1146.33/291.56 1146.33/291.56 * Chain [[11,12],24]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+2 1146.33/291.56 Such that:aux(5) =< V1 1146.33/291.56 it(12) =< V1-V6 1146.33/291.56 it(11) =< V1-V2 1146.33/291.56 aux(8) =< 2*V1-V6-V2 1146.33/291.56 it(11) =< aux(8) 1146.33/291.56 it(12) =< aux(8) 1146.33/291.56 aux(4) =< aux(5)-1 1146.33/291.56 aux(3) =< aux(5)+1 1146.33/291.56 s(9) =< it(11)*aux(5) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V6>=0,V2>=1,V1>=V6+1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [[11,12],22]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+1*s(16)+2 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 it(11) =< V1-V2 1146.33/291.56 aux(12) =< V1 1146.33/291.56 aux(13) =< 2*V1-V6-V2 1146.33/291.56 s(16) =< aux(12) 1146.33/291.56 it(11) =< aux(13) 1146.33/291.56 it(12) =< aux(13) 1146.33/291.56 aux(4) =< aux(12)-1 1146.33/291.56 aux(3) =< aux(12)+1 1146.33/291.56 s(9) =< it(11)*aux(12) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V6>=0,V2>=1,V1>=V6+1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [[11,12],21]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+1*s(17)+2 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 it(11) =< V1-V2 1146.33/291.56 aux(16) =< V1 1146.33/291.56 aux(17) =< 2*V1-V6-V2 1146.33/291.56 s(17) =< aux(16) 1146.33/291.56 it(11) =< aux(17) 1146.33/291.56 it(12) =< aux(17) 1146.33/291.56 aux(4) =< aux(16)-1 1146.33/291.56 aux(3) =< aux(16)+1 1146.33/291.56 s(9) =< it(11)*aux(16) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V6>=0,V2>=1,V1>=V6+1,V1>=V2+1,2*V1>=V2+V6+3] 1146.33/291.56 1146.33/291.56 * Chain [[11,12],14,24]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+2*s(18)+6 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 it(11) =< V1-V2 1146.33/291.56 aux(20) =< V1 1146.33/291.56 aux(21) =< 2*V1-V6-V2 1146.33/291.56 s(18) =< aux(20) 1146.33/291.56 it(11) =< aux(21) 1146.33/291.56 it(12) =< aux(21) 1146.33/291.56 aux(4) =< aux(20)-1 1146.33/291.56 aux(3) =< aux(20)+1 1146.33/291.56 s(9) =< it(11)*aux(20) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V6>=0,V2>=1,V1>=V6+1,V1>=V2+1,2*V1>=V2+V6+3] 1146.33/291.56 1146.33/291.56 * Chain [24]: 2 1146.33/291.56 with precondition: [Out=0,V>=0,V1>=0,V6>=0,V2>=0] 1146.33/291.56 1146.33/291.56 * Chain [23]: 2 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V1>=1,V6>=0] 1146.33/291.56 1146.33/291.56 * Chain [22]: 1*s(16)+2 1146.33/291.56 Such that:s(16) =< V1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V1>=1,V6>=0,V2>=V1] 1146.33/291.56 1146.33/291.56 * Chain [21]: 1*s(17)+2 1146.33/291.56 Such that:s(17) =< V2 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V6>=0,V2>=1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],[11,12],24]: 8*it(11)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+6 1146.33/291.56 Such that:aux(11) =< 2*V1 1146.33/291.56 aux(39) =< V1 1146.33/291.56 it(11) =< aux(39) 1146.33/291.56 it(19) =< aux(11) 1146.33/291.56 it(11) =< aux(11) 1146.33/291.56 aux(4) =< aux(39)-1 1146.33/291.56 aux(3) =< aux(39)+1 1146.33/291.56 s(9) =< it(11)*aux(39) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(39) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=3] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],[11,12],22]: 8*it(11)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+1*s(16)+6 1146.33/291.56 Such that:aux(15) =< 2*V1 1146.33/291.56 aux(40) =< V1 1146.33/291.56 it(11) =< aux(40) 1146.33/291.56 it(19) =< aux(15) 1146.33/291.56 s(16) =< aux(40) 1146.33/291.56 it(11) =< aux(15) 1146.33/291.56 aux(4) =< aux(40)-1 1146.33/291.56 aux(3) =< aux(40)+1 1146.33/291.56 s(9) =< it(11)*aux(40) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(40) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=3] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],[11,12],21]: 8*it(11)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+1*s(17)+6 1146.33/291.56 Such that:aux(19) =< 2*V1 1146.33/291.56 aux(41) =< V1 1146.33/291.56 it(11) =< aux(41) 1146.33/291.56 it(19) =< aux(19) 1146.33/291.56 s(17) =< aux(41) 1146.33/291.56 it(11) =< aux(19) 1146.33/291.56 aux(4) =< aux(41)-1 1146.33/291.56 aux(3) =< aux(41)+1 1146.33/291.56 s(9) =< it(11)*aux(41) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(41) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=3] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],[11,12],14,24]: 8*it(11)+4*it(19)+2*s(9)+1*s(11)+1*s(12)+1*s(15)+2*s(18)+10 1146.33/291.56 Such that:aux(23) =< 2*V1 1146.33/291.56 aux(42) =< V1 1146.33/291.56 it(11) =< aux(42) 1146.33/291.56 it(19) =< aux(23) 1146.33/291.56 s(18) =< aux(42) 1146.33/291.56 it(11) =< aux(23) 1146.33/291.56 aux(4) =< aux(42)-1 1146.33/291.56 aux(3) =< aux(42)+1 1146.33/291.56 s(9) =< it(11)*aux(42) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 s(15) =< it(19)*aux(42) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=3] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],24]: 4*it(19)+1*s(15)+6 1146.33/291.56 Such that:aux(43) =< V1 1146.33/291.56 it(19) =< aux(43) 1146.33/291.56 s(15) =< it(19)*aux(43) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],22]: 5*it(19)+1*s(15)+6 1146.33/291.56 Such that:aux(44) =< V1 1146.33/291.56 it(19) =< aux(44) 1146.33/291.56 s(15) =< it(19)*aux(44) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [20,[19],21]: 5*it(19)+1*s(15)+6 1146.33/291.56 Such that:aux(45) =< V1 1146.33/291.56 it(19) =< aux(45) 1146.33/291.56 s(15) =< it(19)*aux(45) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=3] 1146.33/291.56 1146.33/291.56 * Chain [20,[11,12],24]: 8*it(11)+2*s(9)+1*s(11)+1*s(12)+6 1146.33/291.56 Such that:aux(8) =< 2*V1 1146.33/291.56 aux(46) =< V1 1146.33/291.56 it(11) =< aux(46) 1146.33/291.56 it(11) =< aux(8) 1146.33/291.56 aux(4) =< aux(46)-1 1146.33/291.56 aux(3) =< aux(46)+1 1146.33/291.56 s(9) =< it(11)*aux(46) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [20,[11,12],22]: 8*it(11)+2*s(9)+1*s(11)+1*s(12)+1*s(16)+6 1146.33/291.56 Such that:aux(13) =< 2*V1 1146.33/291.56 aux(47) =< V1 1146.33/291.56 it(11) =< aux(47) 1146.33/291.56 s(16) =< aux(47) 1146.33/291.56 it(11) =< aux(13) 1146.33/291.56 aux(4) =< aux(47)-1 1146.33/291.56 aux(3) =< aux(47)+1 1146.33/291.56 s(9) =< it(11)*aux(47) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [20,[11,12],21]: 8*it(11)+2*s(9)+1*s(11)+1*s(12)+1*s(17)+6 1146.33/291.56 Such that:aux(17) =< 2*V1 1146.33/291.56 aux(48) =< V1 1146.33/291.56 it(11) =< aux(48) 1146.33/291.56 s(17) =< aux(48) 1146.33/291.56 it(11) =< aux(17) 1146.33/291.56 aux(4) =< aux(48)-1 1146.33/291.56 aux(3) =< aux(48)+1 1146.33/291.56 s(9) =< it(11)*aux(48) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [20,[11,12],14,24]: 8*it(11)+2*s(9)+1*s(11)+1*s(12)+2*s(18)+10 1146.33/291.56 Such that:aux(21) =< 2*V1 1146.33/291.56 aux(49) =< V1 1146.33/291.56 it(11) =< aux(49) 1146.33/291.56 s(18) =< aux(49) 1146.33/291.56 it(11) =< aux(21) 1146.33/291.56 aux(4) =< aux(49)-1 1146.33/291.56 aux(3) =< aux(49)+1 1146.33/291.56 s(9) =< it(11)*aux(49) 1146.33/291.56 s(11) =< it(11)*aux(4) 1146.33/291.56 s(12) =< it(11)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [20,24]: 6 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=1] 1146.33/291.56 1146.33/291.56 * Chain [20,22]: 1*s(16)+6 1146.33/291.56 Such that:s(16) =< 1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V1=1,V6=0,V2=0,Out=0] 1146.33/291.56 1146.33/291.56 * Chain [20,21]: 1*s(17)+6 1146.33/291.56 Such that:s(17) =< 1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6=0,V2=0,Out=0,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [18,24]: 1*s(23)+6 1146.33/291.56 Such that:s(23) =< V1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V1>=1,V6+1>=V1] 1146.33/291.56 1146.33/291.56 * Chain [17,24]: 1*s(25)+6 1146.33/291.56 Such that:s(25) =< V1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V1>=1,V6>=V1] 1146.33/291.56 1146.33/291.56 * Chain [15,[11,12],24]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+1*s(24)+6 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 aux(8) =< 2*V1-V6 1146.33/291.56 s(24) =< V6 1146.33/291.56 aux(28) =< V1 1146.33/291.56 it(11) =< aux(28) 1146.33/291.56 it(11) =< aux(8) 1146.33/291.56 it(12) =< aux(8) 1146.33/291.56 aux(4) =< aux(28)-1 1146.33/291.56 aux(3) =< aux(28)+1 1146.33/291.56 s(9) =< it(11)*aux(28) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+1] 1146.33/291.56 1146.33/291.56 * Chain [15,[11,12],22]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+1*s(16)+1*s(24)+6 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 aux(13) =< 2*V1-V6 1146.33/291.56 s(24) =< V6 1146.33/291.56 aux(30) =< V1 1146.33/291.56 it(11) =< aux(30) 1146.33/291.56 s(16) =< aux(30) 1146.33/291.56 it(11) =< aux(13) 1146.33/291.56 it(12) =< aux(13) 1146.33/291.56 aux(4) =< aux(30)-1 1146.33/291.56 aux(3) =< aux(30)+1 1146.33/291.56 s(9) =< it(11)*aux(30) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+1] 1146.33/291.56 1146.33/291.56 * Chain [15,[11,12],21]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+1*s(17)+1*s(24)+6 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 aux(17) =< 2*V1-V6 1146.33/291.56 s(24) =< V6 1146.33/291.56 aux(32) =< V1 1146.33/291.56 it(11) =< aux(32) 1146.33/291.56 s(17) =< aux(32) 1146.33/291.56 it(11) =< aux(17) 1146.33/291.56 it(12) =< aux(17) 1146.33/291.56 aux(4) =< aux(32)-1 1146.33/291.56 aux(3) =< aux(32)+1 1146.33/291.56 s(9) =< it(11)*aux(32) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+1,2*V1>=V6+4] 1146.33/291.56 1146.33/291.56 * Chain [15,[11,12],14,24]: 4*it(11)+4*it(12)+2*s(9)+1*s(11)+1*s(12)+2*s(18)+1*s(24)+10 1146.33/291.56 Such that:it(12) =< V1-V6 1146.33/291.56 aux(21) =< 2*V1-V6 1146.33/291.56 s(24) =< V6 1146.33/291.56 aux(34) =< V1 1146.33/291.56 it(11) =< aux(34) 1146.33/291.56 s(18) =< aux(34) 1146.33/291.56 it(11) =< aux(21) 1146.33/291.56 it(12) =< aux(21) 1146.33/291.56 aux(4) =< aux(34)-1 1146.33/291.56 aux(3) =< aux(34)+1 1146.33/291.56 s(9) =< it(11)*aux(34) 1146.33/291.56 s(11) =< it(12)*aux(4) 1146.33/291.56 s(12) =< it(12)*aux(3) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+1,2*V1>=V6+4] 1146.33/291.56 1146.33/291.56 * Chain [15,24]: 1*s(24)+6 1146.33/291.56 Such that:s(24) =< V6 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+1] 1146.33/291.56 1146.33/291.56 * Chain [15,21]: 1*s(17)+1*s(24)+6 1146.33/291.56 Such that:s(17) =< 1 1146.33/291.56 s(24) =< V6 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V6>=1,V1>=V6+1] 1146.33/291.56 1146.33/291.56 * Chain [15,14,24]: 1*s(18)+1*s(19)+1*s(24)+10 1146.33/291.56 Such that:s(18) =< 1 1146.33/291.56 s(24) =< V6 1146.33/291.56 s(19) =< V6+1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V2=0,Out=0,V1=V6+1,V1>=2] 1146.33/291.56 1146.33/291.56 * Chain [14,24]: 1*s(18)+1*s(19)+6 1146.33/291.56 Such that:s(19) =< V1 1146.33/291.56 s(18) =< V2 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V2>=1,V6+1>=V1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [13,24]: 1*s(26)+1*s(27)+6 1146.33/291.56 Such that:s(27) =< V1 1146.33/291.56 s(26) =< V2+1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,Out=0,V2>=1,V6>=V1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 1146.33/291.56 #### Cost of chains of start(V,V1,V6,V2): 1146.33/291.56 * Chain [32]: 1 1146.33/291.56 with precondition: [V=0,V1>=0] 1146.33/291.56 1146.33/291.56 * Chain [31]: 5*s(341)+56*s(343)+6*s(346)+4*s(354)+12 1146.33/291.56 Such that:s(335) =< 1 1146.33/291.56 aux(63) =< -V6 1146.33/291.56 s(340) =< V6 1146.33/291.56 s(341) =< s(335) 1146.33/291.56 s(343) =< aux(63) 1146.33/291.56 s(346) =< s(340) 1146.33/291.56 s(351) =< 1 1146.33/291.56 s(354) =< s(343)*s(351) 1146.33/291.56 1146.33/291.56 with precondition: [V1=0,V>=1] 1146.33/291.56 1146.33/291.56 * Chain [30]: 10*s(368)+119*s(369)+224*s(370)+48*s(372)+12*s(374)+56*s(379)+28*s(380)+28*s(381)+12*s(387)+1*s(389)+32*s(397)+32*s(398)+12*s(399)+2*s(401)+16*s(404)+8*s(405)+8*s(406)+3*s(407)+16*s(409)+4*s(413)+16*s(423)+24*s(424)+16*s(425)+6*s(426)+6*s(427)+16*s(429)+8*s(432)+4*s(433)+4*s(434)+4*s(441)+12 1146.33/291.56 Such that:s(417) =< V1-V6 1146.33/291.56 s(392) =< V1-V2 1146.33/291.56 s(419) =< 2*V1-V6 1146.33/291.56 aux(67) =< 2*V1-V2 1146.33/291.56 s(420) =< V6 1146.33/291.56 s(395) =< V2 1146.33/291.56 s(389) =< V2+1 1146.33/291.56 aux(68) =< 1 1146.33/291.56 aux(69) =< V1 1146.33/291.56 aux(70) =< 2*V1 1146.33/291.56 s(369) =< aux(69) 1146.33/291.56 s(368) =< aux(68) 1146.33/291.56 s(370) =< aux(69) 1146.33/291.56 s(372) =< aux(70) 1146.33/291.56 s(374) =< s(369)*aux(69) 1146.33/291.56 s(370) =< aux(70) 1146.33/291.56 s(377) =< aux(69)-1 1146.33/291.56 s(378) =< aux(69)+1 1146.33/291.56 s(379) =< s(370)*aux(69) 1146.33/291.56 s(380) =< s(370)*s(377) 1146.33/291.56 s(381) =< s(370)*s(378) 1146.33/291.56 s(387) =< s(372)*aux(69) 1146.33/291.56 s(423) =< s(417) 1146.33/291.56 s(424) =< s(417) 1146.33/291.56 s(425) =< s(419) 1146.33/291.56 s(426) =< s(420) 1146.33/291.56 s(427) =< s(424)*aux(69) 1146.33/291.56 s(429) =< aux(69) 1146.33/291.56 s(429) =< s(419) 1146.33/291.56 s(423) =< s(419) 1146.33/291.56 s(432) =< s(429)*aux(69) 1146.33/291.56 s(433) =< s(423)*s(377) 1146.33/291.56 s(434) =< s(423)*s(378) 1146.33/291.56 s(441) =< s(425)*aux(69) 1146.33/291.56 s(397) =< aux(69) 1146.33/291.56 s(398) =< s(392) 1146.33/291.56 s(399) =< s(392) 1146.33/291.56 s(401) =< s(395) 1146.33/291.56 s(398) =< aux(67) 1146.33/291.56 s(397) =< aux(67) 1146.33/291.56 s(404) =< s(398)*aux(69) 1146.33/291.56 s(405) =< s(397)*s(377) 1146.33/291.56 s(406) =< s(397)*s(378) 1146.33/291.56 s(407) =< s(399)*aux(69) 1146.33/291.56 s(409) =< aux(67) 1146.33/291.56 s(413) =< s(409)*aux(69) 1146.33/291.56 1146.33/291.56 with precondition: [V>=0,V1>=0,V6>=0,V2>=0] 1146.33/291.56 1146.33/291.56 * Chain [29]: 12*s(442)+7*s(449)+54*s(450)+16*s(451)+24*s(452)+16*s(453)+6*s(455)+3*s(456)+16*s(457)+8*s(460)+4*s(461)+4*s(462)+96*s(463)+24*s(464)+12*s(465)+12*s(466)+16*s(467)+4*s(468)+4*s(469)+1*s(471)+16*s(479)+16*s(480)+12*s(481)+16*s(482)+2*s(483)+8*s(486)+4*s(487)+4*s(488)+3*s(489)+16*s(490)+16*s(491)+8*s(492)+4*s(493)+4*s(494)+4*s(495)+2*s(499)+1*s(505)+12 1146.33/291.56 Such that:s(505) =< V 1146.33/291.56 s(474) =< V1-V2 1146.33/291.56 s(446) =< 2*V1 1146.33/291.56 s(447) =< 2*V1-V6 1146.33/291.56 s(475) =< 2*V1-V6-V2 1146.33/291.56 s(476) =< 2*V1-V2 1146.33/291.56 s(477) =< V2 1146.33/291.56 s(471) =< V2+1 1146.33/291.56 aux(73) =< 1 1146.33/291.56 aux(74) =< V1 1146.33/291.56 aux(75) =< V1-V6 1146.33/291.56 aux(76) =< V6 1146.33/291.56 aux(77) =< V6+1 1146.33/291.56 s(449) =< aux(73) 1146.33/291.56 s(450) =< aux(74) 1146.33/291.56 s(442) =< aux(76) 1146.33/291.56 s(499) =< aux(77) 1146.33/291.56 s(451) =< aux(75) 1146.33/291.56 s(452) =< aux(75) 1146.33/291.56 s(453) =< s(447) 1146.33/291.56 s(455) =< s(452)*aux(74) 1146.33/291.56 s(456) =< s(450)*aux(74) 1146.33/291.56 s(457) =< aux(74) 1146.33/291.56 s(457) =< s(447) 1146.33/291.56 s(451) =< s(447) 1146.33/291.56 s(458) =< aux(74)-1 1146.33/291.56 s(459) =< aux(74)+1 1146.33/291.56 s(460) =< s(457)*aux(74) 1146.33/291.56 s(461) =< s(451)*s(458) 1146.33/291.56 s(462) =< s(451)*s(459) 1146.33/291.56 s(463) =< aux(74) 1146.33/291.56 s(463) =< s(446) 1146.33/291.56 s(464) =< s(463)*aux(74) 1146.33/291.56 s(465) =< s(463)*s(458) 1146.33/291.56 s(466) =< s(463)*s(459) 1146.33/291.56 s(467) =< s(446) 1146.33/291.56 s(468) =< s(467)*aux(74) 1146.33/291.56 s(469) =< s(453)*aux(74) 1146.33/291.56 s(479) =< aux(75) 1146.33/291.56 s(480) =< s(474) 1146.33/291.56 s(481) =< s(474) 1146.33/291.56 s(482) =< s(474) 1146.33/291.56 s(483) =< s(477) 1146.33/291.56 s(480) =< s(475) 1146.33/291.56 s(479) =< s(475) 1146.33/291.56 s(486) =< s(480)*aux(74) 1146.33/291.56 s(487) =< s(479)*s(458) 1146.33/291.56 s(488) =< s(479)*s(459) 1146.33/291.56 s(489) =< s(481)*aux(74) 1146.33/291.56 s(490) =< aux(74) 1146.33/291.56 s(491) =< s(476) 1146.33/291.56 s(482) =< s(476) 1146.33/291.56 s(490) =< s(476) 1146.33/291.56 s(492) =< s(482)*aux(74) 1146.33/291.56 s(493) =< s(490)*s(458) 1146.33/291.56 s(494) =< s(490)*s(459) 1146.33/291.56 s(495) =< s(491)*aux(74) 1146.33/291.56 1146.33/291.56 with precondition: [V>=1,V1>=V] 1146.33/291.56 1146.33/291.56 * Chain [28]: 1*s(506)+2 1146.33/291.56 Such that:s(506) =< V1 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V1>=1,V6>=0,V2>=V1] 1146.33/291.56 1146.33/291.56 * Chain [27]: 42*s(507)+5*s(514)+16*s(516)+24*s(517)+16*s(518)+6*s(519)+6*s(520)+3*s(521)+16*s(522)+8*s(525)+4*s(526)+4*s(527)+96*s(528)+24*s(529)+12*s(530)+12*s(531)+16*s(532)+4*s(533)+4*s(534)+12 1146.33/291.56 Such that:s(508) =< 1 1146.33/291.56 s(510) =< V1-V6 1146.33/291.56 s(511) =< 2*V1 1146.33/291.56 s(512) =< 2*V1-V6 1146.33/291.56 s(513) =< V6 1146.33/291.56 aux(78) =< V1 1146.33/291.56 s(507) =< aux(78) 1146.33/291.56 s(514) =< s(508) 1146.33/291.56 s(516) =< s(510) 1146.33/291.56 s(517) =< s(510) 1146.33/291.56 s(518) =< s(512) 1146.33/291.56 s(519) =< s(513) 1146.33/291.56 s(520) =< s(517)*aux(78) 1146.33/291.56 s(521) =< s(507)*aux(78) 1146.33/291.56 s(522) =< aux(78) 1146.33/291.56 s(522) =< s(512) 1146.33/291.56 s(516) =< s(512) 1146.33/291.56 s(523) =< aux(78)-1 1146.33/291.56 s(524) =< aux(78)+1 1146.33/291.56 s(525) =< s(522)*aux(78) 1146.33/291.56 s(526) =< s(516)*s(523) 1146.33/291.56 s(527) =< s(516)*s(524) 1146.33/291.56 s(528) =< aux(78) 1146.33/291.56 s(528) =< s(511) 1146.33/291.56 s(529) =< s(528)*aux(78) 1146.33/291.56 s(530) =< s(528)*s(523) 1146.33/291.56 s(531) =< s(528)*s(524) 1146.33/291.56 s(532) =< s(511) 1146.33/291.56 s(533) =< s(532)*aux(78) 1146.33/291.56 s(534) =< s(518)*aux(78) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V1>=1,V2>=0,V6>=V1] 1146.33/291.56 1146.33/291.56 * Chain [26]: 1*s(535)+12*s(542)+16*s(543)+16*s(544)+12*s(545)+16*s(546)+2*s(547)+8*s(550)+4*s(551)+4*s(552)+3*s(553)+16*s(554)+16*s(555)+8*s(556)+4*s(557)+4*s(558)+4*s(559)+6 1146.33/291.56 Such that:s(536) =< V1 1146.33/291.56 s(537) =< V1-V6 1146.33/291.56 s(538) =< V1-V2 1146.33/291.56 s(539) =< 2*V1-V6-V2 1146.33/291.56 s(540) =< 2*V1-V2 1146.33/291.56 s(541) =< V2 1146.33/291.56 s(535) =< V2+1 1146.33/291.56 s(542) =< s(536) 1146.33/291.56 s(543) =< s(537) 1146.33/291.56 s(544) =< s(538) 1146.33/291.56 s(545) =< s(538) 1146.33/291.56 s(546) =< s(538) 1146.33/291.56 s(547) =< s(541) 1146.33/291.56 s(544) =< s(539) 1146.33/291.56 s(543) =< s(539) 1146.33/291.56 s(548) =< s(536)-1 1146.33/291.56 s(549) =< s(536)+1 1146.33/291.56 s(550) =< s(544)*s(536) 1146.33/291.56 s(551) =< s(543)*s(548) 1146.33/291.56 s(552) =< s(543)*s(549) 1146.33/291.56 s(553) =< s(545)*s(536) 1146.33/291.56 s(554) =< s(536) 1146.33/291.56 s(555) =< s(540) 1146.33/291.56 s(546) =< s(540) 1146.33/291.56 s(554) =< s(540) 1146.33/291.56 s(556) =< s(546)*s(536) 1146.33/291.56 s(557) =< s(554)*s(548) 1146.33/291.56 s(558) =< s(554)*s(549) 1146.33/291.56 s(559) =< s(555)*s(536) 1146.33/291.56 1146.33/291.56 with precondition: [V=1,V6>=0,V2>=1,V1>=V2+1] 1146.33/291.56 1146.33/291.56 * Chain [25]: 1*s(560)+1 1146.33/291.56 Such that:s(560) =< V1 1146.33/291.56 1146.33/291.56 with precondition: [V1>=1,V>=V1+1] 1146.33/291.56 1146.33/291.56 1146.33/291.56 Closed-form bounds of start(V,V1,V6,V2): 1146.33/291.56 ------------------------------------- 1146.33/291.56 * Chain [32] with precondition: [V=0,V1>=0] 1146.33/291.56 - Upper bound: 1 1146.33/291.56 - Complexity: constant 1146.33/291.56 * Chain [31] with precondition: [V1=0,V>=1] 1146.33/291.56 - Upper bound: nat(V6)*6+17+nat(-V6)*60 1146.33/291.56 - Complexity: n 1146.33/291.56 * Chain [30] with precondition: [V>=0,V1>=0,V6>=0,V2>=0] 1146.33/291.56 - Upper bound: 427*V1+22+112*V1*V1+36*V1*nat(V1-1)+12*V1*(2*V1)+10*V1*nat(V1-V6)+19*V1*nat(V1-V2)+4*V1*nat(2*V1-V6)+4*V1*nat(2*V1-V2)+6*V6+2*V2+nat(V1-1)*4*nat(V1-V6)+96*V1+(V2+1)+nat(V1-V6)*44+nat(V1-V2)*44+nat(2*V1-V6)*16+nat(2*V1-V2)*16 1146.33/291.56 - Complexity: n^2 1146.33/291.56 * Chain [29] with precondition: [V>=1,V1>=V] 1146.33/291.56 - Upper bound: V+198*V1+19+51*V1*V1+(V1-1)*(16*V1)+4*V1*(2*V1)+14*V1*nat(V1-V6)+19*V1*nat(V1-V2)+4*V1*nat(2*V1-V6)+4*V1*nat(2*V1-V2)+nat(V6)*12+nat(V2)*2+(8*V1-8)*nat(V1-V6)+32*V1+nat(V6+1)*2+nat(V2+1)+nat(V1-V6)*64+nat(V1-V2)*44+nat(2*V1-V6)*16+nat(2*V1-V2)*16 1146.33/291.56 - Complexity: n^2 1146.33/291.56 * Chain [28] with precondition: [V=1,V1>=1,V6>=0,V2>=V1] 1146.33/291.56 - Upper bound: V1+2 1146.33/291.56 - Complexity: n 1146.33/291.56 * Chain [27] with precondition: [V=1,V1>=1,V2>=0,V6>=V1] 1146.33/291.56 - Upper bound: 166*V1+17+47*V1*V1+(V1-1)*(12*V1)+4*V1*(2*V1)+4*V1*nat(2*V1-V6)+6*V6+32*V1+nat(2*V1-V6)*16 1146.33/291.56 - Complexity: n^2 1146.33/291.56 * Chain [26] with precondition: [V=1,V6>=0,V2>=1,V1>=V2+1] 1146.33/291.56 - Upper bound: 32*V1-16*V2+(44*V1-44*V2+(32*V1+6+4*V1*V1+(V1-1)*(4*V1)+4*V1*nat(V1-V6)+(V1-V2)*(19*V1)+(2*V1-V2)*(4*V1)+2*V2+(4*V1-4)*nat(V1-V6)+(V2+1)+nat(V1-V6)*20)) 1146.33/291.56 - Complexity: n^2 1146.33/291.56 * Chain [25] with precondition: [V1>=1,V>=V1+1] 1146.33/291.56 - Upper bound: V1+1 1146.33/291.56 - Complexity: n 1146.33/291.56 1146.33/291.56 ### Maximum cost of start(V,V1,V6,V2): max([nat(V6)*6+16+nat(-V6)*60,31*V1+4+4*V1*V1+4*V1*nat(V1-1)+max([19*V1*nat(V1-V2)+4*V1*nat(V1-V6)+4*V1*nat(2*V1-V2)+nat(V2)*2+nat(V1-1)*4*nat(V1-V6)+nat(V2+1)+nat(V1-V6)*20+nat(V1-V2)*44+nat(2*V1-V2)*16,32*V1+2+4*V1*V1+4*V1*nat(V1-1)+10*V1*nat(V1-V6)+19*V1*nat(V1-V2)+4*V1*nat(2*V1-V2)+nat(V2)*2+nat(V1-1)*4*nat(V1-V6)+nat(V2+1)+nat(V1-V6)*44+nat(V1-V2)*44+nat(2*V1-V2)*16+max([229*V1+3+61*V1*V1+20*V1*nat(V1-1)+8*V1*(2*V1)+64*V1,4*V1*nat(V1-V6)+V+nat(V6)*6+nat(V1-1)*4*nat(V1-V6)+nat(V6+1)*2+nat(V1-V6)*20])+(134*V1+11+43*V1*V1+8*V1*nat(V1-1)+4*V1*(2*V1)+4*V1*nat(2*V1-V6)+nat(V6)*6+32*V1+nat(2*V1-V6)*16)])+(V1+1)])+1 1146.33/291.56 Asymptotic class: n^2 1146.33/291.56 * Total analysis performed in 1303 ms. 1146.33/291.56 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (10) 1146.33/291.56 BOUNDS(1, n^2) 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (11) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1146.33/291.56 Transformed a relative TRS into a decreasing-loop problem. 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (12) 1146.33/291.56 Obligation: 1146.33/291.56 Analyzing the following TRS for decreasing loops: 1146.33/291.56 1146.33/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1146.33/291.56 1146.33/291.56 1146.33/291.56 The TRS R consists of the following rules: 1146.33/291.56 1146.33/291.56 f(true, x, y, z) -> g(gt(x, y), x, y, z) 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) 1146.33/291.56 gt(0, v) -> false 1146.33/291.56 gt(s(u), 0) -> true 1146.33/291.56 gt(s(u), s(v)) -> gt(u, v) 1146.33/291.56 1146.33/291.56 S is empty. 1146.33/291.56 Rewrite Strategy: INNERMOST 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (13) DecreasingLoopProof (LOWER BOUND(ID)) 1146.33/291.56 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1146.33/291.56 1146.33/291.56 The rewrite sequence 1146.33/291.56 1146.33/291.56 gt(s(u), s(v)) ->^+ gt(u, v) 1146.33/291.56 1146.33/291.56 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 1146.33/291.56 1146.33/291.56 The pumping substitution is [u / s(u), v / s(v)]. 1146.33/291.56 1146.33/291.56 The result substitution is [ ]. 1146.33/291.56 1146.33/291.56 1146.33/291.56 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (14) 1146.33/291.56 Complex Obligation (BEST) 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (15) 1146.33/291.56 Obligation: 1146.33/291.56 Proved the lower bound n^1 for the following obligation: 1146.33/291.56 1146.33/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1146.33/291.56 1146.33/291.56 1146.33/291.56 The TRS R consists of the following rules: 1146.33/291.56 1146.33/291.56 f(true, x, y, z) -> g(gt(x, y), x, y, z) 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) 1146.33/291.56 gt(0, v) -> false 1146.33/291.56 gt(s(u), 0) -> true 1146.33/291.56 gt(s(u), s(v)) -> gt(u, v) 1146.33/291.56 1146.33/291.56 S is empty. 1146.33/291.56 Rewrite Strategy: INNERMOST 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (16) LowerBoundPropagationProof (FINISHED) 1146.33/291.56 Propagated lower bound. 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (17) 1146.33/291.56 BOUNDS(n^1, INF) 1146.33/291.56 1146.33/291.56 ---------------------------------------- 1146.33/291.56 1146.33/291.56 (18) 1146.33/291.56 Obligation: 1146.33/291.56 Analyzing the following TRS for decreasing loops: 1146.33/291.56 1146.33/291.56 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^2). 1146.33/291.56 1146.33/291.56 1146.33/291.56 The TRS R consists of the following rules: 1146.33/291.56 1146.33/291.56 f(true, x, y, z) -> g(gt(x, y), x, y, z) 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, s(y), z) 1146.33/291.56 g(true, x, y, z) -> f(gt(x, z), x, y, s(z)) 1146.33/291.56 gt(0, v) -> false 1146.33/291.56 gt(s(u), 0) -> true 1146.33/291.56 gt(s(u), s(v)) -> gt(u, v) 1146.33/291.56 1146.33/291.56 S is empty. 1146.33/291.56 Rewrite Strategy: INNERMOST 1146.75/291.63 EOF