940.44/291.48 WORST_CASE(Omega(n^1), ?) 940.44/291.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 940.44/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 940.44/291.49 940.44/291.49 940.44/291.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 940.44/291.49 940.44/291.49 (0) CpxTRS 940.44/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 940.44/291.49 (2) CpxTRS 940.44/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 940.44/291.49 (4) typed CpxTrs 940.44/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 940.44/291.49 (6) typed CpxTrs 940.44/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 316 ms] 940.44/291.49 (8) BEST 940.44/291.49 (9) proven lower bound 940.44/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 940.44/291.49 (11) BOUNDS(n^1, INF) 940.44/291.49 (12) typed CpxTrs 940.44/291.49 (13) RewriteLemmaProof [LOWER BOUND(ID), 107 ms] 940.44/291.49 (14) typed CpxTrs 940.44/291.49 (15) RewriteLemmaProof [LOWER BOUND(ID), 124 ms] 940.44/291.49 (16) typed CpxTrs 940.44/291.49 (17) RewriteLemmaProof [LOWER BOUND(ID), 87 ms] 940.44/291.49 (18) typed CpxTrs 940.44/291.49 (19) RewriteLemmaProof [LOWER BOUND(ID), 12 ms] 940.44/291.49 (20) BOUNDS(1, INF) 940.44/291.49 940.44/291.49 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (0) 940.44/291.49 Obligation: 940.44/291.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 940.44/291.49 940.44/291.49 940.44/291.49 The TRS R consists of the following rules: 940.44/291.49 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0, x11), 0) -> Cons(0, Cons(0, x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0) -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0, x11), M(x2)) -> Cons(0, Cons(0, x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0)) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0, x11), S(x2)) -> Cons(S(x2), Cons(0, x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.49 scanr#3(Nil) -> Cons(0, Nil) 940.44/291.49 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.49 foldl#3(x2, Nil) -> x2 940.44/291.49 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.49 minus#2(0, x16) -> 0 940.44/291.49 minus#2(S(x20), 0) -> S(x20) 940.44/291.49 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.49 plus#2(0, S(x2)) -> S(x2) 940.44/291.49 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.49 max#2(0, x8) -> x8 940.44/291.49 max#2(S(x12), 0) -> S(x12) 940.44/291.49 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.49 main(x1) -> foldl#3(0, scanr#3(x1)) 940.44/291.49 940.44/291.49 S is empty. 940.44/291.49 Rewrite Strategy: INNERMOST 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 940.44/291.49 Renamed function symbols to avoid clashes with predefined symbol. 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (2) 940.44/291.49 Obligation: 940.44/291.49 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 940.44/291.49 940.44/291.49 940.44/291.49 The TRS R consists of the following rules: 940.44/291.49 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.49 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.49 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.49 foldl#3(x2, Nil) -> x2 940.44/291.49 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.49 minus#2(0', x16) -> 0' 940.44/291.49 minus#2(S(x20), 0') -> S(x20) 940.44/291.49 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.49 plus#2(0', S(x2)) -> S(x2) 940.44/291.49 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.49 max#2(0', x8) -> x8 940.44/291.49 max#2(S(x12), 0') -> S(x12) 940.44/291.49 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.49 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.49 940.44/291.49 S is empty. 940.44/291.49 Rewrite Strategy: INNERMOST 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 940.44/291.49 Infered types. 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (4) 940.44/291.49 Obligation: 940.44/291.49 Innermost TRS: 940.44/291.49 Rules: 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.49 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.49 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.49 foldl#3(x2, Nil) -> x2 940.44/291.49 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.49 minus#2(0', x16) -> 0' 940.44/291.49 minus#2(S(x20), 0') -> S(x20) 940.44/291.49 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.49 plus#2(0', S(x2)) -> S(x2) 940.44/291.49 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.49 max#2(0', x8) -> x8 940.44/291.49 max#2(S(x12), 0') -> S(x12) 940.44/291.49 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.49 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.49 940.44/291.49 Types: 940.44/291.49 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.49 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.49 0' :: 0':S:M 940.44/291.49 S :: 0':S:M -> 0':S:M 940.44/291.49 M :: 0':S:M -> 0':S:M 940.44/291.49 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.49 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.49 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.49 Nil :: Cons:Nil 940.44/291.49 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.49 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.49 main :: Cons:Nil -> 0':S:M 940.44/291.49 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.49 hole_0':S:M2_5 :: 0':S:M 940.44/291.49 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.49 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.49 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (5) OrderProof (LOWER BOUND(ID)) 940.44/291.49 Heuristically decided to analyse the following defined symbols: 940.44/291.49 minus#2, plus#2, scanr#3, foldl#3, max#2 940.44/291.49 940.44/291.49 They will be analysed ascendingly in the following order: 940.44/291.49 max#2 < foldl#3 940.44/291.49 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (6) 940.44/291.49 Obligation: 940.44/291.49 Innermost TRS: 940.44/291.49 Rules: 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.49 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.49 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.49 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.49 foldl#3(x2, Nil) -> x2 940.44/291.49 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.49 minus#2(0', x16) -> 0' 940.44/291.49 minus#2(S(x20), 0') -> S(x20) 940.44/291.49 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.49 plus#2(0', S(x2)) -> S(x2) 940.44/291.49 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.49 max#2(0', x8) -> x8 940.44/291.49 max#2(S(x12), 0') -> S(x12) 940.44/291.49 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.49 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.49 940.44/291.49 Types: 940.44/291.49 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.49 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.49 0' :: 0':S:M 940.44/291.49 S :: 0':S:M -> 0':S:M 940.44/291.49 M :: 0':S:M -> 0':S:M 940.44/291.49 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.49 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.49 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.49 Nil :: Cons:Nil 940.44/291.49 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.49 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.49 main :: Cons:Nil -> 0':S:M 940.44/291.49 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.49 hole_0':S:M2_5 :: 0':S:M 940.44/291.49 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.49 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.49 940.44/291.49 940.44/291.49 Generator Equations: 940.44/291.49 gen_Cons:Nil3_5(0) <=> Nil 940.44/291.49 gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x)) 940.44/291.49 gen_0':S:M4_5(0) <=> 0' 940.44/291.49 gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x)) 940.44/291.49 940.44/291.49 940.44/291.49 The following defined symbols remain to be analysed: 940.44/291.49 minus#2, plus#2, scanr#3, foldl#3, max#2 940.44/291.49 940.44/291.49 They will be analysed ascendingly in the following order: 940.44/291.49 max#2 < foldl#3 940.44/291.49 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 940.44/291.49 Proved the following rewrite lemma: 940.44/291.49 minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5) 940.44/291.49 940.44/291.49 Induction Base: 940.44/291.49 minus#2(gen_0':S:M4_5(0), gen_0':S:M4_5(0)) ->_R^Omega(1) 940.44/291.49 0' 940.44/291.49 940.44/291.49 Induction Step: 940.44/291.49 minus#2(gen_0':S:M4_5(+(n6_5, 1)), gen_0':S:M4_5(+(n6_5, 1))) ->_R^Omega(1) 940.44/291.49 minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) ->_IH 940.44/291.49 gen_0':S:M4_5(0) 940.44/291.49 940.44/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 940.44/291.49 ---------------------------------------- 940.44/291.49 940.44/291.49 (8) 940.44/291.50 Complex Obligation (BEST) 940.44/291.50 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (9) 940.44/291.50 Obligation: 940.44/291.50 Proved the lower bound n^1 for the following obligation: 940.44/291.50 940.44/291.50 Innermost TRS: 940.44/291.50 Rules: 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.50 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.50 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.50 foldl#3(x2, Nil) -> x2 940.44/291.50 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.50 minus#2(0', x16) -> 0' 940.44/291.50 minus#2(S(x20), 0') -> S(x20) 940.44/291.50 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.50 plus#2(0', S(x2)) -> S(x2) 940.44/291.50 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.50 max#2(0', x8) -> x8 940.44/291.50 max#2(S(x12), 0') -> S(x12) 940.44/291.50 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.50 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.50 940.44/291.50 Types: 940.44/291.50 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.50 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.50 0' :: 0':S:M 940.44/291.50 S :: 0':S:M -> 0':S:M 940.44/291.50 M :: 0':S:M -> 0':S:M 940.44/291.50 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.50 Nil :: Cons:Nil 940.44/291.50 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.50 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 main :: Cons:Nil -> 0':S:M 940.44/291.50 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.50 hole_0':S:M2_5 :: 0':S:M 940.44/291.50 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.50 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.50 940.44/291.50 940.44/291.50 Generator Equations: 940.44/291.50 gen_Cons:Nil3_5(0) <=> Nil 940.44/291.50 gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x)) 940.44/291.50 gen_0':S:M4_5(0) <=> 0' 940.44/291.50 gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x)) 940.44/291.50 940.44/291.50 940.44/291.50 The following defined symbols remain to be analysed: 940.44/291.50 minus#2, plus#2, scanr#3, foldl#3, max#2 940.44/291.50 940.44/291.50 They will be analysed ascendingly in the following order: 940.44/291.50 max#2 < foldl#3 940.44/291.50 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (10) LowerBoundPropagationProof (FINISHED) 940.44/291.50 Propagated lower bound. 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (11) 940.44/291.50 BOUNDS(n^1, INF) 940.44/291.50 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (12) 940.44/291.50 Obligation: 940.44/291.50 Innermost TRS: 940.44/291.50 Rules: 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.50 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.50 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.50 foldl#3(x2, Nil) -> x2 940.44/291.50 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.50 minus#2(0', x16) -> 0' 940.44/291.50 minus#2(S(x20), 0') -> S(x20) 940.44/291.50 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.50 plus#2(0', S(x2)) -> S(x2) 940.44/291.50 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.50 max#2(0', x8) -> x8 940.44/291.50 max#2(S(x12), 0') -> S(x12) 940.44/291.50 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.50 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.50 940.44/291.50 Types: 940.44/291.50 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.50 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.50 0' :: 0':S:M 940.44/291.50 S :: 0':S:M -> 0':S:M 940.44/291.50 M :: 0':S:M -> 0':S:M 940.44/291.50 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.50 Nil :: Cons:Nil 940.44/291.50 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.50 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 main :: Cons:Nil -> 0':S:M 940.44/291.50 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.50 hole_0':S:M2_5 :: 0':S:M 940.44/291.50 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.50 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.50 940.44/291.50 940.44/291.50 Lemmas: 940.44/291.50 minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5) 940.44/291.50 940.44/291.50 940.44/291.50 Generator Equations: 940.44/291.50 gen_Cons:Nil3_5(0) <=> Nil 940.44/291.50 gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x)) 940.44/291.50 gen_0':S:M4_5(0) <=> 0' 940.44/291.50 gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x)) 940.44/291.50 940.44/291.50 940.44/291.50 The following defined symbols remain to be analysed: 940.44/291.50 plus#2, scanr#3, foldl#3, max#2 940.44/291.50 940.44/291.50 They will be analysed ascendingly in the following order: 940.44/291.50 max#2 < foldl#3 940.44/291.50 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (13) RewriteLemmaProof (LOWER BOUND(ID)) 940.44/291.50 Proved the following rewrite lemma: 940.44/291.50 plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5) 940.44/291.50 940.44/291.50 Induction Base: 940.44/291.50 plus#2(gen_0':S:M4_5(0), gen_0':S:M4_5(1)) ->_R^Omega(1) 940.44/291.50 S(gen_0':S:M4_5(0)) 940.44/291.50 940.44/291.50 Induction Step: 940.44/291.50 plus#2(gen_0':S:M4_5(+(n655_5, 1)), gen_0':S:M4_5(1)) ->_R^Omega(1) 940.44/291.50 S(plus#2(gen_0':S:M4_5(n655_5), S(gen_0':S:M4_5(0)))) ->_IH 940.44/291.50 S(gen_0':S:M4_5(+(1, c656_5))) 940.44/291.50 940.44/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (14) 940.44/291.50 Obligation: 940.44/291.50 Innermost TRS: 940.44/291.50 Rules: 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.50 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.50 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.50 foldl#3(x2, Nil) -> x2 940.44/291.50 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.50 minus#2(0', x16) -> 0' 940.44/291.50 minus#2(S(x20), 0') -> S(x20) 940.44/291.50 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.50 plus#2(0', S(x2)) -> S(x2) 940.44/291.50 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.50 max#2(0', x8) -> x8 940.44/291.50 max#2(S(x12), 0') -> S(x12) 940.44/291.50 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.50 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.50 940.44/291.50 Types: 940.44/291.50 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.50 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.50 0' :: 0':S:M 940.44/291.50 S :: 0':S:M -> 0':S:M 940.44/291.50 M :: 0':S:M -> 0':S:M 940.44/291.50 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.50 Nil :: Cons:Nil 940.44/291.50 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.50 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 main :: Cons:Nil -> 0':S:M 940.44/291.50 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.50 hole_0':S:M2_5 :: 0':S:M 940.44/291.50 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.50 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.50 940.44/291.50 940.44/291.50 Lemmas: 940.44/291.50 minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5) 940.44/291.50 plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5) 940.44/291.50 940.44/291.50 940.44/291.50 Generator Equations: 940.44/291.50 gen_Cons:Nil3_5(0) <=> Nil 940.44/291.50 gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x)) 940.44/291.50 gen_0':S:M4_5(0) <=> 0' 940.44/291.50 gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x)) 940.44/291.50 940.44/291.50 940.44/291.50 The following defined symbols remain to be analysed: 940.44/291.50 scanr#3, foldl#3, max#2 940.44/291.50 940.44/291.50 They will be analysed ascendingly in the following order: 940.44/291.50 max#2 < foldl#3 940.44/291.50 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (15) RewriteLemmaProof (LOWER BOUND(ID)) 940.44/291.50 Proved the following rewrite lemma: 940.44/291.50 scanr#3(gen_Cons:Nil3_5(n1267_5)) -> gen_Cons:Nil3_5(+(1, n1267_5)), rt in Omega(1 + n1267_5) 940.44/291.50 940.44/291.50 Induction Base: 940.44/291.50 scanr#3(gen_Cons:Nil3_5(0)) ->_R^Omega(1) 940.44/291.50 Cons(0', Nil) 940.44/291.50 940.44/291.50 Induction Step: 940.44/291.50 scanr#3(gen_Cons:Nil3_5(+(n1267_5, 1))) ->_R^Omega(1) 940.44/291.50 cond_scanr_f_z_xs_1(scanr#3(gen_Cons:Nil3_5(n1267_5)), 0') ->_IH 940.44/291.50 cond_scanr_f_z_xs_1(gen_Cons:Nil3_5(+(1, c1268_5)), 0') ->_R^Omega(1) 940.44/291.50 Cons(0', Cons(0', gen_Cons:Nil3_5(n1267_5))) 940.44/291.50 940.44/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (16) 940.44/291.50 Obligation: 940.44/291.50 Innermost TRS: 940.44/291.50 Rules: 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.50 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.50 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.50 foldl#3(x2, Nil) -> x2 940.44/291.50 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.50 minus#2(0', x16) -> 0' 940.44/291.50 minus#2(S(x20), 0') -> S(x20) 940.44/291.50 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.50 plus#2(0', S(x2)) -> S(x2) 940.44/291.50 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.50 max#2(0', x8) -> x8 940.44/291.50 max#2(S(x12), 0') -> S(x12) 940.44/291.50 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.50 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.50 940.44/291.50 Types: 940.44/291.50 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.50 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.50 0' :: 0':S:M 940.44/291.50 S :: 0':S:M -> 0':S:M 940.44/291.50 M :: 0':S:M -> 0':S:M 940.44/291.50 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.50 Nil :: Cons:Nil 940.44/291.50 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.50 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 main :: Cons:Nil -> 0':S:M 940.44/291.50 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.50 hole_0':S:M2_5 :: 0':S:M 940.44/291.50 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.50 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.50 940.44/291.50 940.44/291.50 Lemmas: 940.44/291.50 minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5) 940.44/291.50 plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5) 940.44/291.50 scanr#3(gen_Cons:Nil3_5(n1267_5)) -> gen_Cons:Nil3_5(+(1, n1267_5)), rt in Omega(1 + n1267_5) 940.44/291.50 940.44/291.50 940.44/291.50 Generator Equations: 940.44/291.50 gen_Cons:Nil3_5(0) <=> Nil 940.44/291.50 gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x)) 940.44/291.50 gen_0':S:M4_5(0) <=> 0' 940.44/291.50 gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x)) 940.44/291.50 940.44/291.50 940.44/291.50 The following defined symbols remain to be analysed: 940.44/291.50 max#2, foldl#3 940.44/291.50 940.44/291.50 They will be analysed ascendingly in the following order: 940.44/291.50 max#2 < foldl#3 940.44/291.50 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (17) RewriteLemmaProof (LOWER BOUND(ID)) 940.44/291.50 Proved the following rewrite lemma: 940.44/291.50 max#2(gen_0':S:M4_5(n15636_5), gen_0':S:M4_5(n15636_5)) -> gen_0':S:M4_5(n15636_5), rt in Omega(1 + n15636_5) 940.44/291.50 940.44/291.50 Induction Base: 940.44/291.50 max#2(gen_0':S:M4_5(0), gen_0':S:M4_5(0)) ->_R^Omega(1) 940.44/291.50 gen_0':S:M4_5(0) 940.44/291.50 940.44/291.50 Induction Step: 940.44/291.50 max#2(gen_0':S:M4_5(+(n15636_5, 1)), gen_0':S:M4_5(+(n15636_5, 1))) ->_R^Omega(1) 940.44/291.50 S(max#2(gen_0':S:M4_5(n15636_5), gen_0':S:M4_5(n15636_5))) ->_IH 940.44/291.50 S(gen_0':S:M4_5(c15637_5)) 940.44/291.50 940.44/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (18) 940.44/291.50 Obligation: 940.44/291.50 Innermost TRS: 940.44/291.50 Rules: 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), 0') -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), 0') -> Cons(S(x2), Cons(S(x2), x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), M(x2)) -> Cons(0', Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x40), x23), M(0')) -> Cons(S(x40), Cons(S(x40), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x8), x23), M(S(x4))) -> Cons(minus#2(x8, x4), Cons(S(x8), x23)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(0', x11), S(x2)) -> Cons(S(x2), Cons(0', x11)) 940.44/291.50 cond_scanr_f_z_xs_1(Cons(S(x2), x11), S(x4)) -> Cons(plus#2(S(x4), S(x2)), Cons(S(x2), x11)) 940.44/291.50 scanr#3(Nil) -> Cons(0', Nil) 940.44/291.50 scanr#3(Cons(x4, x2)) -> cond_scanr_f_z_xs_1(scanr#3(x2), x4) 940.44/291.50 foldl#3(x2, Nil) -> x2 940.44/291.50 foldl#3(x6, Cons(x4, x2)) -> foldl#3(max#2(x6, x4), x2) 940.44/291.50 minus#2(0', x16) -> 0' 940.44/291.50 minus#2(S(x20), 0') -> S(x20) 940.44/291.50 minus#2(S(x4), S(x2)) -> minus#2(x4, x2) 940.44/291.50 plus#2(0', S(x2)) -> S(x2) 940.44/291.50 plus#2(S(x4), S(x2)) -> S(plus#2(x4, S(x2))) 940.44/291.50 max#2(0', x8) -> x8 940.44/291.50 max#2(S(x12), 0') -> S(x12) 940.44/291.50 max#2(S(x4), S(x2)) -> S(max#2(x4, x2)) 940.44/291.50 main(x1) -> foldl#3(0', scanr#3(x1)) 940.44/291.50 940.44/291.50 Types: 940.44/291.50 cond_scanr_f_z_xs_1 :: Cons:Nil -> 0':S:M -> Cons:Nil 940.44/291.50 Cons :: 0':S:M -> Cons:Nil -> Cons:Nil 940.44/291.50 0' :: 0':S:M 940.44/291.50 S :: 0':S:M -> 0':S:M 940.44/291.50 M :: 0':S:M -> 0':S:M 940.44/291.50 minus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 plus#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 scanr#3 :: Cons:Nil -> Cons:Nil 940.44/291.50 Nil :: Cons:Nil 940.44/291.50 foldl#3 :: 0':S:M -> Cons:Nil -> 0':S:M 940.44/291.50 max#2 :: 0':S:M -> 0':S:M -> 0':S:M 940.44/291.50 main :: Cons:Nil -> 0':S:M 940.44/291.50 hole_Cons:Nil1_5 :: Cons:Nil 940.44/291.50 hole_0':S:M2_5 :: 0':S:M 940.44/291.50 gen_Cons:Nil3_5 :: Nat -> Cons:Nil 940.44/291.50 gen_0':S:M4_5 :: Nat -> 0':S:M 940.44/291.50 940.44/291.50 940.44/291.50 Lemmas: 940.44/291.50 minus#2(gen_0':S:M4_5(n6_5), gen_0':S:M4_5(n6_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n6_5) 940.44/291.50 plus#2(gen_0':S:M4_5(n655_5), gen_0':S:M4_5(1)) -> gen_0':S:M4_5(+(1, n655_5)), rt in Omega(1 + n655_5) 940.44/291.50 scanr#3(gen_Cons:Nil3_5(n1267_5)) -> gen_Cons:Nil3_5(+(1, n1267_5)), rt in Omega(1 + n1267_5) 940.44/291.50 max#2(gen_0':S:M4_5(n15636_5), gen_0':S:M4_5(n15636_5)) -> gen_0':S:M4_5(n15636_5), rt in Omega(1 + n15636_5) 940.44/291.50 940.44/291.50 940.44/291.50 Generator Equations: 940.44/291.50 gen_Cons:Nil3_5(0) <=> Nil 940.44/291.50 gen_Cons:Nil3_5(+(x, 1)) <=> Cons(0', gen_Cons:Nil3_5(x)) 940.44/291.50 gen_0':S:M4_5(0) <=> 0' 940.44/291.50 gen_0':S:M4_5(+(x, 1)) <=> S(gen_0':S:M4_5(x)) 940.44/291.50 940.44/291.50 940.44/291.50 The following defined symbols remain to be analysed: 940.44/291.50 foldl#3 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (19) RewriteLemmaProof (LOWER BOUND(ID)) 940.44/291.50 Proved the following rewrite lemma: 940.44/291.50 foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(n16539_5)) -> gen_0':S:M4_5(0), rt in Omega(1 + n16539_5) 940.44/291.50 940.44/291.50 Induction Base: 940.44/291.50 foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(0)) ->_R^Omega(1) 940.44/291.50 gen_0':S:M4_5(0) 940.44/291.50 940.44/291.50 Induction Step: 940.44/291.50 foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(+(n16539_5, 1))) ->_R^Omega(1) 940.44/291.50 foldl#3(max#2(gen_0':S:M4_5(0), 0'), gen_Cons:Nil3_5(n16539_5)) ->_L^Omega(1) 940.44/291.50 foldl#3(gen_0':S:M4_5(0), gen_Cons:Nil3_5(n16539_5)) ->_IH 940.44/291.50 gen_0':S:M4_5(0) 940.44/291.50 940.44/291.50 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 940.44/291.50 ---------------------------------------- 940.44/291.50 940.44/291.50 (20) 940.44/291.50 BOUNDS(1, INF) 940.73/291.57 EOF