31.32/9.17 WORST_CASE(Omega(n^1), O(n^1)) 31.56/9.19 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 31.56/9.19 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 31.56/9.19 31.56/9.19 31.56/9.19 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 31.56/9.19 31.56/9.19 (0) CpxRelTRS 31.56/9.19 (1) STerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 180 ms] 31.56/9.19 (2) CpxRelTRS 31.56/9.19 (3) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 31.56/9.19 (4) CpxWeightedTrs 31.56/9.19 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 31.56/9.19 (6) CpxTypedWeightedTrs 31.56/9.19 (7) CompletionProof [UPPER BOUND(ID), 0 ms] 31.56/9.19 (8) CpxTypedWeightedCompleteTrs 31.56/9.19 (9) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] 31.56/9.19 (10) CpxRNTS 31.56/9.19 (11) CompleteCoflocoProof [FINISHED, 539 ms] 31.56/9.19 (12) BOUNDS(1, n^1) 31.56/9.19 (13) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 31.56/9.19 (14) CpxRelTRS 31.56/9.19 (15) SlicingProof [LOWER BOUND(ID), 0 ms] 31.56/9.19 (16) CpxRelTRS 31.56/9.19 (17) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 31.56/9.19 (18) typed CpxTrs 31.56/9.19 (19) OrderProof [LOWER BOUND(ID), 0 ms] 31.56/9.19 (20) typed CpxTrs 31.56/9.19 (21) RewriteLemmaProof [LOWER BOUND(ID), 260 ms] 31.56/9.19 (22) BEST 31.56/9.19 (23) proven lower bound 31.56/9.19 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 31.56/9.19 (25) BOUNDS(n^1, INF) 31.56/9.19 (26) typed CpxTrs 31.56/9.19 (27) RewriteLemmaProof [LOWER BOUND(ID), 71 ms] 31.56/9.19 (28) typed CpxTrs 31.56/9.19 (29) RewriteLemmaProof [LOWER BOUND(ID), 62 ms] 31.56/9.19 (30) BOUNDS(1, INF) 31.56/9.19 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (0) 31.56/9.19 Obligation: 31.56/9.19 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 31.56/9.19 31.56/9.19 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 notEmpty(Cons(x, xs)) -> True 31.56/9.19 notEmpty(Nil) -> False 31.56/9.19 lt0(x, Nil) -> False 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.19 31.56/9.19 The (relative) TRS S consists of the following rules: 31.56/9.19 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (1) STerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) 31.56/9.19 proved termination of relative rules 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (2) 31.56/9.19 Obligation: 31.56/9.19 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). 31.56/9.19 31.56/9.19 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 notEmpty(Cons(x, xs)) -> True 31.56/9.19 notEmpty(Nil) -> False 31.56/9.19 lt0(x, Nil) -> False 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.19 31.56/9.19 The (relative) TRS S consists of the following rules: 31.56/9.19 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (3) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 31.56/9.19 Transformed relative TRS to weighted TRS 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (4) 31.56/9.19 Obligation: 31.56/9.19 The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). 31.56/9.19 31.56/9.19 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True [1] 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) [1] 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 notEmpty(Cons(x, xs)) -> True [1] 31.56/9.19 notEmpty(Nil) -> False [1] 31.56/9.19 lt0(x, Nil) -> False [1] 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1] 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1] 31.56/9.19 number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) [1] 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) [0] 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) [0] 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) [0] 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) [0] 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 31.56/9.19 Infered types. 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (6) 31.56/9.19 Obligation: 31.56/9.19 Runtime Complexity Weighted TRS with Types. 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True [1] 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) [1] 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 notEmpty(Cons(x, xs)) -> True [1] 31.56/9.19 notEmpty(Nil) -> False [1] 31.56/9.19 lt0(x, Nil) -> False [1] 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1] 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1] 31.56/9.19 number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) [1] 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) [0] 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) [0] 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) [0] 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) [0] 31.56/9.19 31.56/9.19 The TRS has the following type information: 31.56/9.19 lt0 :: Nil:Cons -> Nil:Cons -> True:False 31.56/9.19 Nil :: Nil:Cons 31.56/9.19 Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 True :: True:False 31.56/9.19 g :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 f :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 notEmpty :: Nil:Cons -> True:False 31.56/9.19 False :: True:False 31.56/9.19 g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 number4 :: a -> Nil:Cons 31.56/9.19 goal :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (7) CompletionProof (UPPER BOUND(ID)) 31.56/9.19 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 31.56/9.19 31.56/9.19 g[Ite][False][Ite](v0, v1, v2) -> null_g[Ite][False][Ite] [0] 31.56/9.19 f[Ite][False][Ite](v0, v1, v2) -> null_f[Ite][False][Ite] [0] 31.56/9.19 lt0(v0, v1) -> null_lt0 [0] 31.56/9.19 g(v0, v1) -> null_g [0] 31.56/9.19 f(v0, v1) -> null_f [0] 31.56/9.19 notEmpty(v0) -> null_notEmpty [0] 31.56/9.19 31.56/9.19 And the following fresh constants: null_g[Ite][False][Ite], null_f[Ite][False][Ite], null_lt0, null_g, null_f, null_notEmpty, const 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (8) 31.56/9.19 Obligation: 31.56/9.19 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 31.56/9.19 31.56/9.19 Runtime Complexity Weighted TRS with Types. 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True [1] 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) [1] 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 notEmpty(Cons(x, xs)) -> True [1] 31.56/9.19 notEmpty(Nil) -> False [1] 31.56/9.19 lt0(x, Nil) -> False [1] 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1] 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) [1] 31.56/9.19 number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) [1] 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) [1] 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) [0] 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) [0] 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) [0] 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) [0] 31.56/9.19 g[Ite][False][Ite](v0, v1, v2) -> null_g[Ite][False][Ite] [0] 31.56/9.19 f[Ite][False][Ite](v0, v1, v2) -> null_f[Ite][False][Ite] [0] 31.56/9.19 lt0(v0, v1) -> null_lt0 [0] 31.56/9.19 g(v0, v1) -> null_g [0] 31.56/9.19 f(v0, v1) -> null_f [0] 31.56/9.19 notEmpty(v0) -> null_notEmpty [0] 31.56/9.19 31.56/9.19 The TRS has the following type information: 31.56/9.19 lt0 :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> True:False:null_lt0:null_notEmpty 31.56/9.19 Nil :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 Cons :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 True :: True:False:null_lt0:null_notEmpty 31.56/9.19 g :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 f :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 notEmpty :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> True:False:null_lt0:null_notEmpty 31.56/9.19 False :: True:False:null_lt0:null_notEmpty 31.56/9.19 g[Ite][False][Ite] :: True:False:null_lt0:null_notEmpty -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 f[Ite][False][Ite] :: True:False:null_lt0:null_notEmpty -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 number4 :: a -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 goal :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f -> Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 null_g[Ite][False][Ite] :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 null_f[Ite][False][Ite] :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 null_lt0 :: True:False:null_lt0:null_notEmpty 31.56/9.19 null_g :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 null_f :: Nil:Cons:null_g[Ite][False][Ite]:null_f[Ite][False][Ite]:null_g:null_f 31.56/9.19 null_notEmpty :: True:False:null_lt0:null_notEmpty 31.56/9.19 const :: a 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (9) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) 31.56/9.19 Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. 31.56/9.19 The constant constructors are abstracted as follows: 31.56/9.19 31.56/9.19 Nil => 0 31.56/9.19 True => 2 31.56/9.19 False => 1 31.56/9.19 null_g[Ite][False][Ite] => 0 31.56/9.19 null_f[Ite][False][Ite] => 0 31.56/9.19 null_lt0 => 0 31.56/9.19 null_g => 0 31.56/9.19 null_f => 0 31.56/9.19 null_notEmpty => 0 31.56/9.19 const => 0 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (10) 31.56/9.19 Obligation: 31.56/9.19 Complexity RNTS consisting of the following rules: 31.56/9.19 31.56/9.19 f(z, z') -{ 1 }-> f[Ite][False][Ite](lt0(x, 1 + 0 + 0), x, 1 + x' + xs) :|: xs >= 0, z' = 1 + x' + xs, x >= 0, x' >= 0, z = x 31.56/9.19 f(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 31.56/9.19 f(z, z') -{ 1 }-> 1 + 0 + (1 + 0 + (1 + 0 + (1 + 0 + 0))) :|: x >= 0, z = x, z' = 0 31.56/9.19 f[Ite][False][Ite](z, z', z'') -{ 0 }-> f(x', xs) :|: z = 2, z' = x', xs >= 0, x' >= 0, x >= 0, z'' = 1 + x + xs 31.56/9.19 f[Ite][False][Ite](z, z', z'') -{ 0 }-> f(xs, 1 + (1 + 0 + 0) + y) :|: xs >= 0, z' = 1 + x + xs, z'' = y, z = 1, x >= 0, y >= 0 31.56/9.19 f[Ite][False][Ite](z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 31.56/9.19 g(z, z') -{ 1 }-> g[Ite][False][Ite](lt0(x, 1 + 0 + 0), x, 1 + x' + xs) :|: xs >= 0, z' = 1 + x' + xs, x >= 0, x' >= 0, z = x 31.56/9.19 g(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 31.56/9.19 g(z, z') -{ 1 }-> 1 + 0 + (1 + 0 + (1 + 0 + (1 + 0 + 0))) :|: x >= 0, z = x, z' = 0 31.56/9.19 g[Ite][False][Ite](z, z', z'') -{ 0 }-> g(x', xs) :|: z = 2, z' = x', xs >= 0, x' >= 0, x >= 0, z'' = 1 + x + xs 31.56/9.19 g[Ite][False][Ite](z, z', z'') -{ 0 }-> g(xs, 1 + (1 + 0 + 0) + y) :|: xs >= 0, z' = 1 + x + xs, z'' = y, z = 1, x >= 0, y >= 0 31.56/9.19 g[Ite][False][Ite](z, z', z'') -{ 0 }-> 0 :|: v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0 31.56/9.19 goal(z, z') -{ 1 }-> 1 + f(x, y) + (1 + g(x, y) + 0) :|: x >= 0, y >= 0, z = x, z' = y 31.56/9.19 lt0(z, z') -{ 1 }-> lt0(xs', xs) :|: xs >= 0, z' = 1 + x + xs, x' >= 0, xs' >= 0, x >= 0, z = 1 + x' + xs' 31.56/9.19 lt0(z, z') -{ 1 }-> 2 :|: xs >= 0, z' = 1 + x' + xs, x' >= 0, z = 0 31.56/9.19 lt0(z, z') -{ 1 }-> 1 :|: x >= 0, z = x, z' = 0 31.56/9.19 lt0(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 31.56/9.19 notEmpty(z) -{ 1 }-> 2 :|: z = 1 + x + xs, xs >= 0, x >= 0 31.56/9.19 notEmpty(z) -{ 1 }-> 1 :|: z = 0 31.56/9.19 notEmpty(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 31.56/9.19 number4(z) -{ 1 }-> 1 + 0 + (1 + 0 + (1 + 0 + (1 + 0 + 0))) :|: n >= 0, z = n 31.56/9.19 31.56/9.19 Only complete derivations are relevant for the runtime complexity. 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (11) CompleteCoflocoProof (FINISHED) 31.56/9.19 Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: 31.56/9.19 31.56/9.19 eq(start(V1, V, V22),0,[lt0(V1, V, Out)],[V1 >= 0,V >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[g(V1, V, Out)],[V1 >= 0,V >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[f(V1, V, Out)],[V1 >= 0,V >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[notEmpty(V1, Out)],[V1 >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[number4(V1, Out)],[V1 >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[goal(V1, V, Out)],[V1 >= 0,V >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[fun(V1, V, V22, Out)],[V1 >= 0,V >= 0,V22 >= 0]). 31.56/9.19 eq(start(V1, V, V22),0,[fun1(V1, V, V22, Out)],[V1 >= 0,V >= 0,V22 >= 0]). 31.56/9.19 eq(lt0(V1, V, Out),1,[],[Out = 2,V2 >= 0,V = 1 + V2 + V3,V3 >= 0,V1 = 0]). 31.56/9.19 eq(lt0(V1, V, Out),1,[lt0(V4, V5, Ret)],[Out = Ret,V5 >= 0,V = 1 + V5 + V6,V7 >= 0,V4 >= 0,V6 >= 0,V1 = 1 + V4 + V7]). 31.56/9.19 eq(g(V1, V, Out),1,[],[Out = 4,V8 >= 0,V1 = V8,V = 0]). 31.56/9.19 eq(f(V1, V, Out),1,[],[Out = 4,V9 >= 0,V1 = V9,V = 0]). 31.56/9.19 eq(notEmpty(V1, Out),1,[],[Out = 2,V1 = 1 + V10 + V11,V11 >= 0,V10 >= 0]). 31.56/9.19 eq(notEmpty(V1, Out),1,[],[Out = 1,V1 = 0]). 31.56/9.19 eq(lt0(V1, V, Out),1,[],[Out = 1,V12 >= 0,V1 = V12,V = 0]). 31.56/9.19 eq(g(V1, V, Out),1,[lt0(V13, 1 + 0 + 0, Ret0),fun(Ret0, V13, 1 + V15 + V14, Ret1)],[Out = Ret1,V14 >= 0,V = 1 + V14 + V15,V13 >= 0,V15 >= 0,V1 = V13]). 31.56/9.19 eq(f(V1, V, Out),1,[lt0(V17, 1 + 0 + 0, Ret01),fun1(Ret01, V17, 1 + V18 + V16, Ret2)],[Out = Ret2,V16 >= 0,V = 1 + V16 + V18,V17 >= 0,V18 >= 0,V1 = V17]). 31.56/9.19 eq(number4(V1, Out),1,[],[Out = 4,V19 >= 0,V1 = V19]). 31.56/9.19 eq(goal(V1, V, Out),1,[f(V20, V21, Ret011),g(V20, V21, Ret101)],[Out = 2 + Ret011 + Ret101,V20 >= 0,V21 >= 0,V1 = V20,V = V21]). 31.56/9.19 eq(fun(V1, V, V22, Out),0,[g(V23, 1 + (1 + 0 + 0) + V25, Ret3)],[Out = Ret3,V23 >= 0,V = 1 + V23 + V24,V22 = V25,V1 = 1,V24 >= 0,V25 >= 0]). 31.56/9.19 eq(fun(V1, V, V22, Out),0,[g(V27, V26, Ret4)],[Out = Ret4,V1 = 2,V = V27,V26 >= 0,V27 >= 0,V28 >= 0,V22 = 1 + V26 + V28]). 31.56/9.19 eq(fun1(V1, V, V22, Out),0,[f(V30, 1 + (1 + 0 + 0) + V29, Ret5)],[Out = Ret5,V30 >= 0,V = 1 + V30 + V31,V22 = V29,V1 = 1,V31 >= 0,V29 >= 0]). 31.56/9.19 eq(fun1(V1, V, V22, Out),0,[f(V33, V32, Ret6)],[Out = Ret6,V1 = 2,V = V33,V32 >= 0,V33 >= 0,V34 >= 0,V22 = 1 + V32 + V34]). 31.56/9.19 eq(fun(V1, V, V22, Out),0,[],[Out = 0,V36 >= 0,V22 = V37,V35 >= 0,V1 = V36,V = V35,V37 >= 0]). 31.56/9.19 eq(fun1(V1, V, V22, Out),0,[],[Out = 0,V40 >= 0,V22 = V38,V39 >= 0,V1 = V40,V = V39,V38 >= 0]). 31.56/9.19 eq(lt0(V1, V, Out),0,[],[Out = 0,V42 >= 0,V41 >= 0,V1 = V42,V = V41]). 31.56/9.19 eq(g(V1, V, Out),0,[],[Out = 0,V43 >= 0,V44 >= 0,V1 = V43,V = V44]). 31.56/9.19 eq(f(V1, V, Out),0,[],[Out = 0,V46 >= 0,V45 >= 0,V1 = V46,V = V45]). 31.56/9.19 eq(notEmpty(V1, Out),0,[],[Out = 0,V47 >= 0,V1 = V47]). 31.56/9.19 input_output_vars(lt0(V1,V,Out),[V1,V],[Out]). 31.56/9.19 input_output_vars(g(V1,V,Out),[V1,V],[Out]). 31.56/9.19 input_output_vars(f(V1,V,Out),[V1,V],[Out]). 31.56/9.19 input_output_vars(notEmpty(V1,Out),[V1],[Out]). 31.56/9.19 input_output_vars(number4(V1,Out),[V1],[Out]). 31.56/9.19 input_output_vars(goal(V1,V,Out),[V1,V],[Out]). 31.56/9.19 input_output_vars(fun(V1,V,V22,Out),[V1,V,V22],[Out]). 31.56/9.19 input_output_vars(fun1(V1,V,V22,Out),[V1,V,V22],[Out]). 31.56/9.19 31.56/9.19 31.56/9.19 CoFloCo proof output: 31.56/9.19 Preprocessing Cost Relations 31.56/9.19 ===================================== 31.56/9.19 31.56/9.19 #### Computed strongly connected components 31.56/9.19 0. recursive : [lt0/3] 31.56/9.19 1. recursive : [f/3,fun1/4] 31.56/9.19 2. recursive : [fun/4,g/3] 31.56/9.19 3. non_recursive : [goal/3] 31.56/9.19 4. non_recursive : [notEmpty/2] 31.56/9.19 5. non_recursive : [number4/2] 31.56/9.19 6. non_recursive : [start/3] 31.56/9.19 31.56/9.19 #### Obtained direct recursion through partial evaluation 31.56/9.19 0. SCC is partially evaluated into lt0/3 31.56/9.19 1. SCC is partially evaluated into f/3 31.56/9.19 2. SCC is partially evaluated into g/3 31.56/9.19 3. SCC is partially evaluated into goal/3 31.56/9.19 4. SCC is partially evaluated into notEmpty/2 31.56/9.19 5. SCC is completely evaluated into other SCCs 31.56/9.19 6. SCC is partially evaluated into start/3 31.56/9.19 31.56/9.19 Control-Flow Refinement of Cost Relations 31.56/9.19 ===================================== 31.56/9.19 31.56/9.19 ### Specialization of cost equations lt0/3 31.56/9.19 * CE 25 is refined into CE [30] 31.56/9.19 * CE 24 is refined into CE [31] 31.56/9.19 * CE 22 is refined into CE [32] 31.56/9.19 * CE 23 is refined into CE [33] 31.56/9.19 31.56/9.19 31.56/9.19 ### Cost equations --> "Loop" of lt0/3 31.56/9.19 * CEs [33] --> Loop 19 31.56/9.19 * CEs [30] --> Loop 20 31.56/9.19 * CEs [31] --> Loop 21 31.56/9.19 * CEs [32] --> Loop 22 31.56/9.19 31.56/9.19 ### Ranking functions of CR lt0(V1,V,Out) 31.56/9.19 * RF of phase [19]: [V,V1] 31.56/9.19 31.56/9.19 #### Partial ranking functions of CR lt0(V1,V,Out) 31.56/9.19 * Partial RF of phase [19]: 31.56/9.19 - RF of loop [19:1]: 31.56/9.19 V 31.56/9.19 V1 31.56/9.19 31.56/9.19 31.56/9.19 ### Specialization of cost equations f/3 31.56/9.19 * CE 17 is refined into CE [34,35,36] 31.56/9.19 * CE 21 is refined into CE [37] 31.56/9.19 * CE 20 is refined into CE [38] 31.56/9.19 * CE 19 is refined into CE [39] 31.56/9.19 * CE 18 is refined into CE [40] 31.56/9.19 31.56/9.19 31.56/9.19 ### Cost equations --> "Loop" of f/3 31.56/9.19 * CEs [39] --> Loop 23 31.56/9.19 * CEs [40] --> Loop 24 31.56/9.19 * CEs [38] --> Loop 25 31.56/9.19 * CEs [34,35,36,37] --> Loop 26 31.56/9.19 31.56/9.19 ### Ranking functions of CR f(V1,V,Out) 31.56/9.19 * RF of phase [23]: [V1] 31.56/9.19 * RF of phase [24]: [V] 31.56/9.19 31.56/9.19 #### Partial ranking functions of CR f(V1,V,Out) 31.56/9.19 * Partial RF of phase [23]: 31.56/9.19 - RF of loop [23:1]: 31.56/9.19 V1 31.56/9.19 * Partial RF of phase [24]: 31.56/9.19 - RF of loop [24:1]: 31.56/9.19 V 31.56/9.19 31.56/9.19 31.56/9.19 ### Specialization of cost equations g/3 31.56/9.19 * CE 12 is refined into CE [41,42,43] 31.56/9.19 * CE 16 is refined into CE [44] 31.56/9.19 * CE 15 is refined into CE [45] 31.56/9.19 * CE 14 is refined into CE [46] 31.56/9.19 * CE 13 is refined into CE [47] 31.56/9.19 31.56/9.19 31.56/9.19 ### Cost equations --> "Loop" of g/3 31.56/9.19 * CEs [46] --> Loop 27 31.56/9.19 * CEs [47] --> Loop 28 31.56/9.19 * CEs [45] --> Loop 29 31.56/9.19 * CEs [41,42,43,44] --> Loop 30 31.56/9.19 31.56/9.19 ### Ranking functions of CR g(V1,V,Out) 31.56/9.19 * RF of phase [27]: [V1] 31.56/9.19 * RF of phase [28]: [V] 31.56/9.19 31.56/9.19 #### Partial ranking functions of CR g(V1,V,Out) 31.56/9.19 * Partial RF of phase [27]: 31.56/9.19 - RF of loop [27:1]: 31.56/9.19 V1 31.56/9.19 * Partial RF of phase [28]: 31.56/9.19 - RF of loop [28:1]: 31.56/9.19 V 31.56/9.19 31.56/9.19 31.56/9.19 ### Specialization of cost equations goal/3 31.56/9.19 * CE 29 is refined into CE [48,49,50,51,52,53,54,55,56,57] 31.56/9.19 31.56/9.19 31.56/9.19 ### Cost equations --> "Loop" of goal/3 31.56/9.19 * CEs [57] --> Loop 31 31.56/9.19 * CEs [51,56] --> Loop 32 31.56/9.19 * CEs [48] --> Loop 33 31.56/9.19 * CEs [55] --> Loop 34 31.56/9.19 * CEs [50,54] --> Loop 35 31.56/9.19 * CEs [53] --> Loop 36 31.56/9.19 * CEs [49,52] --> Loop 37 31.56/9.19 31.56/9.19 ### Ranking functions of CR goal(V1,V,Out) 31.56/9.19 31.56/9.19 #### Partial ranking functions of CR goal(V1,V,Out) 31.56/9.19 31.56/9.19 31.56/9.19 ### Specialization of cost equations notEmpty/2 31.56/9.19 * CE 26 is refined into CE [58] 31.56/9.19 * CE 28 is refined into CE [59] 31.56/9.19 * CE 27 is refined into CE [60] 31.56/9.19 31.56/9.19 31.56/9.19 ### Cost equations --> "Loop" of notEmpty/2 31.56/9.19 * CEs [58] --> Loop 38 31.56/9.19 * CEs [59] --> Loop 39 31.56/9.19 * CEs [60] --> Loop 40 31.56/9.19 31.56/9.19 ### Ranking functions of CR notEmpty(V1,Out) 31.56/9.19 31.56/9.19 #### Partial ranking functions of CR notEmpty(V1,Out) 31.56/9.19 31.56/9.19 31.56/9.19 ### Specialization of cost equations start/3 31.56/9.19 * CE 2 is refined into CE [61,62,63,64] 31.56/9.19 * CE 4 is refined into CE [65,66,67,68] 31.56/9.19 * CE 1 is refined into CE [69] 31.56/9.19 * CE 3 is refined into CE [70,71,72] 31.56/9.19 * CE 5 is refined into CE [73,74,75] 31.56/9.19 * CE 6 is refined into CE [76,77,78,79,80] 31.56/9.19 * CE 7 is refined into CE [81,82,83,84] 31.56/9.19 * CE 8 is refined into CE [85,86,87,88] 31.56/9.19 * CE 9 is refined into CE [89,90,91] 31.56/9.19 * CE 10 is refined into CE [92] 31.56/9.19 * CE 11 is refined into CE [93,94,95,96,97,98,99] 31.56/9.19 31.56/9.19 31.56/9.19 ### Cost equations --> "Loop" of start/3 31.56/9.19 * CEs [77,83,87,95,96] --> Loop 41 31.56/9.19 * CEs [61,62,63,64,65,66,67,68] --> Loop 42 31.56/9.19 * CEs [70,71,72,73,74,75] --> Loop 43 31.56/9.19 * CEs [69,76,78,79,80,81,82,84,85,86,88,89,90,91,92,93,94,97,98,99] --> Loop 44 31.56/9.19 31.56/9.19 ### Ranking functions of CR start(V1,V,V22) 31.56/9.19 31.56/9.19 #### Partial ranking functions of CR start(V1,V,V22) 31.56/9.19 31.56/9.19 31.56/9.19 Computing Bounds 31.56/9.19 ===================================== 31.56/9.19 31.56/9.19 #### Cost of chains of lt0(V1,V,Out): 31.56/9.19 * Chain [[19],22]: 1*it(19)+1 31.56/9.19 Such that:it(19) =< V 31.56/9.19 31.56/9.19 with precondition: [Out=2,V1>=1,V>=2] 31.56/9.19 31.56/9.19 * Chain [[19],21]: 1*it(19)+1 31.56/9.19 Such that:it(19) =< V 31.56/9.19 31.56/9.19 with precondition: [Out=1,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [[19],20]: 1*it(19)+0 31.56/9.19 Such that:it(19) =< V 31.56/9.19 31.56/9.19 with precondition: [Out=0,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [22]: 1 31.56/9.19 with precondition: [V1=0,Out=2,V>=1] 31.56/9.19 31.56/9.19 * Chain [21]: 1 31.56/9.19 with precondition: [V=0,Out=1,V1>=0] 31.56/9.19 31.56/9.19 * Chain [20]: 0 31.56/9.19 with precondition: [Out=0,V1>=0,V>=0] 31.56/9.19 31.56/9.19 31.56/9.19 #### Cost of chains of f(V1,V,Out): 31.56/9.19 * Chain [[24],26]: 2*it(24)+4 31.56/9.19 Such that:it(24) =< V 31.56/9.19 31.56/9.19 with precondition: [V1=0,Out=0,V>=1] 31.56/9.19 31.56/9.19 * Chain [[24],25]: 2*it(24)+1 31.56/9.19 Such that:it(24) =< V 31.56/9.19 31.56/9.19 with precondition: [V1=0,Out=4,V>=1] 31.56/9.19 31.56/9.19 * Chain [[23],[24],26]: 3*it(23)+2*it(24)+4 31.56/9.19 Such that:it(24) =< 2*V1+V 31.56/9.19 aux(5) =< V1 31.56/9.19 it(23) =< aux(5) 31.56/9.19 31.56/9.19 with precondition: [Out=0,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [[23],[24],25]: 3*it(23)+2*it(24)+1 31.56/9.19 Such that:it(24) =< 2*V1+V 31.56/9.19 aux(6) =< V1 31.56/9.19 it(23) =< aux(6) 31.56/9.19 31.56/9.19 with precondition: [Out=4,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [[23],26]: 3*it(23)+4 31.56/9.19 Such that:aux(7) =< V1 31.56/9.19 it(23) =< aux(7) 31.56/9.19 31.56/9.19 with precondition: [Out=0,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [26]: 4 31.56/9.19 with precondition: [Out=0,V1>=0,V>=0] 31.56/9.19 31.56/9.19 * Chain [25]: 1 31.56/9.19 with precondition: [V=0,Out=4,V1>=0] 31.56/9.19 31.56/9.19 31.56/9.19 #### Cost of chains of g(V1,V,Out): 31.56/9.19 * Chain [[28],30]: 2*it(28)+4 31.56/9.19 Such that:it(28) =< V 31.56/9.19 31.56/9.19 with precondition: [V1=0,Out=0,V>=1] 31.56/9.19 31.56/9.19 * Chain [[28],29]: 2*it(28)+1 31.56/9.19 Such that:it(28) =< V 31.56/9.19 31.56/9.19 with precondition: [V1=0,Out=4,V>=1] 31.56/9.19 31.56/9.19 * Chain [[27],[28],30]: 3*it(27)+2*it(28)+4 31.56/9.19 Such that:it(28) =< 2*V1+V 31.56/9.19 aux(13) =< V1 31.56/9.19 it(27) =< aux(13) 31.56/9.19 31.56/9.19 with precondition: [Out=0,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [[27],[28],29]: 3*it(27)+2*it(28)+1 31.56/9.19 Such that:it(28) =< 2*V1+V 31.56/9.19 aux(14) =< V1 31.56/9.19 it(27) =< aux(14) 31.56/9.19 31.56/9.19 with precondition: [Out=4,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [[27],30]: 3*it(27)+4 31.56/9.19 Such that:aux(15) =< V1 31.56/9.19 it(27) =< aux(15) 31.56/9.19 31.56/9.19 with precondition: [Out=0,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [30]: 4 31.56/9.19 with precondition: [Out=0,V1>=0,V>=0] 31.56/9.19 31.56/9.19 * Chain [29]: 1 31.56/9.19 with precondition: [V=0,Out=4,V1>=0] 31.56/9.19 31.56/9.19 31.56/9.19 #### Cost of chains of goal(V1,V,Out): 31.56/9.19 * Chain [37]: 12*s(24)+6 31.56/9.19 Such that:aux(19) =< V 31.56/9.19 s(24) =< aux(19) 31.56/9.19 31.56/9.19 with precondition: [V1=0,Out=6,V>=1] 31.56/9.19 31.56/9.19 * Chain [36]: 4*s(34)+3 31.56/9.19 Such that:aux(20) =< V 31.56/9.19 s(34) =< aux(20) 31.56/9.19 31.56/9.19 with precondition: [V1=0,Out=10,V>=1] 31.56/9.19 31.56/9.19 * Chain [35]: 4*s(36)+12*s(39)+6 31.56/9.19 Such that:aux(21) =< V1 31.56/9.19 aux(22) =< 2*V1 31.56/9.19 s(36) =< aux(22) 31.56/9.19 s(39) =< aux(21) 31.56/9.19 31.56/9.19 with precondition: [V=0,Out=6,V1>=0] 31.56/9.19 31.56/9.19 * Chain [34]: 3 31.56/9.19 with precondition: [V=0,Out=10,V1>=0] 31.56/9.19 31.56/9.19 * Chain [33]: 4*s(44)+4*s(45)+12*s(47)+9 31.56/9.19 Such that:aux(23) =< V1 31.56/9.19 aux(24) =< 2*V1+V 31.56/9.19 aux(25) =< V 31.56/9.19 s(44) =< aux(24) 31.56/9.19 s(45) =< aux(25) 31.56/9.19 s(47) =< aux(23) 31.56/9.19 31.56/9.19 with precondition: [Out=2,V1>=0,V>=0] 31.56/9.19 31.56/9.19 * Chain [32]: 8*s(52)+4*s(53)+18*s(55)+6 31.56/9.19 Such that:aux(30) =< V1 31.56/9.19 aux(31) =< 2*V1+V 31.56/9.19 aux(32) =< V 31.56/9.19 s(53) =< aux(32) 31.56/9.19 s(52) =< aux(31) 31.56/9.19 s(55) =< aux(30) 31.56/9.19 31.56/9.19 with precondition: [Out=6,V1>=1,V>=1] 31.56/9.19 31.56/9.19 * Chain [31]: 4*s(66)+6*s(68)+3 31.56/9.19 Such that:aux(33) =< V1 31.56/9.19 aux(34) =< 2*V1+V 31.56/9.19 s(66) =< aux(34) 31.56/9.19 s(68) =< aux(33) 31.56/9.19 31.56/9.19 with precondition: [Out=10,V1>=1,V>=1] 31.56/9.19 31.56/9.19 31.56/9.19 #### Cost of chains of notEmpty(V1,Out): 31.56/9.19 * Chain [40]: 1 31.56/9.19 with precondition: [V1=0,Out=1] 31.56/9.19 31.56/9.19 * Chain [39]: 0 31.56/9.19 with precondition: [Out=0,V1>=0] 31.56/9.19 31.56/9.19 * Chain [38]: 1 31.56/9.19 with precondition: [Out=2,V1>=1] 31.56/9.19 31.56/9.19 31.56/9.19 #### Cost of chains of start(V1,V,V22): 31.56/9.19 * Chain [44]: 35*s(72)+24*s(75)+54*s(78)+9 31.56/9.19 Such that:aux(35) =< V1 31.56/9.19 aux(36) =< 2*V1+V 31.56/9.19 aux(37) =< V 31.56/9.19 s(75) =< aux(36) 31.56/9.19 s(72) =< aux(37) 31.56/9.19 s(78) =< aux(35) 31.56/9.19 31.56/9.19 with precondition: [V1>=0] 31.56/9.19 31.56/9.19 * Chain [43]: 8*s(111)+8*s(112)+18*s(114)+4 31.56/9.19 Such that:aux(38) =< V 31.56/9.19 aux(39) =< 2*V+V22 31.56/9.19 aux(40) =< V22+2 31.56/9.19 s(111) =< aux(39) 31.56/9.19 s(112) =< aux(40) 31.56/9.19 s(114) =< aux(38) 31.56/9.19 31.56/9.19 with precondition: [V1=1,V>=1,V22>=0] 31.56/9.19 31.56/9.19 * Chain [42]: 8*s(127)+8*s(128)+18*s(130)+4 31.56/9.19 Such that:aux(41) =< V 31.56/9.19 aux(42) =< 2*V+V22 31.56/9.19 aux(43) =< V22 31.56/9.19 s(127) =< aux(42) 31.56/9.19 s(128) =< aux(43) 31.56/9.19 s(130) =< aux(41) 31.56/9.19 31.56/9.19 with precondition: [V1=2,V>=0,V22>=1] 31.56/9.19 31.56/9.19 * Chain [41]: 4*s(145)+12*s(146)+6 31.56/9.19 Such that:s(143) =< V1 31.56/9.19 s(144) =< 2*V1 31.56/9.19 s(145) =< s(144) 31.56/9.19 s(146) =< s(143) 31.56/9.19 31.56/9.19 with precondition: [V=0,V1>=0] 31.56/9.19 31.56/9.19 31.56/9.19 Closed-form bounds of start(V1,V,V22): 31.56/9.19 ------------------------------------- 31.56/9.19 * Chain [44] with precondition: [V1>=0] 31.56/9.19 - Upper bound: 54*V1+9+nat(V)*35+nat(2*V1+V)*24 31.56/9.19 - Complexity: n 31.56/9.19 * Chain [43] with precondition: [V1=1,V>=1,V22>=0] 31.56/9.19 - Upper bound: 34*V+16*V22+20 31.56/9.19 - Complexity: n 31.56/9.19 * Chain [42] with precondition: [V1=2,V>=0,V22>=1] 31.56/9.19 - Upper bound: 34*V+16*V22+4 31.56/9.19 - Complexity: n 31.56/9.19 * Chain [41] with precondition: [V=0,V1>=0] 31.56/9.19 - Upper bound: 20*V1+6 31.56/9.19 - Complexity: n 31.56/9.19 31.56/9.19 ### Maximum cost of start(V1,V,V22): max([20*V1+2,nat(V)*18+max([nat(2*V+V22)*8+max([nat(V22)*8,nat(V22+2)*8]),54*V1+5+nat(V)*17+nat(2*V1+V)*24])])+4 31.56/9.19 Asymptotic class: n 31.56/9.19 * Total analysis performed in 462 ms. 31.56/9.19 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (12) 31.56/9.19 BOUNDS(1, n^1) 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (13) RenamingProof (BOTH BOUNDS(ID, ID)) 31.56/9.19 Renamed function symbols to avoid clashes with predefined symbol. 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (14) 31.56/9.19 Obligation: 31.56/9.19 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 31.56/9.19 31.56/9.19 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 notEmpty(Cons(x, xs)) -> True 31.56/9.19 notEmpty(Nil) -> False 31.56/9.19 lt0(x, Nil) -> False 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 number4(n) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.19 31.56/9.19 The (relative) TRS S consists of the following rules: 31.56/9.19 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (15) SlicingProof (LOWER BOUND(ID)) 31.56/9.19 Sliced the following arguments: 31.56/9.19 number4/0 31.56/9.19 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (16) 31.56/9.19 Obligation: 31.56/9.19 The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). 31.56/9.19 31.56/9.19 31.56/9.19 The TRS R consists of the following rules: 31.56/9.19 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 notEmpty(Cons(x, xs)) -> True 31.56/9.19 notEmpty(Nil) -> False 31.56/9.19 lt0(x, Nil) -> False 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.19 31.56/9.19 The (relative) TRS S consists of the following rules: 31.56/9.19 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.19 31.56/9.19 Rewrite Strategy: INNERMOST 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (17) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 31.56/9.19 Infered types. 31.56/9.19 ---------------------------------------- 31.56/9.19 31.56/9.19 (18) 31.56/9.19 Obligation: 31.56/9.19 Innermost TRS: 31.56/9.19 Rules: 31.56/9.19 lt0(Nil, Cons(x', xs)) -> True 31.56/9.19 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.19 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 notEmpty(Cons(x, xs)) -> True 31.56/9.19 notEmpty(Nil) -> False 31.56/9.19 lt0(x, Nil) -> False 31.56/9.19 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.19 number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.19 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.19 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.19 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.19 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.19 31.56/9.19 Types: 31.56/9.19 lt0 :: Nil:Cons -> Nil:Cons -> True:False 31.56/9.19 Nil :: Nil:Cons 31.56/9.19 Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 True :: True:False 31.56/9.19 g :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 f :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.19 notEmpty :: Nil:Cons -> True:False 31.56/9.19 False :: True:False 31.56/9.19 g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 number4 :: Nil:Cons 31.56/9.20 goal :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 hole_True:False1_1 :: True:False 31.56/9.20 hole_Nil:Cons2_1 :: Nil:Cons 31.56/9.20 gen_Nil:Cons3_1 :: Nat -> Nil:Cons 31.56/9.20 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (19) OrderProof (LOWER BOUND(ID)) 31.56/9.20 Heuristically decided to analyse the following defined symbols: 31.56/9.20 lt0, g, f 31.56/9.20 31.56/9.20 They will be analysed ascendingly in the following order: 31.56/9.20 lt0 < g 31.56/9.20 lt0 < f 31.56/9.20 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (20) 31.56/9.20 Obligation: 31.56/9.20 Innermost TRS: 31.56/9.20 Rules: 31.56/9.20 lt0(Nil, Cons(x', xs)) -> True 31.56/9.20 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.20 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 notEmpty(Cons(x, xs)) -> True 31.56/9.20 notEmpty(Nil) -> False 31.56/9.20 lt0(x, Nil) -> False 31.56/9.20 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.20 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.20 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.20 31.56/9.20 Types: 31.56/9.20 lt0 :: Nil:Cons -> Nil:Cons -> True:False 31.56/9.20 Nil :: Nil:Cons 31.56/9.20 Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 True :: True:False 31.56/9.20 g :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 notEmpty :: Nil:Cons -> True:False 31.56/9.20 False :: True:False 31.56/9.20 g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 number4 :: Nil:Cons 31.56/9.20 goal :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 hole_True:False1_1 :: True:False 31.56/9.20 hole_Nil:Cons2_1 :: Nil:Cons 31.56/9.20 gen_Nil:Cons3_1 :: Nat -> Nil:Cons 31.56/9.20 31.56/9.20 31.56/9.20 Generator Equations: 31.56/9.20 gen_Nil:Cons3_1(0) <=> Nil 31.56/9.20 gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x)) 31.56/9.20 31.56/9.20 31.56/9.20 The following defined symbols remain to be analysed: 31.56/9.20 lt0, g, f 31.56/9.20 31.56/9.20 They will be analysed ascendingly in the following order: 31.56/9.20 lt0 < g 31.56/9.20 lt0 < f 31.56/9.20 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (21) RewriteLemmaProof (LOWER BOUND(ID)) 31.56/9.20 Proved the following rewrite lemma: 31.56/9.20 lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) -> True, rt in Omega(1 + n5_1) 31.56/9.20 31.56/9.20 Induction Base: 31.56/9.20 lt0(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(+(1, 0))) ->_R^Omega(1) 31.56/9.20 True 31.56/9.20 31.56/9.20 Induction Step: 31.56/9.20 lt0(gen_Nil:Cons3_1(+(n5_1, 1)), gen_Nil:Cons3_1(+(1, +(n5_1, 1)))) ->_R^Omega(1) 31.56/9.20 lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) ->_IH 31.56/9.20 True 31.56/9.20 31.56/9.20 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (22) 31.56/9.20 Complex Obligation (BEST) 31.56/9.20 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (23) 31.56/9.20 Obligation: 31.56/9.20 Proved the lower bound n^1 for the following obligation: 31.56/9.20 31.56/9.20 Innermost TRS: 31.56/9.20 Rules: 31.56/9.20 lt0(Nil, Cons(x', xs)) -> True 31.56/9.20 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.20 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 notEmpty(Cons(x, xs)) -> True 31.56/9.20 notEmpty(Nil) -> False 31.56/9.20 lt0(x, Nil) -> False 31.56/9.20 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.20 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.20 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.20 31.56/9.20 Types: 31.56/9.20 lt0 :: Nil:Cons -> Nil:Cons -> True:False 31.56/9.20 Nil :: Nil:Cons 31.56/9.20 Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 True :: True:False 31.56/9.20 g :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 notEmpty :: Nil:Cons -> True:False 31.56/9.20 False :: True:False 31.56/9.20 g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 number4 :: Nil:Cons 31.56/9.20 goal :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 hole_True:False1_1 :: True:False 31.56/9.20 hole_Nil:Cons2_1 :: Nil:Cons 31.56/9.20 gen_Nil:Cons3_1 :: Nat -> Nil:Cons 31.56/9.20 31.56/9.20 31.56/9.20 Generator Equations: 31.56/9.20 gen_Nil:Cons3_1(0) <=> Nil 31.56/9.20 gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x)) 31.56/9.20 31.56/9.20 31.56/9.20 The following defined symbols remain to be analysed: 31.56/9.20 lt0, g, f 31.56/9.20 31.56/9.20 They will be analysed ascendingly in the following order: 31.56/9.20 lt0 < g 31.56/9.20 lt0 < f 31.56/9.20 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (24) LowerBoundPropagationProof (FINISHED) 31.56/9.20 Propagated lower bound. 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (25) 31.56/9.20 BOUNDS(n^1, INF) 31.56/9.20 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (26) 31.56/9.20 Obligation: 31.56/9.20 Innermost TRS: 31.56/9.20 Rules: 31.56/9.20 lt0(Nil, Cons(x', xs)) -> True 31.56/9.20 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.20 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 notEmpty(Cons(x, xs)) -> True 31.56/9.20 notEmpty(Nil) -> False 31.56/9.20 lt0(x, Nil) -> False 31.56/9.20 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.20 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.20 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.20 31.56/9.20 Types: 31.56/9.20 lt0 :: Nil:Cons -> Nil:Cons -> True:False 31.56/9.20 Nil :: Nil:Cons 31.56/9.20 Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 True :: True:False 31.56/9.20 g :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 notEmpty :: Nil:Cons -> True:False 31.56/9.20 False :: True:False 31.56/9.20 g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 number4 :: Nil:Cons 31.56/9.20 goal :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 hole_True:False1_1 :: True:False 31.56/9.20 hole_Nil:Cons2_1 :: Nil:Cons 31.56/9.20 gen_Nil:Cons3_1 :: Nat -> Nil:Cons 31.56/9.20 31.56/9.20 31.56/9.20 Lemmas: 31.56/9.20 lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) -> True, rt in Omega(1 + n5_1) 31.56/9.20 31.56/9.20 31.56/9.20 Generator Equations: 31.56/9.20 gen_Nil:Cons3_1(0) <=> Nil 31.56/9.20 gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x)) 31.56/9.20 31.56/9.20 31.56/9.20 The following defined symbols remain to be analysed: 31.56/9.20 g, f 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (27) RewriteLemmaProof (LOWER BOUND(ID)) 31.56/9.20 Proved the following rewrite lemma: 31.56/9.20 g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n359_1)) -> gen_Nil:Cons3_1(4), rt in Omega(1 + n359_1) 31.56/9.20 31.56/9.20 Induction Base: 31.56/9.20 g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(0)) ->_R^Omega(1) 31.56/9.20 Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 31.56/9.20 Induction Step: 31.56/9.20 g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(+(n359_1, 1))) ->_R^Omega(1) 31.56/9.20 g[Ite][False][Ite](lt0(gen_Nil:Cons3_1(0), Cons(Nil, Nil)), gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n359_1))) ->_L^Omega(1) 31.56/9.20 g[Ite][False][Ite](True, gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n359_1))) ->_R^Omega(0) 31.56/9.20 g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n359_1)) ->_IH 31.56/9.20 gen_Nil:Cons3_1(4) 31.56/9.20 31.56/9.20 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (28) 31.56/9.20 Obligation: 31.56/9.20 Innermost TRS: 31.56/9.20 Rules: 31.56/9.20 lt0(Nil, Cons(x', xs)) -> True 31.56/9.20 lt0(Cons(x', xs'), Cons(x, xs)) -> lt0(xs', xs) 31.56/9.20 g(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 f(x, Nil) -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 notEmpty(Cons(x, xs)) -> True 31.56/9.20 notEmpty(Nil) -> False 31.56/9.20 lt0(x, Nil) -> False 31.56/9.20 g(x, Cons(x', xs)) -> g[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 f(x, Cons(x', xs)) -> f[Ite][False][Ite](lt0(x, Cons(Nil, Nil)), x, Cons(x', xs)) 31.56/9.20 number4 -> Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 goal(x, y) -> Cons(f(x, y), Cons(g(x, y), Nil)) 31.56/9.20 g[Ite][False][Ite](False, Cons(x, xs), y) -> g(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 g[Ite][False][Ite](True, x', Cons(x, xs)) -> g(x', xs) 31.56/9.20 f[Ite][False][Ite](False, Cons(x, xs), y) -> f(xs, Cons(Cons(Nil, Nil), y)) 31.56/9.20 f[Ite][False][Ite](True, x', Cons(x, xs)) -> f(x', xs) 31.56/9.20 31.56/9.20 Types: 31.56/9.20 lt0 :: Nil:Cons -> Nil:Cons -> True:False 31.56/9.20 Nil :: Nil:Cons 31.56/9.20 Cons :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 True :: True:False 31.56/9.20 g :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 notEmpty :: Nil:Cons -> True:False 31.56/9.20 False :: True:False 31.56/9.20 g[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 f[Ite][False][Ite] :: True:False -> Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 number4 :: Nil:Cons 31.56/9.20 goal :: Nil:Cons -> Nil:Cons -> Nil:Cons 31.56/9.20 hole_True:False1_1 :: True:False 31.56/9.20 hole_Nil:Cons2_1 :: Nil:Cons 31.56/9.20 gen_Nil:Cons3_1 :: Nat -> Nil:Cons 31.56/9.20 31.56/9.20 31.56/9.20 Lemmas: 31.56/9.20 lt0(gen_Nil:Cons3_1(n5_1), gen_Nil:Cons3_1(+(1, n5_1))) -> True, rt in Omega(1 + n5_1) 31.56/9.20 g(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n359_1)) -> gen_Nil:Cons3_1(4), rt in Omega(1 + n359_1) 31.56/9.20 31.56/9.20 31.56/9.20 Generator Equations: 31.56/9.20 gen_Nil:Cons3_1(0) <=> Nil 31.56/9.20 gen_Nil:Cons3_1(+(x, 1)) <=> Cons(Nil, gen_Nil:Cons3_1(x)) 31.56/9.20 31.56/9.20 31.56/9.20 The following defined symbols remain to be analysed: 31.56/9.20 f 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (29) RewriteLemmaProof (LOWER BOUND(ID)) 31.56/9.20 Proved the following rewrite lemma: 31.56/9.20 f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n1010_1)) -> gen_Nil:Cons3_1(4), rt in Omega(1 + n1010_1) 31.56/9.20 31.56/9.20 Induction Base: 31.56/9.20 f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(0)) ->_R^Omega(1) 31.56/9.20 Cons(Nil, Cons(Nil, Cons(Nil, Cons(Nil, Nil)))) 31.56/9.20 31.56/9.20 Induction Step: 31.56/9.20 f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(+(n1010_1, 1))) ->_R^Omega(1) 31.56/9.20 f[Ite][False][Ite](lt0(gen_Nil:Cons3_1(0), Cons(Nil, Nil)), gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n1010_1))) ->_L^Omega(1) 31.56/9.20 f[Ite][False][Ite](True, gen_Nil:Cons3_1(0), Cons(Nil, gen_Nil:Cons3_1(n1010_1))) ->_R^Omega(0) 31.56/9.20 f(gen_Nil:Cons3_1(0), gen_Nil:Cons3_1(n1010_1)) ->_IH 31.56/9.20 gen_Nil:Cons3_1(4) 31.56/9.20 31.56/9.20 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 31.56/9.20 ---------------------------------------- 31.56/9.20 31.56/9.20 (30) 31.56/9.20 BOUNDS(1, INF) 31.56/9.24 EOF