1140.33/291.51 WORST_CASE(Omega(n^1), ?) 1140.50/291.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1140.50/291.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1140.50/291.53 1140.50/291.53 1140.50/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1140.50/291.53 1140.50/291.53 (0) CpxTRS 1140.50/291.53 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1140.50/291.53 (2) CpxTRS 1140.50/291.53 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 1140.50/291.53 (4) CpxTRS 1140.50/291.53 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1140.50/291.53 (6) typed CpxTrs 1140.50/291.53 (7) OrderProof [LOWER BOUND(ID), 0 ms] 1140.50/291.53 (8) typed CpxTrs 1140.50/291.53 (9) RewriteLemmaProof [LOWER BOUND(ID), 286 ms] 1140.50/291.53 (10) BEST 1140.50/291.53 (11) proven lower bound 1140.50/291.53 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 1140.50/291.53 (13) BOUNDS(n^1, INF) 1140.50/291.53 (14) typed CpxTrs 1140.50/291.53 (15) RewriteLemmaProof [LOWER BOUND(ID), 75 ms] 1140.50/291.53 (16) typed CpxTrs 1140.50/291.53 (17) RewriteLemmaProof [LOWER BOUND(ID), 32 ms] 1140.50/291.53 (18) typed CpxTrs 1140.50/291.53 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (0) 1140.50/291.53 Obligation: 1140.50/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1140.50/291.53 1140.50/291.53 1140.50/291.53 The TRS R consists of the following rules: 1140.50/291.53 1140.50/291.53 ge(x, 0) -> true 1140.50/291.53 ge(0, s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(0, length(x)), nil, 0, length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(x, y), z) -> if(append(y, cons(x, nil)), ge(c, l), cons(x, z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(x, y), z) -> cons(x, append(y, z)) 1140.50/291.53 length(nil) -> 0 1140.50/291.53 length(cons(x, y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 S is empty. 1140.50/291.53 Rewrite Strategy: INNERMOST 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1140.50/291.53 Renamed function symbols to avoid clashes with predefined symbol. 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (2) 1140.50/291.53 Obligation: 1140.50/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1140.50/291.53 1140.50/291.53 1140.50/291.53 The TRS R consists of the following rules: 1140.50/291.53 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(0', length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(x, y), z) -> if(append(y, cons(x, nil)), ge(c, l), cons(x, z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(x, y), z) -> cons(x, append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(x, y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 S is empty. 1140.50/291.53 Rewrite Strategy: INNERMOST 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (3) SlicingProof (LOWER BOUND(ID)) 1140.50/291.53 Sliced the following arguments: 1140.50/291.53 eq/0 1140.50/291.53 cons/0 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (4) 1140.50/291.53 Obligation: 1140.50/291.53 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1140.50/291.53 1140.50/291.53 1140.50/291.53 The TRS R consists of the following rules: 1140.50/291.53 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 S is empty. 1140.50/291.53 Rewrite Strategy: INNERMOST 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1140.50/291.53 Infered types. 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (6) 1140.50/291.53 Obligation: 1140.50/291.53 Innermost TRS: 1140.50/291.53 Rules: 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 Types: 1140.50/291.53 ge :: 0':s -> 0':s -> true:false:eq 1140.50/291.53 0' :: 0':s 1140.50/291.53 true :: true:false:eq 1140.50/291.53 s :: 0':s -> 0':s 1140.50/291.53 false :: true:false:eq 1140.50/291.53 rev :: nil:cons -> nil:cons 1140.50/291.53 if :: nil:cons -> true:false:eq -> nil:cons -> 0':s -> 0':s -> nil:cons 1140.50/291.53 eq :: 0':s -> true:false:eq 1140.50/291.53 length :: nil:cons -> 0':s 1140.50/291.53 nil :: nil:cons 1140.50/291.53 help :: 0':s -> 0':s -> nil:cons -> nil:cons -> nil:cons 1140.50/291.53 cons :: nil:cons -> nil:cons 1140.50/291.53 append :: nil:cons -> nil:cons -> nil:cons 1140.50/291.53 hole_true:false:eq1_0 :: true:false:eq 1140.50/291.53 hole_0':s2_0 :: 0':s 1140.50/291.53 hole_nil:cons3_0 :: nil:cons 1140.50/291.53 gen_0':s4_0 :: Nat -> 0':s 1140.50/291.53 gen_nil:cons5_0 :: Nat -> nil:cons 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (7) OrderProof (LOWER BOUND(ID)) 1140.50/291.53 Heuristically decided to analyse the following defined symbols: 1140.50/291.53 ge, length, help, append 1140.50/291.53 1140.50/291.53 They will be analysed ascendingly in the following order: 1140.50/291.53 ge < help 1140.50/291.53 append < help 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (8) 1140.50/291.53 Obligation: 1140.50/291.53 Innermost TRS: 1140.50/291.53 Rules: 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 Types: 1140.50/291.53 ge :: 0':s -> 0':s -> true:false:eq 1140.50/291.53 0' :: 0':s 1140.50/291.53 true :: true:false:eq 1140.50/291.53 s :: 0':s -> 0':s 1140.50/291.53 false :: true:false:eq 1140.50/291.53 rev :: nil:cons -> nil:cons 1140.50/291.53 if :: nil:cons -> true:false:eq -> nil:cons -> 0':s -> 0':s -> nil:cons 1140.50/291.53 eq :: 0':s -> true:false:eq 1140.50/291.53 length :: nil:cons -> 0':s 1140.50/291.53 nil :: nil:cons 1140.50/291.53 help :: 0':s -> 0':s -> nil:cons -> nil:cons -> nil:cons 1140.50/291.53 cons :: nil:cons -> nil:cons 1140.50/291.53 append :: nil:cons -> nil:cons -> nil:cons 1140.50/291.53 hole_true:false:eq1_0 :: true:false:eq 1140.50/291.53 hole_0':s2_0 :: 0':s 1140.50/291.53 hole_nil:cons3_0 :: nil:cons 1140.50/291.53 gen_0':s4_0 :: Nat -> 0':s 1140.50/291.53 gen_nil:cons5_0 :: Nat -> nil:cons 1140.50/291.53 1140.50/291.53 1140.50/291.53 Generator Equations: 1140.50/291.53 gen_0':s4_0(0) <=> 0' 1140.50/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1140.50/291.53 gen_nil:cons5_0(0) <=> nil 1140.50/291.53 gen_nil:cons5_0(+(x, 1)) <=> cons(gen_nil:cons5_0(x)) 1140.50/291.53 1140.50/291.53 1140.50/291.53 The following defined symbols remain to be analysed: 1140.50/291.53 ge, length, help, append 1140.50/291.53 1140.50/291.53 They will be analysed ascendingly in the following order: 1140.50/291.53 ge < help 1140.50/291.53 append < help 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (9) RewriteLemmaProof (LOWER BOUND(ID)) 1140.50/291.53 Proved the following rewrite lemma: 1140.50/291.53 ge(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1140.50/291.53 1140.50/291.53 Induction Base: 1140.50/291.53 ge(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1140.50/291.53 true 1140.50/291.53 1140.50/291.53 Induction Step: 1140.50/291.53 ge(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(+(n7_0, 1))) ->_R^Omega(1) 1140.50/291.53 ge(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) ->_IH 1140.50/291.53 true 1140.50/291.53 1140.50/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (10) 1140.50/291.53 Complex Obligation (BEST) 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (11) 1140.50/291.53 Obligation: 1140.50/291.53 Proved the lower bound n^1 for the following obligation: 1140.50/291.53 1140.50/291.53 Innermost TRS: 1140.50/291.53 Rules: 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 Types: 1140.50/291.53 ge :: 0':s -> 0':s -> true:false:eq 1140.50/291.53 0' :: 0':s 1140.50/291.53 true :: true:false:eq 1140.50/291.53 s :: 0':s -> 0':s 1140.50/291.53 false :: true:false:eq 1140.50/291.53 rev :: nil:cons -> nil:cons 1140.50/291.53 if :: nil:cons -> true:false:eq -> nil:cons -> 0':s -> 0':s -> nil:cons 1140.50/291.53 eq :: 0':s -> true:false:eq 1140.50/291.53 length :: nil:cons -> 0':s 1140.50/291.53 nil :: nil:cons 1140.50/291.53 help :: 0':s -> 0':s -> nil:cons -> nil:cons -> nil:cons 1140.50/291.53 cons :: nil:cons -> nil:cons 1140.50/291.53 append :: nil:cons -> nil:cons -> nil:cons 1140.50/291.53 hole_true:false:eq1_0 :: true:false:eq 1140.50/291.53 hole_0':s2_0 :: 0':s 1140.50/291.53 hole_nil:cons3_0 :: nil:cons 1140.50/291.53 gen_0':s4_0 :: Nat -> 0':s 1140.50/291.53 gen_nil:cons5_0 :: Nat -> nil:cons 1140.50/291.53 1140.50/291.53 1140.50/291.53 Generator Equations: 1140.50/291.53 gen_0':s4_0(0) <=> 0' 1140.50/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1140.50/291.53 gen_nil:cons5_0(0) <=> nil 1140.50/291.53 gen_nil:cons5_0(+(x, 1)) <=> cons(gen_nil:cons5_0(x)) 1140.50/291.53 1140.50/291.53 1140.50/291.53 The following defined symbols remain to be analysed: 1140.50/291.53 ge, length, help, append 1140.50/291.53 1140.50/291.53 They will be analysed ascendingly in the following order: 1140.50/291.53 ge < help 1140.50/291.53 append < help 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (12) LowerBoundPropagationProof (FINISHED) 1140.50/291.53 Propagated lower bound. 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (13) 1140.50/291.53 BOUNDS(n^1, INF) 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (14) 1140.50/291.53 Obligation: 1140.50/291.53 Innermost TRS: 1140.50/291.53 Rules: 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 Types: 1140.50/291.53 ge :: 0':s -> 0':s -> true:false:eq 1140.50/291.53 0' :: 0':s 1140.50/291.53 true :: true:false:eq 1140.50/291.53 s :: 0':s -> 0':s 1140.50/291.53 false :: true:false:eq 1140.50/291.53 rev :: nil:cons -> nil:cons 1140.50/291.53 if :: nil:cons -> true:false:eq -> nil:cons -> 0':s -> 0':s -> nil:cons 1140.50/291.53 eq :: 0':s -> true:false:eq 1140.50/291.53 length :: nil:cons -> 0':s 1140.50/291.53 nil :: nil:cons 1140.50/291.53 help :: 0':s -> 0':s -> nil:cons -> nil:cons -> nil:cons 1140.50/291.53 cons :: nil:cons -> nil:cons 1140.50/291.53 append :: nil:cons -> nil:cons -> nil:cons 1140.50/291.53 hole_true:false:eq1_0 :: true:false:eq 1140.50/291.53 hole_0':s2_0 :: 0':s 1140.50/291.53 hole_nil:cons3_0 :: nil:cons 1140.50/291.53 gen_0':s4_0 :: Nat -> 0':s 1140.50/291.53 gen_nil:cons5_0 :: Nat -> nil:cons 1140.50/291.53 1140.50/291.53 1140.50/291.53 Lemmas: 1140.50/291.53 ge(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1140.50/291.53 1140.50/291.53 1140.50/291.53 Generator Equations: 1140.50/291.53 gen_0':s4_0(0) <=> 0' 1140.50/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1140.50/291.53 gen_nil:cons5_0(0) <=> nil 1140.50/291.53 gen_nil:cons5_0(+(x, 1)) <=> cons(gen_nil:cons5_0(x)) 1140.50/291.53 1140.50/291.53 1140.50/291.53 The following defined symbols remain to be analysed: 1140.50/291.53 length, help, append 1140.50/291.53 1140.50/291.53 They will be analysed ascendingly in the following order: 1140.50/291.53 append < help 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1140.50/291.53 Proved the following rewrite lemma: 1140.50/291.53 length(gen_nil:cons5_0(n275_0)) -> gen_0':s4_0(n275_0), rt in Omega(1 + n275_0) 1140.50/291.53 1140.50/291.53 Induction Base: 1140.50/291.53 length(gen_nil:cons5_0(0)) ->_R^Omega(1) 1140.50/291.53 0' 1140.50/291.53 1140.50/291.53 Induction Step: 1140.50/291.53 length(gen_nil:cons5_0(+(n275_0, 1))) ->_R^Omega(1) 1140.50/291.53 s(length(gen_nil:cons5_0(n275_0))) ->_IH 1140.50/291.53 s(gen_0':s4_0(c276_0)) 1140.50/291.53 1140.50/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (16) 1140.50/291.53 Obligation: 1140.50/291.53 Innermost TRS: 1140.50/291.53 Rules: 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 Types: 1140.50/291.53 ge :: 0':s -> 0':s -> true:false:eq 1140.50/291.53 0' :: 0':s 1140.50/291.53 true :: true:false:eq 1140.50/291.53 s :: 0':s -> 0':s 1140.50/291.53 false :: true:false:eq 1140.50/291.53 rev :: nil:cons -> nil:cons 1140.50/291.53 if :: nil:cons -> true:false:eq -> nil:cons -> 0':s -> 0':s -> nil:cons 1140.50/291.53 eq :: 0':s -> true:false:eq 1140.50/291.53 length :: nil:cons -> 0':s 1140.50/291.53 nil :: nil:cons 1140.50/291.53 help :: 0':s -> 0':s -> nil:cons -> nil:cons -> nil:cons 1140.50/291.53 cons :: nil:cons -> nil:cons 1140.50/291.53 append :: nil:cons -> nil:cons -> nil:cons 1140.50/291.53 hole_true:false:eq1_0 :: true:false:eq 1140.50/291.53 hole_0':s2_0 :: 0':s 1140.50/291.53 hole_nil:cons3_0 :: nil:cons 1140.50/291.53 gen_0':s4_0 :: Nat -> 0':s 1140.50/291.53 gen_nil:cons5_0 :: Nat -> nil:cons 1140.50/291.53 1140.50/291.53 1140.50/291.53 Lemmas: 1140.50/291.53 ge(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1140.50/291.53 length(gen_nil:cons5_0(n275_0)) -> gen_0':s4_0(n275_0), rt in Omega(1 + n275_0) 1140.50/291.53 1140.50/291.53 1140.50/291.53 Generator Equations: 1140.50/291.53 gen_0':s4_0(0) <=> 0' 1140.50/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1140.50/291.53 gen_nil:cons5_0(0) <=> nil 1140.50/291.53 gen_nil:cons5_0(+(x, 1)) <=> cons(gen_nil:cons5_0(x)) 1140.50/291.53 1140.50/291.53 1140.50/291.53 The following defined symbols remain to be analysed: 1140.50/291.53 append, help 1140.50/291.53 1140.50/291.53 They will be analysed ascendingly in the following order: 1140.50/291.53 append < help 1140.50/291.53 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1140.50/291.53 Proved the following rewrite lemma: 1140.50/291.53 append(gen_nil:cons5_0(n497_0), gen_nil:cons5_0(b)) -> gen_nil:cons5_0(+(n497_0, b)), rt in Omega(1 + n497_0) 1140.50/291.53 1140.50/291.53 Induction Base: 1140.50/291.53 append(gen_nil:cons5_0(0), gen_nil:cons5_0(b)) ->_R^Omega(1) 1140.50/291.53 gen_nil:cons5_0(b) 1140.50/291.53 1140.50/291.53 Induction Step: 1140.50/291.53 append(gen_nil:cons5_0(+(n497_0, 1)), gen_nil:cons5_0(b)) ->_R^Omega(1) 1140.50/291.53 cons(append(gen_nil:cons5_0(n497_0), gen_nil:cons5_0(b))) ->_IH 1140.50/291.53 cons(gen_nil:cons5_0(+(b, c498_0))) 1140.50/291.53 1140.50/291.53 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1140.50/291.53 ---------------------------------------- 1140.50/291.53 1140.50/291.53 (18) 1140.50/291.53 Obligation: 1140.50/291.53 Innermost TRS: 1140.50/291.53 Rules: 1140.50/291.53 ge(x, 0') -> true 1140.50/291.53 ge(0', s(y)) -> false 1140.50/291.53 ge(s(x), s(y)) -> ge(x, y) 1140.50/291.53 rev(x) -> if(x, eq(length(x)), nil, 0', length(x)) 1140.50/291.53 if(x, true, z, c, l) -> z 1140.50/291.53 if(x, false, z, c, l) -> help(s(c), l, x, z) 1140.50/291.53 help(c, l, cons(y), z) -> if(append(y, cons(nil)), ge(c, l), cons(z), c, l) 1140.50/291.53 append(nil, y) -> y 1140.50/291.53 append(cons(y), z) -> cons(append(y, z)) 1140.50/291.53 length(nil) -> 0' 1140.50/291.53 length(cons(y)) -> s(length(y)) 1140.50/291.53 1140.50/291.53 Types: 1140.50/291.53 ge :: 0':s -> 0':s -> true:false:eq 1140.50/291.53 0' :: 0':s 1140.50/291.53 true :: true:false:eq 1140.50/291.53 s :: 0':s -> 0':s 1140.50/291.53 false :: true:false:eq 1140.50/291.53 rev :: nil:cons -> nil:cons 1140.50/291.53 if :: nil:cons -> true:false:eq -> nil:cons -> 0':s -> 0':s -> nil:cons 1140.50/291.53 eq :: 0':s -> true:false:eq 1140.50/291.53 length :: nil:cons -> 0':s 1140.50/291.53 nil :: nil:cons 1140.50/291.53 help :: 0':s -> 0':s -> nil:cons -> nil:cons -> nil:cons 1140.50/291.53 cons :: nil:cons -> nil:cons 1140.50/291.53 append :: nil:cons -> nil:cons -> nil:cons 1140.50/291.53 hole_true:false:eq1_0 :: true:false:eq 1140.50/291.53 hole_0':s2_0 :: 0':s 1140.50/291.53 hole_nil:cons3_0 :: nil:cons 1140.50/291.53 gen_0':s4_0 :: Nat -> 0':s 1140.50/291.53 gen_nil:cons5_0 :: Nat -> nil:cons 1140.50/291.53 1140.50/291.53 1140.50/291.53 Lemmas: 1140.50/291.53 ge(gen_0':s4_0(n7_0), gen_0':s4_0(n7_0)) -> true, rt in Omega(1 + n7_0) 1140.50/291.53 length(gen_nil:cons5_0(n275_0)) -> gen_0':s4_0(n275_0), rt in Omega(1 + n275_0) 1140.50/291.53 append(gen_nil:cons5_0(n497_0), gen_nil:cons5_0(b)) -> gen_nil:cons5_0(+(n497_0, b)), rt in Omega(1 + n497_0) 1140.50/291.53 1140.50/291.53 1140.50/291.53 Generator Equations: 1140.50/291.53 gen_0':s4_0(0) <=> 0' 1140.50/291.53 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1140.50/291.53 gen_nil:cons5_0(0) <=> nil 1140.50/291.53 gen_nil:cons5_0(+(x, 1)) <=> cons(gen_nil:cons5_0(x)) 1140.50/291.53 1140.50/291.53 1140.50/291.53 The following defined symbols remain to be analysed: 1140.50/291.53 help 1140.56/291.59 EOF