1118.59/291.85 WORST_CASE(Omega(n^2), ?) 1118.92/291.87 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 1118.92/291.87 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1118.92/291.87 1118.92/291.87 1118.92/291.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.92/291.87 1118.92/291.87 (0) CpxTRS 1118.92/291.87 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.92/291.87 (2) CpxTRS 1118.92/291.87 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1118.92/291.87 (4) typed CpxTrs 1118.92/291.87 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1118.92/291.87 (6) typed CpxTrs 1118.92/291.87 (7) RewriteLemmaProof [LOWER BOUND(ID), 265 ms] 1118.92/291.87 (8) BEST 1118.92/291.87 (9) proven lower bound 1118.92/291.87 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1118.92/291.87 (11) BOUNDS(n^1, INF) 1118.92/291.87 (12) typed CpxTrs 1118.92/291.87 (13) RewriteLemmaProof [LOWER BOUND(ID), 125 ms] 1118.92/291.87 (14) BEST 1118.92/291.87 (15) proven lower bound 1118.92/291.87 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 1118.92/291.87 (17) BOUNDS(n^2, INF) 1118.92/291.87 (18) typed CpxTrs 1118.92/291.87 (19) RewriteLemmaProof [LOWER BOUND(ID), 58 ms] 1118.92/291.87 (20) typed CpxTrs 1118.92/291.87 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (0) 1118.92/291.87 Obligation: 1118.92/291.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.92/291.87 1118.92/291.87 1118.92/291.87 The TRS R consists of the following rules: 1118.92/291.87 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0) -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0) -> 0 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0) -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0), shorter(l, s(0)), l) 1118.92/291.87 if(true, b, l) -> s(0) 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 S is empty. 1118.92/291.87 Rewrite Strategy: INNERMOST 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1118.92/291.87 Renamed function symbols to avoid clashes with predefined symbol. 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (2) 1118.92/291.87 Obligation: 1118.92/291.87 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 1118.92/291.87 1118.92/291.87 1118.92/291.87 The TRS R consists of the following rules: 1118.92/291.87 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 S is empty. 1118.92/291.87 Rewrite Strategy: INNERMOST 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1118.92/291.87 Infered types. 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (4) 1118.92/291.87 Obligation: 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (5) OrderProof (LOWER BOUND(ID)) 1118.92/291.87 Heuristically decided to analyse the following defined symbols: 1118.92/291.87 plus, times, shorter, prod 1118.92/291.87 1118.92/291.87 They will be analysed ascendingly in the following order: 1118.92/291.87 plus < times 1118.92/291.87 times < prod 1118.92/291.87 shorter < prod 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (6) 1118.92/291.87 Obligation: 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 1118.92/291.87 Generator Equations: 1118.92/291.87 gen_0':s4_0(0) <=> 0' 1118.92/291.87 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.92/291.87 gen_cons:nil5_0(0) <=> nil 1118.92/291.87 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1118.92/291.87 1118.92/291.87 1118.92/291.87 The following defined symbols remain to be analysed: 1118.92/291.87 plus, times, shorter, prod 1118.92/291.87 1118.92/291.87 They will be analysed ascendingly in the following order: 1118.92/291.87 plus < times 1118.92/291.87 times < prod 1118.92/291.87 shorter < prod 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1118.92/291.87 Proved the following rewrite lemma: 1118.92/291.87 plus(gen_0':s4_0(n7_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1118.92/291.87 1118.92/291.87 Induction Base: 1118.92/291.87 plus(gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 ifplus(isZero(gen_0':s4_0(0)), gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 ifplus(true, gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 gen_0':s4_0(b) 1118.92/291.87 1118.92/291.87 Induction Step: 1118.92/291.87 plus(gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 ifplus(isZero(gen_0':s4_0(+(n7_0, 1))), gen_0':s4_0(+(n7_0, 1)), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 ifplus(false, gen_0':s4_0(+(1, n7_0)), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 s(plus(p(gen_0':s4_0(+(1, n7_0))), gen_0':s4_0(b))) ->_R^Omega(1) 1118.92/291.87 s(plus(gen_0':s4_0(n7_0), gen_0':s4_0(b))) ->_IH 1118.92/291.87 s(gen_0':s4_0(+(b, c8_0))) 1118.92/291.87 1118.92/291.87 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (8) 1118.92/291.87 Complex Obligation (BEST) 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (9) 1118.92/291.87 Obligation: 1118.92/291.87 Proved the lower bound n^1 for the following obligation: 1118.92/291.87 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 1118.92/291.87 Generator Equations: 1118.92/291.87 gen_0':s4_0(0) <=> 0' 1118.92/291.87 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.92/291.87 gen_cons:nil5_0(0) <=> nil 1118.92/291.87 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1118.92/291.87 1118.92/291.87 1118.92/291.87 The following defined symbols remain to be analysed: 1118.92/291.87 plus, times, shorter, prod 1118.92/291.87 1118.92/291.87 They will be analysed ascendingly in the following order: 1118.92/291.87 plus < times 1118.92/291.87 times < prod 1118.92/291.87 shorter < prod 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (10) LowerBoundPropagationProof (FINISHED) 1118.92/291.87 Propagated lower bound. 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (11) 1118.92/291.87 BOUNDS(n^1, INF) 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (12) 1118.92/291.87 Obligation: 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 1118.92/291.87 Lemmas: 1118.92/291.87 plus(gen_0':s4_0(n7_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1118.92/291.87 1118.92/291.87 1118.92/291.87 Generator Equations: 1118.92/291.87 gen_0':s4_0(0) <=> 0' 1118.92/291.87 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.92/291.87 gen_cons:nil5_0(0) <=> nil 1118.92/291.87 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1118.92/291.87 1118.92/291.87 1118.92/291.87 The following defined symbols remain to be analysed: 1118.92/291.87 times, shorter, prod 1118.92/291.87 1118.92/291.87 They will be analysed ascendingly in the following order: 1118.92/291.87 times < prod 1118.92/291.87 shorter < prod 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (13) RewriteLemmaProof (LOWER BOUND(ID)) 1118.92/291.87 Proved the following rewrite lemma: 1118.92/291.87 times(gen_0':s4_0(n1525_0), gen_0':s4_0(b)) -> gen_0':s4_0(*(n1525_0, b)), rt in Omega(1 + b*n1525_0 + n1525_0) 1118.92/291.87 1118.92/291.87 Induction Base: 1118.92/291.87 times(gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 iftimes(isZero(gen_0':s4_0(0)), gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 iftimes(true, gen_0':s4_0(0), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 0' 1118.92/291.87 1118.92/291.87 Induction Step: 1118.92/291.87 times(gen_0':s4_0(+(n1525_0, 1)), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 iftimes(isZero(gen_0':s4_0(+(n1525_0, 1))), gen_0':s4_0(+(n1525_0, 1)), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 iftimes(false, gen_0':s4_0(+(1, n1525_0)), gen_0':s4_0(b)) ->_R^Omega(1) 1118.92/291.87 plus(gen_0':s4_0(b), times(p(gen_0':s4_0(+(1, n1525_0))), gen_0':s4_0(b))) ->_R^Omega(1) 1118.92/291.87 plus(gen_0':s4_0(b), times(gen_0':s4_0(n1525_0), gen_0':s4_0(b))) ->_IH 1118.92/291.87 plus(gen_0':s4_0(b), gen_0':s4_0(*(c1526_0, b))) ->_L^Omega(1 + b) 1118.92/291.87 gen_0':s4_0(+(b, *(n1525_0, b))) 1118.92/291.87 1118.92/291.87 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (14) 1118.92/291.87 Complex Obligation (BEST) 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (15) 1118.92/291.87 Obligation: 1118.92/291.87 Proved the lower bound n^2 for the following obligation: 1118.92/291.87 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 1118.92/291.87 Lemmas: 1118.92/291.87 plus(gen_0':s4_0(n7_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1118.92/291.87 1118.92/291.87 1118.92/291.87 Generator Equations: 1118.92/291.87 gen_0':s4_0(0) <=> 0' 1118.92/291.87 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.92/291.87 gen_cons:nil5_0(0) <=> nil 1118.92/291.87 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1118.92/291.87 1118.92/291.87 1118.92/291.87 The following defined symbols remain to be analysed: 1118.92/291.87 times, shorter, prod 1118.92/291.87 1118.92/291.87 They will be analysed ascendingly in the following order: 1118.92/291.87 times < prod 1118.92/291.87 shorter < prod 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (16) LowerBoundPropagationProof (FINISHED) 1118.92/291.87 Propagated lower bound. 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (17) 1118.92/291.87 BOUNDS(n^2, INF) 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (18) 1118.92/291.87 Obligation: 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 1118.92/291.87 Lemmas: 1118.92/291.87 plus(gen_0':s4_0(n7_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1118.92/291.87 times(gen_0':s4_0(n1525_0), gen_0':s4_0(b)) -> gen_0':s4_0(*(n1525_0, b)), rt in Omega(1 + b*n1525_0 + n1525_0) 1118.92/291.87 1118.92/291.87 1118.92/291.87 Generator Equations: 1118.92/291.87 gen_0':s4_0(0) <=> 0' 1118.92/291.87 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.92/291.87 gen_cons:nil5_0(0) <=> nil 1118.92/291.87 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1118.92/291.87 1118.92/291.87 1118.92/291.87 The following defined symbols remain to be analysed: 1118.92/291.87 shorter, prod 1118.92/291.87 1118.92/291.87 They will be analysed ascendingly in the following order: 1118.92/291.87 shorter < prod 1118.92/291.87 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (19) RewriteLemmaProof (LOWER BOUND(ID)) 1118.92/291.87 Proved the following rewrite lemma: 1118.92/291.87 shorter(gen_cons:nil5_0(n3763_0), gen_0':s4_0(n3763_0)) -> true, rt in Omega(1 + n3763_0) 1118.92/291.87 1118.92/291.87 Induction Base: 1118.92/291.87 shorter(gen_cons:nil5_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 1118.92/291.87 true 1118.92/291.87 1118.92/291.87 Induction Step: 1118.92/291.87 shorter(gen_cons:nil5_0(+(n3763_0, 1)), gen_0':s4_0(+(n3763_0, 1))) ->_R^Omega(1) 1118.92/291.87 shorter(gen_cons:nil5_0(n3763_0), gen_0':s4_0(n3763_0)) ->_IH 1118.92/291.87 true 1118.92/291.87 1118.92/291.87 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1118.92/291.87 ---------------------------------------- 1118.92/291.87 1118.92/291.87 (20) 1118.92/291.87 Obligation: 1118.92/291.87 Innermost TRS: 1118.92/291.87 Rules: 1118.92/291.87 car(cons(x, l)) -> x 1118.92/291.87 cddr(nil) -> nil 1118.92/291.87 cddr(cons(x, nil)) -> nil 1118.92/291.87 cddr(cons(x, cons(y, l))) -> l 1118.92/291.87 cadr(cons(x, cons(y, l))) -> y 1118.92/291.87 isZero(0') -> true 1118.92/291.87 isZero(s(x)) -> false 1118.92/291.87 plus(x, y) -> ifplus(isZero(x), x, y) 1118.92/291.87 ifplus(true, x, y) -> y 1118.92/291.87 ifplus(false, x, y) -> s(plus(p(x), y)) 1118.92/291.87 times(x, y) -> iftimes(isZero(x), x, y) 1118.92/291.87 iftimes(true, x, y) -> 0' 1118.92/291.87 iftimes(false, x, y) -> plus(y, times(p(x), y)) 1118.92/291.87 p(s(x)) -> x 1118.92/291.87 p(0') -> 0' 1118.92/291.87 shorter(nil, y) -> true 1118.92/291.87 shorter(cons(x, l), 0') -> false 1118.92/291.87 shorter(cons(x, l), s(y)) -> shorter(l, y) 1118.92/291.87 prod(l) -> if(shorter(l, 0'), shorter(l, s(0')), l) 1118.92/291.87 if(true, b, l) -> s(0') 1118.92/291.87 if(false, b, l) -> if2(b, l) 1118.92/291.87 if2(true, l) -> car(l) 1118.92/291.87 if2(false, l) -> prod(cons(times(car(l), cadr(l)), cddr(l))) 1118.92/291.87 1118.92/291.87 Types: 1118.92/291.87 car :: cons:nil -> 0':s 1118.92/291.87 cons :: 0':s -> cons:nil -> cons:nil 1118.92/291.87 cddr :: cons:nil -> cons:nil 1118.92/291.87 nil :: cons:nil 1118.92/291.87 cadr :: cons:nil -> 0':s 1118.92/291.87 isZero :: 0':s -> true:false 1118.92/291.87 0' :: 0':s 1118.92/291.87 true :: true:false 1118.92/291.87 s :: 0':s -> 0':s 1118.92/291.87 false :: true:false 1118.92/291.87 plus :: 0':s -> 0':s -> 0':s 1118.92/291.87 ifplus :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 p :: 0':s -> 0':s 1118.92/291.87 times :: 0':s -> 0':s -> 0':s 1118.92/291.87 iftimes :: true:false -> 0':s -> 0':s -> 0':s 1118.92/291.87 shorter :: cons:nil -> 0':s -> true:false 1118.92/291.87 prod :: cons:nil -> 0':s 1118.92/291.87 if :: true:false -> true:false -> cons:nil -> 0':s 1118.92/291.87 if2 :: true:false -> cons:nil -> 0':s 1118.92/291.87 hole_0':s1_0 :: 0':s 1118.92/291.87 hole_cons:nil2_0 :: cons:nil 1118.92/291.87 hole_true:false3_0 :: true:false 1118.92/291.87 gen_0':s4_0 :: Nat -> 0':s 1118.92/291.87 gen_cons:nil5_0 :: Nat -> cons:nil 1118.92/291.87 1118.92/291.87 1118.92/291.87 Lemmas: 1118.92/291.87 plus(gen_0':s4_0(n7_0), gen_0':s4_0(b)) -> gen_0':s4_0(+(n7_0, b)), rt in Omega(1 + n7_0) 1118.92/291.87 times(gen_0':s4_0(n1525_0), gen_0':s4_0(b)) -> gen_0':s4_0(*(n1525_0, b)), rt in Omega(1 + b*n1525_0 + n1525_0) 1118.92/291.87 shorter(gen_cons:nil5_0(n3763_0), gen_0':s4_0(n3763_0)) -> true, rt in Omega(1 + n3763_0) 1118.92/291.87 1118.92/291.87 1118.92/291.87 Generator Equations: 1118.92/291.87 gen_0':s4_0(0) <=> 0' 1118.92/291.87 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 1118.92/291.87 gen_cons:nil5_0(0) <=> nil 1118.92/291.87 gen_cons:nil5_0(+(x, 1)) <=> cons(0', gen_cons:nil5_0(x)) 1118.92/291.87 1118.92/291.87 1118.92/291.87 The following defined symbols remain to be analysed: 1118.92/291.87 prod 1119.09/291.96 EOF