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