15.95/5.00 WORST_CASE(Omega(n^1), O(n^1)) 15.95/5.01 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 15.95/5.01 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 15.95/5.01 15.95/5.01 15.95/5.01 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 15.95/5.01 15.95/5.01 (0) CpxRelTRS 15.95/5.01 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 212 ms] 15.95/5.01 (2) CpxRelTRS 15.95/5.01 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 15.95/5.01 (4) CpxWeightedTrs 15.95/5.01 (5) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 15.95/5.01 (6) CpxWeightedTrs 15.95/5.01 (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 15.95/5.01 (8) CpxTypedWeightedTrs 15.95/5.01 (9) CompletionProof [UPPER BOUND(ID), 0 ms] 15.95/5.01 (10) CpxTypedWeightedCompleteTrs 15.95/5.01 (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 15.95/5.01 (12) CpxRNTS 15.95/5.01 (13) CompleteCoflocoProof [FINISHED, 234 ms] 15.95/5.01 (14) BOUNDS(1, n^1) 15.95/5.01 (15) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 15.95/5.01 (16) TRS for Loop Detection 15.95/5.01 (17) DecreasingLoopProof [LOWER BOUND(ID), 25 ms] 15.95/5.01 (18) BEST 15.95/5.01 (19) proven lower bound 15.95/5.01 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 15.95/5.01 (21) BOUNDS(n^1, INF) 15.95/5.01 (22) TRS for Loop Detection 15.95/5.01 15.95/5.01 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (0) 15.95/5.01 Obligation: 15.95/5.01 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 15.95/5.01 15.95/5.01 15.95/5.01 The TRS R consists of the following rules: 15.95/5.01 15.95/5.01 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](<(x', x), Cons(x', Cons(x, xs))) 15.95/5.01 ordered(Cons(x, Nil)) -> True 15.95/5.01 ordered(Nil) -> True 15.95/5.01 notEmpty(Cons(x, xs)) -> True 15.95/5.01 notEmpty(Nil) -> False 15.95/5.01 goal(xs) -> ordered(xs) 15.95/5.01 15.95/5.01 The (relative) TRS S consists of the following rules: 15.95/5.01 15.95/5.01 <(S(x), S(y)) -> <(x, y) 15.95/5.01 <(0, S(y)) -> True 15.95/5.01 <(x, 0) -> False 15.95/5.01 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) 15.95/5.01 ordered[Ite](False, xs) -> False 15.95/5.01 15.95/5.01 Rewrite Strategy: INNERMOST 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 15.95/5.01 proved termination of relative rules 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (2) 15.95/5.01 Obligation: 15.95/5.01 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 15.95/5.01 15.95/5.01 15.95/5.01 The TRS R consists of the following rules: 15.95/5.01 15.95/5.01 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](<(x', x), Cons(x', Cons(x, xs))) 15.95/5.01 ordered(Cons(x, Nil)) -> True 15.95/5.01 ordered(Nil) -> True 15.95/5.01 notEmpty(Cons(x, xs)) -> True 15.95/5.01 notEmpty(Nil) -> False 15.95/5.01 goal(xs) -> ordered(xs) 15.95/5.01 15.95/5.01 The (relative) TRS S consists of the following rules: 15.95/5.01 15.95/5.01 <(S(x), S(y)) -> <(x, y) 15.95/5.01 <(0, S(y)) -> True 15.95/5.01 <(x, 0) -> False 15.95/5.01 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) 15.95/5.01 ordered[Ite](False, xs) -> False 15.95/5.01 15.95/5.01 Rewrite Strategy: INNERMOST 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 15.95/5.01 Transformed relative TRS to weighted TRS 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (4) 15.95/5.01 Obligation: 15.95/5.01 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 15.95/5.01 15.95/5.01 15.95/5.01 The TRS R consists of the following rules: 15.95/5.01 15.95/5.01 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](<(x', x), Cons(x', Cons(x, xs))) [1] 15.95/5.01 ordered(Cons(x, Nil)) -> True [1] 15.95/5.01 ordered(Nil) -> True [1] 15.95/5.01 notEmpty(Cons(x, xs)) -> True [1] 15.95/5.01 notEmpty(Nil) -> False [1] 15.95/5.01 goal(xs) -> ordered(xs) [1] 15.95/5.01 <(S(x), S(y)) -> <(x, y) [0] 15.95/5.01 <(0, S(y)) -> True [0] 15.95/5.01 <(x, 0) -> False [0] 15.95/5.01 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) [0] 15.95/5.01 ordered[Ite](False, xs) -> False [0] 15.95/5.01 15.95/5.01 Rewrite Strategy: INNERMOST 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (5) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) 15.95/5.01 Renamed defined symbols to avoid conflicts with arithmetic symbols: 15.95/5.01 15.95/5.01 < => lt 15.95/5.01 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (6) 15.95/5.01 Obligation: 15.95/5.01 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 15.95/5.01 15.95/5.01 15.95/5.01 The TRS R consists of the following rules: 15.95/5.01 15.95/5.01 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](lt(x', x), Cons(x', Cons(x, xs))) [1] 15.95/5.01 ordered(Cons(x, Nil)) -> True [1] 15.95/5.01 ordered(Nil) -> True [1] 15.95/5.01 notEmpty(Cons(x, xs)) -> True [1] 15.95/5.01 notEmpty(Nil) -> False [1] 15.95/5.01 goal(xs) -> ordered(xs) [1] 15.95/5.01 lt(S(x), S(y)) -> lt(x, y) [0] 15.95/5.01 lt(0, S(y)) -> True [0] 15.95/5.01 lt(x, 0) -> False [0] 15.95/5.01 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) [0] 15.95/5.01 ordered[Ite](False, xs) -> False [0] 15.95/5.01 15.95/5.01 Rewrite Strategy: INNERMOST 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 15.95/5.01 Infered types. 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (8) 15.95/5.01 Obligation: 15.95/5.01 Runtime Complexity Weighted TRS with Types. 15.95/5.01 The TRS R consists of the following rules: 15.95/5.01 15.95/5.01 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](lt(x', x), Cons(x', Cons(x, xs))) [1] 15.95/5.01 ordered(Cons(x, Nil)) -> True [1] 15.95/5.01 ordered(Nil) -> True [1] 15.95/5.01 notEmpty(Cons(x, xs)) -> True [1] 15.95/5.01 notEmpty(Nil) -> False [1] 15.95/5.01 goal(xs) -> ordered(xs) [1] 15.95/5.01 lt(S(x), S(y)) -> lt(x, y) [0] 15.95/5.01 lt(0, S(y)) -> True [0] 15.95/5.01 lt(x, 0) -> False [0] 15.95/5.01 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) [0] 15.95/5.01 ordered[Ite](False, xs) -> False [0] 15.95/5.01 15.95/5.01 The TRS has the following type information: 15.95/5.01 ordered :: Cons:Nil -> True:False 15.95/5.01 Cons :: S:0 -> Cons:Nil -> Cons:Nil 15.95/5.01 ordered[Ite] :: True:False -> Cons:Nil -> True:False 15.95/5.01 lt :: S:0 -> S:0 -> True:False 15.95/5.01 Nil :: Cons:Nil 15.95/5.01 True :: True:False 15.95/5.01 notEmpty :: Cons:Nil -> True:False 15.95/5.01 False :: True:False 15.95/5.01 goal :: Cons:Nil -> True:False 15.95/5.01 S :: S:0 -> S:0 15.95/5.01 0 :: S:0 15.95/5.01 15.95/5.01 Rewrite Strategy: INNERMOST 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (9) CompletionProof (UPPER BOUND(ID)) 15.95/5.01 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 15.95/5.01 15.95/5.01 lt(v0, v1) -> null_lt [0] 15.95/5.01 ordered[Ite](v0, v1) -> null_ordered[Ite] [0] 15.95/5.01 15.95/5.01 And the following fresh constants: null_lt, null_ordered[Ite] 15.95/5.01 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (10) 15.95/5.01 Obligation: 15.95/5.01 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 15.95/5.01 15.95/5.01 Runtime Complexity Weighted TRS with Types. 15.95/5.01 The TRS R consists of the following rules: 15.95/5.01 15.95/5.01 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](lt(x', x), Cons(x', Cons(x, xs))) [1] 15.95/5.01 ordered(Cons(x, Nil)) -> True [1] 15.95/5.01 ordered(Nil) -> True [1] 15.95/5.01 notEmpty(Cons(x, xs)) -> True [1] 15.95/5.01 notEmpty(Nil) -> False [1] 15.95/5.01 goal(xs) -> ordered(xs) [1] 15.95/5.01 lt(S(x), S(y)) -> lt(x, y) [0] 15.95/5.01 lt(0, S(y)) -> True [0] 15.95/5.01 lt(x, 0) -> False [0] 15.95/5.01 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) [0] 15.95/5.01 ordered[Ite](False, xs) -> False [0] 15.95/5.01 lt(v0, v1) -> null_lt [0] 15.95/5.01 ordered[Ite](v0, v1) -> null_ordered[Ite] [0] 15.95/5.01 15.95/5.01 The TRS has the following type information: 15.95/5.01 ordered :: Cons:Nil -> True:False:null_lt:null_ordered[Ite] 15.95/5.01 Cons :: S:0 -> Cons:Nil -> Cons:Nil 15.95/5.01 ordered[Ite] :: True:False:null_lt:null_ordered[Ite] -> Cons:Nil -> True:False:null_lt:null_ordered[Ite] 15.95/5.01 lt :: S:0 -> S:0 -> True:False:null_lt:null_ordered[Ite] 15.95/5.01 Nil :: Cons:Nil 15.95/5.01 True :: True:False:null_lt:null_ordered[Ite] 15.95/5.01 notEmpty :: Cons:Nil -> True:False:null_lt:null_ordered[Ite] 15.95/5.01 False :: True:False:null_lt:null_ordered[Ite] 15.95/5.01 goal :: Cons:Nil -> True:False:null_lt:null_ordered[Ite] 15.95/5.01 S :: S:0 -> S:0 15.95/5.01 0 :: S:0 15.95/5.01 null_lt :: True:False:null_lt:null_ordered[Ite] 15.95/5.01 null_ordered[Ite] :: True:False:null_lt:null_ordered[Ite] 15.95/5.01 15.95/5.01 Rewrite Strategy: INNERMOST 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 15.95/5.01 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 15.95/5.01 The constant constructors are abstracted as follows: 15.95/5.01 15.95/5.01 Nil => 0 15.95/5.01 True => 2 15.95/5.01 False => 1 15.95/5.01 0 => 0 15.95/5.01 null_lt => 0 15.95/5.01 null_ordered[Ite] => 0 15.95/5.01 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (12) 15.95/5.01 Obligation: 15.95/5.01 Complexity RNTS consisting of the following rules: 15.95/5.01 15.95/5.01 goal(z) -{ 1 }-> ordered(xs) :|: xs >= 0, z = xs 15.95/5.01 lt(z, z') -{ 0 }-> lt(x, y) :|: z' = 1 + y, x >= 0, y >= 0, z = 1 + x 15.95/5.01 lt(z, z') -{ 0 }-> 2 :|: z' = 1 + y, y >= 0, z = 0 15.95/5.01 lt(z, z') -{ 0 }-> 1 :|: x >= 0, z = x, z' = 0 15.95/5.01 lt(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 15.95/5.01 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 15.95/5.01 notEmpty(z) -{ 1 }-> 1 :|: z = 0 15.95/5.01 ordered(z) -{ 1 }-> ordered[Ite](lt(x', x), 1 + x' + (1 + x + xs)) :|: xs >= 0, x' >= 0, x >= 0, z = 1 + x' + (1 + x + xs) 15.95/5.01 ordered(z) -{ 1 }-> 2 :|: x >= 0, z = 1 + x + 0 15.95/5.01 ordered(z) -{ 1 }-> 2 :|: z = 0 15.95/5.01 ordered[Ite](z, z') -{ 0 }-> ordered(xs) :|: z = 2, z' = 1 + x' + (1 + x + xs), xs >= 0, x' >= 0, x >= 0 15.95/5.01 ordered[Ite](z, z') -{ 0 }-> 1 :|: xs >= 0, z = 1, z' = xs 15.95/5.01 ordered[Ite](z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 15.95/5.01 15.95/5.01 Only complete derivations are relevant for the runtime complexity. 15.95/5.01 15.95/5.01 ---------------------------------------- 15.95/5.01 15.95/5.01 (13) CompleteCoflocoProof (FINISHED) 15.95/5.01 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 15.95/5.01 15.95/5.01 eq(start(V, V9),0,[ordered(V, Out)],[V >= 0]). 15.95/5.01 eq(start(V, V9),0,[notEmpty(V, Out)],[V >= 0]). 15.95/5.01 eq(start(V, V9),0,[goal(V, Out)],[V >= 0]). 15.95/5.01 eq(start(V, V9),0,[lt(V, V9, Out)],[V >= 0,V9 >= 0]). 15.95/5.01 eq(start(V, V9),0,[fun(V, V9, Out)],[V >= 0,V9 >= 0]). 15.95/5.01 eq(ordered(V, Out),1,[lt(V2, V3, Ret0),fun(Ret0, 1 + V2 + (1 + V3 + V1), Ret)],[Out = Ret,V1 >= 0,V2 >= 0,V3 >= 0,V = 2 + V1 + V2 + V3]). 15.95/5.01 eq(ordered(V, Out),1,[],[Out = 2,V4 >= 0,V = 1 + V4]). 15.95/5.01 eq(ordered(V, Out),1,[],[Out = 2,V = 0]). 15.95/5.01 eq(notEmpty(V, Out),1,[],[Out = 2,V = 1 + V5 + V6,V6 >= 0,V5 >= 0]). 15.95/5.01 eq(notEmpty(V, Out),1,[],[Out = 1,V = 0]). 15.95/5.01 eq(goal(V, Out),1,[ordered(V7, Ret1)],[Out = Ret1,V7 >= 0,V = V7]). 15.95/5.01 eq(lt(V, V9, Out),0,[lt(V8, V10, Ret2)],[Out = Ret2,V9 = 1 + V10,V8 >= 0,V10 >= 0,V = 1 + V8]). 15.95/5.01 eq(lt(V, V9, Out),0,[],[Out = 2,V9 = 1 + V11,V11 >= 0,V = 0]). 15.95/5.01 eq(lt(V, V9, Out),0,[],[Out = 1,V12 >= 0,V = V12,V9 = 0]). 15.95/5.01 eq(fun(V, V9, Out),0,[ordered(V14, Ret3)],[Out = Ret3,V = 2,V9 = 2 + V13 + V14 + V15,V14 >= 0,V15 >= 0,V13 >= 0]). 15.95/5.01 eq(fun(V, V9, Out),0,[],[Out = 1,V16 >= 0,V = 1,V9 = V16]). 15.95/5.01 eq(lt(V, V9, Out),0,[],[Out = 0,V18 >= 0,V17 >= 0,V = V18,V9 = V17]). 15.95/5.01 eq(fun(V, V9, Out),0,[],[Out = 0,V20 >= 0,V19 >= 0,V = V20,V9 = V19]). 15.95/5.01 input_output_vars(ordered(V,Out),[V],[Out]). 15.95/5.01 input_output_vars(notEmpty(V,Out),[V],[Out]). 15.95/5.01 input_output_vars(goal(V,Out),[V],[Out]). 15.95/5.01 input_output_vars(lt(V,V9,Out),[V,V9],[Out]). 15.95/5.01 input_output_vars(fun(V,V9,Out),[V,V9],[Out]). 15.95/5.01 15.95/5.01 15.95/5.01 CoFloCo proof output: 15.95/5.01 Preprocessing Cost Relations 15.95/5.01 ===================================== 15.95/5.01 15.95/5.01 #### Computed strongly connected components 15.95/5.01 0. recursive : [lt/3] 15.95/5.01 1. recursive : [fun/3,ordered/2] 15.95/5.01 2. non_recursive : [goal/2] 15.95/5.01 3. non_recursive : [notEmpty/2] 15.95/5.01 4. non_recursive : [start/2] 15.95/5.01 15.95/5.01 #### Obtained direct recursion through partial evaluation 15.95/5.01 0. SCC is partially evaluated into lt/3 15.95/5.01 1. SCC is partially evaluated into ordered/2 15.95/5.01 2. SCC is completely evaluated into other SCCs 15.95/5.01 3. SCC is partially evaluated into notEmpty/2 15.95/5.01 4. SCC is partially evaluated into start/2 15.95/5.01 15.95/5.01 Control-Flow Refinement of Cost Relations 15.95/5.01 ===================================== 15.95/5.01 15.95/5.01 ### Specialization of cost equations lt/3 15.95/5.01 * CE 17 is refined into CE [18] 15.95/5.01 * CE 16 is refined into CE [19] 15.95/5.01 * CE 15 is refined into CE [20] 15.95/5.01 * CE 14 is refined into CE [21] 15.95/5.01 15.95/5.01 15.95/5.01 ### Cost equations --> "Loop" of lt/3 15.95/5.01 * CEs [21] --> Loop 13 15.95/5.01 * CEs [18] --> Loop 14 15.95/5.01 * CEs [19] --> Loop 15 15.95/5.01 * CEs [20] --> Loop 16 15.95/5.01 15.95/5.01 ### Ranking functions of CR lt(V,V9,Out) 15.95/5.01 * RF of phase [13]: [V,V9] 15.95/5.01 15.95/5.01 #### Partial ranking functions of CR lt(V,V9,Out) 15.95/5.01 * Partial RF of phase [13]: 15.95/5.01 - RF of loop [13:1]: 15.95/5.01 V 15.95/5.01 V9 15.95/5.01 15.95/5.01 15.95/5.01 ### Specialization of cost equations ordered/2 15.95/5.01 * CE 10 is refined into CE [22] 15.95/5.01 * CE 8 is refined into CE [23,24] 15.95/5.01 * CE 7 is refined into CE [25,26,27,28,29] 15.95/5.01 * CE 11 is refined into CE [30] 15.95/5.01 * CE 9 is refined into CE [31,32] 15.95/5.01 15.95/5.01 15.95/5.01 ### Cost equations --> "Loop" of ordered/2 15.95/5.01 * CEs [31,32] --> Loop 17 15.95/5.01 * CEs [22] --> Loop 18 15.95/5.01 * CEs [23,24] --> Loop 19 15.95/5.01 * CEs [25,26,27,28,29] --> Loop 20 15.95/5.01 * CEs [30] --> Loop 21 15.95/5.01 15.95/5.01 ### Ranking functions of CR ordered(V,Out) 15.95/5.01 * RF of phase [17]: [V/2-1] 15.95/5.01 15.95/5.01 #### Partial ranking functions of CR ordered(V,Out) 15.95/5.01 * Partial RF of phase [17]: 15.95/5.01 - RF of loop [17:1]: 15.95/5.01 V/2-1 15.95/5.01 15.95/5.01 15.95/5.01 ### Specialization of cost equations notEmpty/2 15.95/5.01 * CE 12 is refined into CE [33] 15.95/5.01 * CE 13 is refined into CE [34] 15.95/5.01 15.95/5.01 15.95/5.01 ### Cost equations --> "Loop" of notEmpty/2 15.95/5.01 * CEs [33] --> Loop 22 15.95/5.01 * CEs [34] --> Loop 23 15.95/5.01 15.95/5.01 ### Ranking functions of CR notEmpty(V,Out) 15.95/5.01 15.95/5.01 #### Partial ranking functions of CR notEmpty(V,Out) 15.95/5.01 15.95/5.01 15.95/5.01 ### Specialization of cost equations start/2 15.95/5.01 * CE 1 is refined into CE [35] 15.95/5.01 * CE 2 is refined into CE [36,37,38,39] 15.95/5.02 * CE 3 is refined into CE [40,41,42,43] 15.95/5.02 * CE 4 is refined into CE [44,45] 15.95/5.02 * CE 5 is refined into CE [46,47,48,49] 15.95/5.02 * CE 6 is refined into CE [50,51,52,53,54] 15.95/5.02 15.95/5.02 15.95/5.02 ### Cost equations --> "Loop" of start/2 15.95/5.02 * CEs [41,42,43,45,47,48,49] --> Loop 24 15.95/5.02 * CEs [51] --> Loop 25 15.95/5.02 * CEs [35,36,37,38,39,52,53,54] --> Loop 26 15.95/5.02 * CEs [40,44,46,50] --> Loop 27 15.95/5.02 15.95/5.02 ### Ranking functions of CR start(V,V9) 15.95/5.02 15.95/5.02 #### Partial ranking functions of CR start(V,V9) 15.95/5.02 15.95/5.02 15.95/5.02 Computing Bounds 15.95/5.02 ===================================== 15.95/5.02 15.95/5.02 #### Cost of chains of lt(V,V9,Out): 15.95/5.02 * Chain [[13],16]: 0 15.95/5.02 with precondition: [Out=2,V>=1,V9>=V+1] 15.95/5.02 15.95/5.02 * Chain [[13],15]: 0 15.95/5.02 with precondition: [Out=1,V9>=1,V>=V9] 15.95/5.02 15.95/5.02 * Chain [[13],14]: 0 15.95/5.02 with precondition: [Out=0,V>=1,V9>=1] 15.95/5.02 15.95/5.02 * Chain [16]: 0 15.95/5.02 with precondition: [V=0,Out=2,V9>=1] 15.95/5.02 15.95/5.02 * Chain [15]: 0 15.95/5.02 with precondition: [V9=0,Out=1,V>=0] 15.95/5.02 15.95/5.02 * Chain [14]: 0 15.95/5.02 with precondition: [Out=0,V>=0,V9>=0] 15.95/5.02 15.95/5.02 15.95/5.02 #### Cost of chains of ordered(V,Out): 15.95/5.02 * Chain [[17],21]: 1*it(17)+1 15.95/5.02 Such that:it(17) =< V/2 15.95/5.02 15.95/5.02 with precondition: [Out=2,V>=3] 15.95/5.02 15.95/5.02 * Chain [[17],20]: 1*it(17)+1 15.95/5.02 Such that:it(17) =< V/2 15.95/5.02 15.95/5.02 with precondition: [Out=0,V>=4] 15.95/5.02 15.95/5.02 * Chain [[17],19]: 1*it(17)+1 15.95/5.02 Such that:it(17) =< V/2 15.95/5.02 15.95/5.02 with precondition: [Out=1,V>=4] 15.95/5.02 15.95/5.02 * Chain [[17],18]: 1*it(17)+1 15.95/5.02 Such that:it(17) =< V/2 15.95/5.02 15.95/5.02 with precondition: [Out=2,V>=3] 15.95/5.02 15.95/5.02 * Chain [21]: 1 15.95/5.02 with precondition: [V=0,Out=2] 15.95/5.02 15.95/5.02 * Chain [20]: 1 15.95/5.02 with precondition: [Out=0,V>=2] 15.95/5.02 15.95/5.02 * Chain [19]: 1 15.95/5.02 with precondition: [Out=1,V>=2] 15.95/5.02 15.95/5.02 * Chain [18]: 1 15.95/5.02 with precondition: [Out=2,V>=1] 15.95/5.02 15.95/5.02 15.95/5.02 #### Cost of chains of notEmpty(V,Out): 15.95/5.02 * Chain [23]: 1 15.95/5.02 with precondition: [V=0,Out=1] 15.95/5.02 15.95/5.02 * Chain [22]: 1 15.95/5.02 with precondition: [Out=2,V>=1] 15.95/5.02 15.95/5.02 15.95/5.02 #### Cost of chains of start(V,V9): 15.95/5.02 * Chain [27]: 2 15.95/5.02 with precondition: [V=0] 15.95/5.02 15.95/5.02 * Chain [26]: 4*s(5)+1 15.95/5.02 Such that:aux(2) =< V9/2 15.95/5.02 s(5) =< aux(2) 15.95/5.02 15.95/5.02 with precondition: [V>=0,V9>=0] 15.95/5.02 15.95/5.02 * Chain [25]: 0 15.95/5.02 with precondition: [V9=0,V>=0] 15.95/5.02 15.95/5.02 * Chain [24]: 8*s(9)+2 15.95/5.02 Such that:aux(3) =< V/2 15.95/5.02 s(9) =< aux(3) 15.95/5.02 15.95/5.02 with precondition: [V>=1] 15.95/5.02 15.95/5.02 15.95/5.02 Closed-form bounds of start(V,V9): 15.95/5.02 ------------------------------------- 15.95/5.02 * Chain [27] with precondition: [V=0] 15.95/5.02 - Upper bound: 2 15.95/5.02 - Complexity: constant 15.95/5.02 * Chain [26] with precondition: [V>=0,V9>=0] 15.95/5.02 - Upper bound: 2*V9+1 15.95/5.02 - Complexity: n 15.95/5.02 * Chain [25] with precondition: [V9=0,V>=0] 15.95/5.02 - Upper bound: 0 15.95/5.02 - Complexity: constant 15.95/5.02 * Chain [24] with precondition: [V>=1] 15.95/5.02 - Upper bound: 4*V+2 15.95/5.02 - Complexity: n 15.95/5.02 15.95/5.02 ### Maximum cost of start(V,V9): max([4*V+2,nat(V9/2)*4+1]) 15.95/5.02 Asymptotic class: n 15.95/5.02 * Total analysis performed in 179 ms. 15.95/5.02 15.95/5.02 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (14) 15.95/5.02 BOUNDS(1, n^1) 15.95/5.02 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (15) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 15.95/5.02 Transformed a relative TRS into a decreasing-loop problem. 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (16) 15.95/5.02 Obligation: 15.95/5.02 Analyzing the following TRS for decreasing loops: 15.95/5.02 15.95/5.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 15.95/5.02 15.95/5.02 15.95/5.02 The TRS R consists of the following rules: 15.95/5.02 15.95/5.02 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](<(x', x), Cons(x', Cons(x, xs))) 15.95/5.02 ordered(Cons(x, Nil)) -> True 15.95/5.02 ordered(Nil) -> True 15.95/5.02 notEmpty(Cons(x, xs)) -> True 15.95/5.02 notEmpty(Nil) -> False 15.95/5.02 goal(xs) -> ordered(xs) 15.95/5.02 15.95/5.02 The (relative) TRS S consists of the following rules: 15.95/5.02 15.95/5.02 <(S(x), S(y)) -> <(x, y) 15.95/5.02 <(0, S(y)) -> True 15.95/5.02 <(x, 0) -> False 15.95/5.02 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) 15.95/5.02 ordered[Ite](False, xs) -> False 15.95/5.02 15.95/5.02 Rewrite Strategy: INNERMOST 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (17) DecreasingLoopProof (LOWER BOUND(ID)) 15.95/5.02 The following loop(s) give(s) rise to the lower bound Omega(n^1): 15.95/5.02 15.95/5.02 The rewrite sequence 15.95/5.02 15.95/5.02 ordered(Cons(0, Cons(S(y1_0), xs))) ->^+ ordered(xs) 15.95/5.02 15.95/5.02 gives rise to a decreasing loop by considering the right hand sides subterm at position []. 15.95/5.02 15.95/5.02 The pumping substitution is [xs / Cons(0, Cons(S(y1_0), xs))]. 15.95/5.02 15.95/5.02 The result substitution is [ ]. 15.95/5.02 15.95/5.02 15.95/5.02 15.95/5.02 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (18) 15.95/5.02 Complex Obligation (BEST) 15.95/5.02 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (19) 15.95/5.02 Obligation: 15.95/5.02 Proved the lower bound n^1 for the following obligation: 15.95/5.02 15.95/5.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 15.95/5.02 15.95/5.02 15.95/5.02 The TRS R consists of the following rules: 15.95/5.02 15.95/5.02 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](<(x', x), Cons(x', Cons(x, xs))) 15.95/5.02 ordered(Cons(x, Nil)) -> True 15.95/5.02 ordered(Nil) -> True 15.95/5.02 notEmpty(Cons(x, xs)) -> True 15.95/5.02 notEmpty(Nil) -> False 15.95/5.02 goal(xs) -> ordered(xs) 15.95/5.02 15.95/5.02 The (relative) TRS S consists of the following rules: 15.95/5.02 15.95/5.02 <(S(x), S(y)) -> <(x, y) 15.95/5.02 <(0, S(y)) -> True 15.95/5.02 <(x, 0) -> False 15.95/5.02 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) 15.95/5.02 ordered[Ite](False, xs) -> False 15.95/5.02 15.95/5.02 Rewrite Strategy: INNERMOST 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (20) LowerBoundPropagationProof (FINISHED) 15.95/5.02 Propagated lower bound. 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (21) 15.95/5.02 BOUNDS(n^1, INF) 15.95/5.02 15.95/5.02 ---------------------------------------- 15.95/5.02 15.95/5.02 (22) 15.95/5.02 Obligation: 15.95/5.02 Analyzing the following TRS for decreasing loops: 15.95/5.02 15.95/5.02 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 15.95/5.02 15.95/5.02 15.95/5.02 The TRS R consists of the following rules: 15.95/5.02 15.95/5.02 ordered(Cons(x', Cons(x, xs))) -> ordered[Ite](<(x', x), Cons(x', Cons(x, xs))) 15.95/5.02 ordered(Cons(x, Nil)) -> True 15.95/5.02 ordered(Nil) -> True 15.95/5.02 notEmpty(Cons(x, xs)) -> True 15.95/5.02 notEmpty(Nil) -> False 15.95/5.02 goal(xs) -> ordered(xs) 15.95/5.02 15.95/5.02 The (relative) TRS S consists of the following rules: 15.95/5.02 15.95/5.02 <(S(x), S(y)) -> <(x, y) 15.95/5.02 <(0, S(y)) -> True 15.95/5.02 <(x, 0) -> False 15.95/5.02 ordered[Ite](True, Cons(x', Cons(x, xs))) -> ordered(xs) 15.95/5.02 ordered[Ite](False, xs) -> False 15.95/5.02 15.95/5.02 Rewrite Strategy: INNERMOST 16.39/5.07 EOF