1111.12/291.69 WORST_CASE(Omega(n^2), ?) 1111.12/291.72 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1111.12/291.72 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1111.12/291.72 1111.12/291.72 1111.12/291.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.12/291.72 1111.12/291.72 (0) CpxTRS 1111.12/291.72 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.12/291.72 (2) CpxTRS 1111.12/291.72 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 1111.12/291.72 (4) CpxTRS 1111.12/291.72 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1111.12/291.72 (6) typed CpxTrs 1111.12/291.72 (7) OrderProof [LOWER BOUND(ID), 0 ms] 1111.12/291.72 (8) typed CpxTrs 1111.12/291.72 (9) RewriteLemmaProof [LOWER BOUND(ID), 280 ms] 1111.12/291.72 (10) BEST 1111.12/291.72 (11) proven lower bound 1111.12/291.72 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 1111.12/291.72 (13) BOUNDS(n^1, INF) 1111.12/291.72 (14) typed CpxTrs 1111.12/291.72 (15) RewriteLemmaProof [LOWER BOUND(ID), 81 ms] 1111.12/291.72 (16) typed CpxTrs 1111.12/291.72 (17) RewriteLemmaProof [LOWER BOUND(ID), 82 ms] 1111.12/291.72 (18) BEST 1111.12/291.72 (19) proven lower bound 1111.12/291.72 (20) LowerBoundPropagationProof [FINISHED, 0 ms] 1111.12/291.72 (21) BOUNDS(n^2, INF) 1111.12/291.72 (22) typed CpxTrs 1111.12/291.72 1111.12/291.72 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (0) 1111.12/291.72 Obligation: 1111.12/291.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.12/291.72 1111.12/291.72 1111.12/291.72 The TRS R consists of the following rules: 1111.12/291.72 1111.12/291.72 table -> gen(s(0)) 1111.12/291.72 gen(x) -> if1(le(x, 10), x) 1111.12/291.72 if1(false, x) -> nil 1111.12/291.72 if1(true, x) -> if2(x, x) 1111.12/291.72 if2(x, y) -> if3(le(y, 10), x, y) 1111.12/291.72 if3(true, x, y) -> cons(entry(x, y, times(x, y)), if2(x, s(y))) 1111.12/291.72 if3(false, x, y) -> gen(s(x)) 1111.12/291.72 le(0, y) -> true 1111.12/291.72 le(s(x), 0) -> false 1111.12/291.72 le(s(x), s(y)) -> le(x, y) 1111.12/291.72 plus(0, y) -> y 1111.12/291.72 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.72 times(0, y) -> 0 1111.12/291.72 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.72 10 -> s(s(s(s(s(s(s(s(s(s(0)))))))))) 1111.12/291.72 1111.12/291.72 S is empty. 1111.12/291.72 Rewrite Strategy: INNERMOST 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1111.12/291.72 Renamed function symbols to avoid clashes with predefined symbol. 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (2) 1111.12/291.72 Obligation: 1111.12/291.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.12/291.72 1111.12/291.72 1111.12/291.72 The TRS R consists of the following rules: 1111.12/291.72 1111.12/291.72 table -> gen(s(0')) 1111.12/291.72 gen(x) -> if1(le(x, 10'), x) 1111.12/291.72 if1(false, x) -> nil 1111.12/291.72 if1(true, x) -> if2(x, x) 1111.12/291.72 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.72 if3(true, x, y) -> cons(entry(x, y, times(x, y)), if2(x, s(y))) 1111.12/291.72 if3(false, x, y) -> gen(s(x)) 1111.12/291.72 le(0', y) -> true 1111.12/291.72 le(s(x), 0') -> false 1111.12/291.72 le(s(x), s(y)) -> le(x, y) 1111.12/291.72 plus(0', y) -> y 1111.12/291.72 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.72 times(0', y) -> 0' 1111.12/291.72 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.72 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.72 1111.12/291.72 S is empty. 1111.12/291.72 Rewrite Strategy: INNERMOST 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (3) SlicingProof (LOWER BOUND(ID)) 1111.12/291.72 Sliced the following arguments: 1111.12/291.72 entry/0 1111.12/291.72 entry/1 1111.12/291.72 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (4) 1111.12/291.72 Obligation: 1111.12/291.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1111.12/291.72 1111.12/291.72 1111.12/291.72 The TRS R consists of the following rules: 1111.12/291.72 1111.12/291.72 table -> gen(s(0')) 1111.12/291.72 gen(x) -> if1(le(x, 10'), x) 1111.12/291.72 if1(false, x) -> nil 1111.12/291.72 if1(true, x) -> if2(x, x) 1111.12/291.72 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.72 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.72 if3(false, x, y) -> gen(s(x)) 1111.12/291.72 le(0', y) -> true 1111.12/291.72 le(s(x), 0') -> false 1111.12/291.72 le(s(x), s(y)) -> le(x, y) 1111.12/291.72 plus(0', y) -> y 1111.12/291.72 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.72 times(0', y) -> 0' 1111.12/291.72 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.72 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.72 1111.12/291.72 S is empty. 1111.12/291.72 Rewrite Strategy: INNERMOST 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1111.12/291.72 Infered types. 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (6) 1111.12/291.72 Obligation: 1111.12/291.72 Innermost TRS: 1111.12/291.72 Rules: 1111.12/291.72 table -> gen(s(0')) 1111.12/291.72 gen(x) -> if1(le(x, 10'), x) 1111.12/291.72 if1(false, x) -> nil 1111.12/291.72 if1(true, x) -> if2(x, x) 1111.12/291.72 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.72 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.72 if3(false, x, y) -> gen(s(x)) 1111.12/291.72 le(0', y) -> true 1111.12/291.72 le(s(x), 0') -> false 1111.12/291.72 le(s(x), s(y)) -> le(x, y) 1111.12/291.72 plus(0', y) -> y 1111.12/291.72 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.72 times(0', y) -> 0' 1111.12/291.72 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.72 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.72 1111.12/291.72 Types: 1111.12/291.72 table :: nil:cons 1111.12/291.72 gen :: 0':s -> nil:cons 1111.12/291.72 s :: 0':s -> 0':s 1111.12/291.72 0' :: 0':s 1111.12/291.72 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.72 le :: 0':s -> 0':s -> false:true 1111.12/291.72 10' :: 0':s 1111.12/291.72 false :: false:true 1111.12/291.72 nil :: nil:cons 1111.12/291.72 true :: false:true 1111.12/291.72 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.72 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.72 cons :: entry -> nil:cons -> nil:cons 1111.12/291.72 entry :: 0':s -> entry 1111.12/291.72 times :: 0':s -> 0':s -> 0':s 1111.12/291.72 plus :: 0':s -> 0':s -> 0':s 1111.12/291.72 hole_nil:cons1_0 :: nil:cons 1111.12/291.72 hole_0':s2_0 :: 0':s 1111.12/291.72 hole_false:true3_0 :: false:true 1111.12/291.72 hole_entry4_0 :: entry 1111.12/291.72 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.72 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.72 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (7) OrderProof (LOWER BOUND(ID)) 1111.12/291.72 Heuristically decided to analyse the following defined symbols: 1111.12/291.72 gen, le, if2, times, plus 1111.12/291.72 1111.12/291.72 They will be analysed ascendingly in the following order: 1111.12/291.72 le < gen 1111.12/291.72 gen = if2 1111.12/291.72 le < if2 1111.12/291.72 times < if2 1111.12/291.72 plus < times 1111.12/291.72 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (8) 1111.12/291.72 Obligation: 1111.12/291.72 Innermost TRS: 1111.12/291.72 Rules: 1111.12/291.72 table -> gen(s(0')) 1111.12/291.72 gen(x) -> if1(le(x, 10'), x) 1111.12/291.72 if1(false, x) -> nil 1111.12/291.72 if1(true, x) -> if2(x, x) 1111.12/291.72 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.72 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.72 if3(false, x, y) -> gen(s(x)) 1111.12/291.72 le(0', y) -> true 1111.12/291.72 le(s(x), 0') -> false 1111.12/291.72 le(s(x), s(y)) -> le(x, y) 1111.12/291.72 plus(0', y) -> y 1111.12/291.72 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.72 times(0', y) -> 0' 1111.12/291.72 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.72 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.72 1111.12/291.72 Types: 1111.12/291.72 table :: nil:cons 1111.12/291.72 gen :: 0':s -> nil:cons 1111.12/291.72 s :: 0':s -> 0':s 1111.12/291.72 0' :: 0':s 1111.12/291.72 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.72 le :: 0':s -> 0':s -> false:true 1111.12/291.72 10' :: 0':s 1111.12/291.72 false :: false:true 1111.12/291.72 nil :: nil:cons 1111.12/291.72 true :: false:true 1111.12/291.72 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.72 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.72 cons :: entry -> nil:cons -> nil:cons 1111.12/291.72 entry :: 0':s -> entry 1111.12/291.72 times :: 0':s -> 0':s -> 0':s 1111.12/291.72 plus :: 0':s -> 0':s -> 0':s 1111.12/291.72 hole_nil:cons1_0 :: nil:cons 1111.12/291.72 hole_0':s2_0 :: 0':s 1111.12/291.72 hole_false:true3_0 :: false:true 1111.12/291.72 hole_entry4_0 :: entry 1111.12/291.72 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.72 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.72 1111.12/291.72 1111.12/291.72 Generator Equations: 1111.12/291.72 gen_nil:cons5_0(0) <=> nil 1111.12/291.72 gen_nil:cons5_0(+(x, 1)) <=> cons(entry(0'), gen_nil:cons5_0(x)) 1111.12/291.72 gen_0':s6_0(0) <=> 0' 1111.12/291.72 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.12/291.72 1111.12/291.72 1111.12/291.72 The following defined symbols remain to be analysed: 1111.12/291.72 le, gen, if2, times, plus 1111.12/291.72 1111.12/291.72 They will be analysed ascendingly in the following order: 1111.12/291.72 le < gen 1111.12/291.72 gen = if2 1111.12/291.72 le < if2 1111.12/291.72 times < if2 1111.12/291.72 plus < times 1111.12/291.72 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (9) RewriteLemmaProof (LOWER BOUND(ID)) 1111.12/291.72 Proved the following rewrite lemma: 1111.12/291.72 le(gen_0':s6_0(n8_0), gen_0':s6_0(n8_0)) -> true, rt in Omega(1 + n8_0) 1111.12/291.72 1111.12/291.72 Induction Base: 1111.12/291.72 le(gen_0':s6_0(0), gen_0':s6_0(0)) ->_R^Omega(1) 1111.12/291.72 true 1111.12/291.72 1111.12/291.72 Induction Step: 1111.12/291.72 le(gen_0':s6_0(+(n8_0, 1)), gen_0':s6_0(+(n8_0, 1))) ->_R^Omega(1) 1111.12/291.72 le(gen_0':s6_0(n8_0), gen_0':s6_0(n8_0)) ->_IH 1111.12/291.72 true 1111.12/291.72 1111.12/291.72 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (10) 1111.12/291.72 Complex Obligation (BEST) 1111.12/291.72 1111.12/291.72 ---------------------------------------- 1111.12/291.72 1111.12/291.72 (11) 1111.12/291.72 Obligation: 1111.12/291.72 Proved the lower bound n^1 for the following obligation: 1111.12/291.72 1111.12/291.72 Innermost TRS: 1111.12/291.72 Rules: 1111.12/291.72 table -> gen(s(0')) 1111.12/291.72 gen(x) -> if1(le(x, 10'), x) 1111.12/291.72 if1(false, x) -> nil 1111.12/291.72 if1(true, x) -> if2(x, x) 1111.12/291.73 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.73 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.73 if3(false, x, y) -> gen(s(x)) 1111.12/291.73 le(0', y) -> true 1111.12/291.73 le(s(x), 0') -> false 1111.12/291.73 le(s(x), s(y)) -> le(x, y) 1111.12/291.73 plus(0', y) -> y 1111.12/291.73 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.73 times(0', y) -> 0' 1111.12/291.73 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.73 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.73 1111.12/291.73 Types: 1111.12/291.73 table :: nil:cons 1111.12/291.73 gen :: 0':s -> nil:cons 1111.12/291.73 s :: 0':s -> 0':s 1111.12/291.73 0' :: 0':s 1111.12/291.73 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.73 le :: 0':s -> 0':s -> false:true 1111.12/291.73 10' :: 0':s 1111.12/291.73 false :: false:true 1111.12/291.73 nil :: nil:cons 1111.12/291.73 true :: false:true 1111.12/291.73 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.73 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.73 cons :: entry -> nil:cons -> nil:cons 1111.12/291.73 entry :: 0':s -> entry 1111.12/291.73 times :: 0':s -> 0':s -> 0':s 1111.12/291.73 plus :: 0':s -> 0':s -> 0':s 1111.12/291.73 hole_nil:cons1_0 :: nil:cons 1111.12/291.73 hole_0':s2_0 :: 0':s 1111.12/291.73 hole_false:true3_0 :: false:true 1111.12/291.73 hole_entry4_0 :: entry 1111.12/291.73 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.73 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.73 1111.12/291.73 1111.12/291.73 Generator Equations: 1111.12/291.73 gen_nil:cons5_0(0) <=> nil 1111.12/291.73 gen_nil:cons5_0(+(x, 1)) <=> cons(entry(0'), gen_nil:cons5_0(x)) 1111.12/291.73 gen_0':s6_0(0) <=> 0' 1111.12/291.73 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.12/291.73 1111.12/291.73 1111.12/291.73 The following defined symbols remain to be analysed: 1111.12/291.73 le, gen, if2, times, plus 1111.12/291.73 1111.12/291.73 They will be analysed ascendingly in the following order: 1111.12/291.73 le < gen 1111.12/291.73 gen = if2 1111.12/291.73 le < if2 1111.12/291.73 times < if2 1111.12/291.73 plus < times 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (12) LowerBoundPropagationProof (FINISHED) 1111.12/291.73 Propagated lower bound. 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (13) 1111.12/291.73 BOUNDS(n^1, INF) 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (14) 1111.12/291.73 Obligation: 1111.12/291.73 Innermost TRS: 1111.12/291.73 Rules: 1111.12/291.73 table -> gen(s(0')) 1111.12/291.73 gen(x) -> if1(le(x, 10'), x) 1111.12/291.73 if1(false, x) -> nil 1111.12/291.73 if1(true, x) -> if2(x, x) 1111.12/291.73 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.73 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.73 if3(false, x, y) -> gen(s(x)) 1111.12/291.73 le(0', y) -> true 1111.12/291.73 le(s(x), 0') -> false 1111.12/291.73 le(s(x), s(y)) -> le(x, y) 1111.12/291.73 plus(0', y) -> y 1111.12/291.73 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.73 times(0', y) -> 0' 1111.12/291.73 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.73 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.73 1111.12/291.73 Types: 1111.12/291.73 table :: nil:cons 1111.12/291.73 gen :: 0':s -> nil:cons 1111.12/291.73 s :: 0':s -> 0':s 1111.12/291.73 0' :: 0':s 1111.12/291.73 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.73 le :: 0':s -> 0':s -> false:true 1111.12/291.73 10' :: 0':s 1111.12/291.73 false :: false:true 1111.12/291.73 nil :: nil:cons 1111.12/291.73 true :: false:true 1111.12/291.73 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.73 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.73 cons :: entry -> nil:cons -> nil:cons 1111.12/291.73 entry :: 0':s -> entry 1111.12/291.73 times :: 0':s -> 0':s -> 0':s 1111.12/291.73 plus :: 0':s -> 0':s -> 0':s 1111.12/291.73 hole_nil:cons1_0 :: nil:cons 1111.12/291.73 hole_0':s2_0 :: 0':s 1111.12/291.73 hole_false:true3_0 :: false:true 1111.12/291.73 hole_entry4_0 :: entry 1111.12/291.73 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.73 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.73 1111.12/291.73 1111.12/291.73 Lemmas: 1111.12/291.73 le(gen_0':s6_0(n8_0), gen_0':s6_0(n8_0)) -> true, rt in Omega(1 + n8_0) 1111.12/291.73 1111.12/291.73 1111.12/291.73 Generator Equations: 1111.12/291.73 gen_nil:cons5_0(0) <=> nil 1111.12/291.73 gen_nil:cons5_0(+(x, 1)) <=> cons(entry(0'), gen_nil:cons5_0(x)) 1111.12/291.73 gen_0':s6_0(0) <=> 0' 1111.12/291.73 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.12/291.73 1111.12/291.73 1111.12/291.73 The following defined symbols remain to be analysed: 1111.12/291.73 plus, gen, if2, times 1111.12/291.73 1111.12/291.73 They will be analysed ascendingly in the following order: 1111.12/291.73 gen = if2 1111.12/291.73 times < if2 1111.12/291.73 plus < times 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (15) RewriteLemmaProof (LOWER BOUND(ID)) 1111.12/291.73 Proved the following rewrite lemma: 1111.12/291.73 plus(gen_0':s6_0(n319_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n319_0, b)), rt in Omega(1 + n319_0) 1111.12/291.73 1111.12/291.73 Induction Base: 1111.12/291.73 plus(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1) 1111.12/291.73 gen_0':s6_0(b) 1111.12/291.73 1111.12/291.73 Induction Step: 1111.12/291.73 plus(gen_0':s6_0(+(n319_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1) 1111.12/291.73 s(plus(gen_0':s6_0(n319_0), gen_0':s6_0(b))) ->_IH 1111.12/291.73 s(gen_0':s6_0(+(b, c320_0))) 1111.12/291.73 1111.12/291.73 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (16) 1111.12/291.73 Obligation: 1111.12/291.73 Innermost TRS: 1111.12/291.73 Rules: 1111.12/291.73 table -> gen(s(0')) 1111.12/291.73 gen(x) -> if1(le(x, 10'), x) 1111.12/291.73 if1(false, x) -> nil 1111.12/291.73 if1(true, x) -> if2(x, x) 1111.12/291.73 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.73 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.73 if3(false, x, y) -> gen(s(x)) 1111.12/291.73 le(0', y) -> true 1111.12/291.73 le(s(x), 0') -> false 1111.12/291.73 le(s(x), s(y)) -> le(x, y) 1111.12/291.73 plus(0', y) -> y 1111.12/291.73 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.73 times(0', y) -> 0' 1111.12/291.73 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.73 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.73 1111.12/291.73 Types: 1111.12/291.73 table :: nil:cons 1111.12/291.73 gen :: 0':s -> nil:cons 1111.12/291.73 s :: 0':s -> 0':s 1111.12/291.73 0' :: 0':s 1111.12/291.73 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.73 le :: 0':s -> 0':s -> false:true 1111.12/291.73 10' :: 0':s 1111.12/291.73 false :: false:true 1111.12/291.73 nil :: nil:cons 1111.12/291.73 true :: false:true 1111.12/291.73 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.73 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.73 cons :: entry -> nil:cons -> nil:cons 1111.12/291.73 entry :: 0':s -> entry 1111.12/291.73 times :: 0':s -> 0':s -> 0':s 1111.12/291.73 plus :: 0':s -> 0':s -> 0':s 1111.12/291.73 hole_nil:cons1_0 :: nil:cons 1111.12/291.73 hole_0':s2_0 :: 0':s 1111.12/291.73 hole_false:true3_0 :: false:true 1111.12/291.73 hole_entry4_0 :: entry 1111.12/291.73 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.73 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.73 1111.12/291.73 1111.12/291.73 Lemmas: 1111.12/291.73 le(gen_0':s6_0(n8_0), gen_0':s6_0(n8_0)) -> true, rt in Omega(1 + n8_0) 1111.12/291.73 plus(gen_0':s6_0(n319_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n319_0, b)), rt in Omega(1 + n319_0) 1111.12/291.73 1111.12/291.73 1111.12/291.73 Generator Equations: 1111.12/291.73 gen_nil:cons5_0(0) <=> nil 1111.12/291.73 gen_nil:cons5_0(+(x, 1)) <=> cons(entry(0'), gen_nil:cons5_0(x)) 1111.12/291.73 gen_0':s6_0(0) <=> 0' 1111.12/291.73 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.12/291.73 1111.12/291.73 1111.12/291.73 The following defined symbols remain to be analysed: 1111.12/291.73 times, gen, if2 1111.12/291.73 1111.12/291.73 They will be analysed ascendingly in the following order: 1111.12/291.73 gen = if2 1111.12/291.73 times < if2 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (17) RewriteLemmaProof (LOWER BOUND(ID)) 1111.12/291.73 Proved the following rewrite lemma: 1111.12/291.73 times(gen_0':s6_0(n1176_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1176_0, b)), rt in Omega(1 + b*n1176_0 + n1176_0) 1111.12/291.73 1111.12/291.73 Induction Base: 1111.12/291.73 times(gen_0':s6_0(0), gen_0':s6_0(b)) ->_R^Omega(1) 1111.12/291.73 0' 1111.12/291.73 1111.12/291.73 Induction Step: 1111.12/291.73 times(gen_0':s6_0(+(n1176_0, 1)), gen_0':s6_0(b)) ->_R^Omega(1) 1111.12/291.73 plus(gen_0':s6_0(b), times(gen_0':s6_0(n1176_0), gen_0':s6_0(b))) ->_IH 1111.12/291.73 plus(gen_0':s6_0(b), gen_0':s6_0(*(c1177_0, b))) ->_L^Omega(1 + b) 1111.12/291.73 gen_0':s6_0(+(b, *(n1176_0, b))) 1111.12/291.73 1111.12/291.73 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (18) 1111.12/291.73 Complex Obligation (BEST) 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (19) 1111.12/291.73 Obligation: 1111.12/291.73 Proved the lower bound n^2 for the following obligation: 1111.12/291.73 1111.12/291.73 Innermost TRS: 1111.12/291.73 Rules: 1111.12/291.73 table -> gen(s(0')) 1111.12/291.73 gen(x) -> if1(le(x, 10'), x) 1111.12/291.73 if1(false, x) -> nil 1111.12/291.73 if1(true, x) -> if2(x, x) 1111.12/291.73 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.73 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.73 if3(false, x, y) -> gen(s(x)) 1111.12/291.73 le(0', y) -> true 1111.12/291.73 le(s(x), 0') -> false 1111.12/291.73 le(s(x), s(y)) -> le(x, y) 1111.12/291.73 plus(0', y) -> y 1111.12/291.73 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.73 times(0', y) -> 0' 1111.12/291.73 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.73 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.73 1111.12/291.73 Types: 1111.12/291.73 table :: nil:cons 1111.12/291.73 gen :: 0':s -> nil:cons 1111.12/291.73 s :: 0':s -> 0':s 1111.12/291.73 0' :: 0':s 1111.12/291.73 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.73 le :: 0':s -> 0':s -> false:true 1111.12/291.73 10' :: 0':s 1111.12/291.73 false :: false:true 1111.12/291.73 nil :: nil:cons 1111.12/291.73 true :: false:true 1111.12/291.73 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.73 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.73 cons :: entry -> nil:cons -> nil:cons 1111.12/291.73 entry :: 0':s -> entry 1111.12/291.73 times :: 0':s -> 0':s -> 0':s 1111.12/291.73 plus :: 0':s -> 0':s -> 0':s 1111.12/291.73 hole_nil:cons1_0 :: nil:cons 1111.12/291.73 hole_0':s2_0 :: 0':s 1111.12/291.73 hole_false:true3_0 :: false:true 1111.12/291.73 hole_entry4_0 :: entry 1111.12/291.73 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.73 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.73 1111.12/291.73 1111.12/291.73 Lemmas: 1111.12/291.73 le(gen_0':s6_0(n8_0), gen_0':s6_0(n8_0)) -> true, rt in Omega(1 + n8_0) 1111.12/291.73 plus(gen_0':s6_0(n319_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n319_0, b)), rt in Omega(1 + n319_0) 1111.12/291.73 1111.12/291.73 1111.12/291.73 Generator Equations: 1111.12/291.73 gen_nil:cons5_0(0) <=> nil 1111.12/291.73 gen_nil:cons5_0(+(x, 1)) <=> cons(entry(0'), gen_nil:cons5_0(x)) 1111.12/291.73 gen_0':s6_0(0) <=> 0' 1111.12/291.73 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.12/291.73 1111.12/291.73 1111.12/291.73 The following defined symbols remain to be analysed: 1111.12/291.73 times, gen, if2 1111.12/291.73 1111.12/291.73 They will be analysed ascendingly in the following order: 1111.12/291.73 gen = if2 1111.12/291.73 times < if2 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (20) LowerBoundPropagationProof (FINISHED) 1111.12/291.73 Propagated lower bound. 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (21) 1111.12/291.73 BOUNDS(n^2, INF) 1111.12/291.73 1111.12/291.73 ---------------------------------------- 1111.12/291.73 1111.12/291.73 (22) 1111.12/291.73 Obligation: 1111.12/291.73 Innermost TRS: 1111.12/291.73 Rules: 1111.12/291.73 table -> gen(s(0')) 1111.12/291.73 gen(x) -> if1(le(x, 10'), x) 1111.12/291.73 if1(false, x) -> nil 1111.12/291.73 if1(true, x) -> if2(x, x) 1111.12/291.73 if2(x, y) -> if3(le(y, 10'), x, y) 1111.12/291.73 if3(true, x, y) -> cons(entry(times(x, y)), if2(x, s(y))) 1111.12/291.73 if3(false, x, y) -> gen(s(x)) 1111.12/291.73 le(0', y) -> true 1111.12/291.73 le(s(x), 0') -> false 1111.12/291.73 le(s(x), s(y)) -> le(x, y) 1111.12/291.73 plus(0', y) -> y 1111.12/291.73 plus(s(x), y) -> s(plus(x, y)) 1111.12/291.73 times(0', y) -> 0' 1111.12/291.73 times(s(x), y) -> plus(y, times(x, y)) 1111.12/291.73 10' -> s(s(s(s(s(s(s(s(s(s(0')))))))))) 1111.12/291.73 1111.12/291.73 Types: 1111.12/291.73 table :: nil:cons 1111.12/291.73 gen :: 0':s -> nil:cons 1111.12/291.73 s :: 0':s -> 0':s 1111.12/291.73 0' :: 0':s 1111.12/291.73 if1 :: false:true -> 0':s -> nil:cons 1111.12/291.73 le :: 0':s -> 0':s -> false:true 1111.12/291.73 10' :: 0':s 1111.12/291.73 false :: false:true 1111.12/291.73 nil :: nil:cons 1111.12/291.73 true :: false:true 1111.12/291.73 if2 :: 0':s -> 0':s -> nil:cons 1111.12/291.73 if3 :: false:true -> 0':s -> 0':s -> nil:cons 1111.12/291.73 cons :: entry -> nil:cons -> nil:cons 1111.12/291.73 entry :: 0':s -> entry 1111.12/291.73 times :: 0':s -> 0':s -> 0':s 1111.12/291.73 plus :: 0':s -> 0':s -> 0':s 1111.12/291.73 hole_nil:cons1_0 :: nil:cons 1111.12/291.73 hole_0':s2_0 :: 0':s 1111.12/291.73 hole_false:true3_0 :: false:true 1111.12/291.73 hole_entry4_0 :: entry 1111.12/291.73 gen_nil:cons5_0 :: Nat -> nil:cons 1111.12/291.73 gen_0':s6_0 :: Nat -> 0':s 1111.12/291.73 1111.12/291.73 1111.12/291.73 Lemmas: 1111.12/291.73 le(gen_0':s6_0(n8_0), gen_0':s6_0(n8_0)) -> true, rt in Omega(1 + n8_0) 1111.12/291.73 plus(gen_0':s6_0(n319_0), gen_0':s6_0(b)) -> gen_0':s6_0(+(n319_0, b)), rt in Omega(1 + n319_0) 1111.12/291.73 times(gen_0':s6_0(n1176_0), gen_0':s6_0(b)) -> gen_0':s6_0(*(n1176_0, b)), rt in Omega(1 + b*n1176_0 + n1176_0) 1111.12/291.73 1111.12/291.73 1111.12/291.73 Generator Equations: 1111.12/291.73 gen_nil:cons5_0(0) <=> nil 1111.12/291.73 gen_nil:cons5_0(+(x, 1)) <=> cons(entry(0'), gen_nil:cons5_0(x)) 1111.12/291.73 gen_0':s6_0(0) <=> 0' 1111.12/291.73 gen_0':s6_0(+(x, 1)) <=> s(gen_0':s6_0(x)) 1111.12/291.73 1111.12/291.73 1111.12/291.73 The following defined symbols remain to be analysed: 1111.12/291.73 if2, gen 1111.12/291.73 1111.12/291.73 They will be analysed ascendingly in the following order: 1111.12/291.73 gen = if2 1111.42/291.78 EOF