999.10/291.53 WORST_CASE(Omega(n^2), ?) 999.10/291.54 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 999.10/291.54 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 999.10/291.54 999.10/291.54 999.10/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 999.10/291.54 999.10/291.54 (0) CpxTRS 999.10/291.54 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 999.10/291.54 (2) CpxTRS 999.10/291.54 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 999.10/291.54 (4) typed CpxTrs 999.10/291.54 (5) OrderProof [LOWER BOUND(ID), 0 ms] 999.10/291.54 (6) typed CpxTrs 999.10/291.54 (7) RewriteLemmaProof [LOWER BOUND(ID), 268 ms] 999.10/291.54 (8) BEST 999.10/291.54 (9) proven lower bound 999.10/291.54 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 999.10/291.54 (11) BOUNDS(n^1, INF) 999.10/291.54 (12) typed CpxTrs 999.10/291.54 (13) RewriteLemmaProof [LOWER BOUND(ID), 60 ms] 999.10/291.54 (14) typed CpxTrs 999.10/291.54 (15) RewriteLemmaProof [LOWER BOUND(ID), 63 ms] 999.10/291.54 (16) BEST 999.10/291.54 (17) proven lower bound 999.10/291.54 (18) LowerBoundPropagationProof [FINISHED, 0 ms] 999.10/291.54 (19) BOUNDS(n^2, INF) 999.10/291.54 (20) typed CpxTrs 999.10/291.54 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (0) 999.10/291.54 Obligation: 999.10/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 999.10/291.54 999.10/291.54 999.10/291.54 The TRS R consists of the following rules: 999.10/291.54 999.10/291.54 lt(0, s(x)) -> true 999.10/291.54 lt(x, 0) -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0, y) -> 0 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0, y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0), s(0)) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 S is empty. 999.10/291.54 Rewrite Strategy: FULL 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 999.10/291.54 Renamed function symbols to avoid clashes with predefined symbol. 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (2) 999.10/291.54 Obligation: 999.10/291.54 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). 999.10/291.54 999.10/291.54 999.10/291.54 The TRS R consists of the following rules: 999.10/291.54 999.10/291.54 lt(0', s(x)) -> true 999.10/291.54 lt(x, 0') -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0', y) -> 0' 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0', y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 S is empty. 999.10/291.54 Rewrite Strategy: FULL 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 999.10/291.54 Infered types. 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (4) 999.10/291.54 Obligation: 999.10/291.54 TRS: 999.10/291.54 Rules: 999.10/291.54 lt(0', s(x)) -> true 999.10/291.54 lt(x, 0') -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0', y) -> 0' 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0', y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 Types: 999.10/291.54 lt :: 0':s -> 0':s -> true:false 999.10/291.54 0' :: 0':s 999.10/291.54 s :: 0':s -> 0':s 999.10/291.54 true :: true:false 999.10/291.54 false :: true:false 999.10/291.54 times :: 0':s -> 0':s -> 0':s 999.10/291.54 plus :: 0':s -> 0':s -> 0':s 999.10/291.54 fac :: 0':s -> 0':s 999.10/291.54 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 hole_true:false1_0 :: true:false 999.10/291.54 hole_0':s2_0 :: 0':s 999.10/291.54 gen_0':s3_0 :: Nat -> 0':s 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (5) OrderProof (LOWER BOUND(ID)) 999.10/291.54 Heuristically decided to analyse the following defined symbols: 999.10/291.54 lt, times, plus, loop 999.10/291.54 999.10/291.54 They will be analysed ascendingly in the following order: 999.10/291.54 lt < loop 999.10/291.54 plus < times 999.10/291.54 times < loop 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (6) 999.10/291.54 Obligation: 999.10/291.54 TRS: 999.10/291.54 Rules: 999.10/291.54 lt(0', s(x)) -> true 999.10/291.54 lt(x, 0') -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0', y) -> 0' 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0', y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 Types: 999.10/291.54 lt :: 0':s -> 0':s -> true:false 999.10/291.54 0' :: 0':s 999.10/291.54 s :: 0':s -> 0':s 999.10/291.54 true :: true:false 999.10/291.54 false :: true:false 999.10/291.54 times :: 0':s -> 0':s -> 0':s 999.10/291.54 plus :: 0':s -> 0':s -> 0':s 999.10/291.54 fac :: 0':s -> 0':s 999.10/291.54 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 hole_true:false1_0 :: true:false 999.10/291.54 hole_0':s2_0 :: 0':s 999.10/291.54 gen_0':s3_0 :: Nat -> 0':s 999.10/291.54 999.10/291.54 999.10/291.54 Generator Equations: 999.10/291.54 gen_0':s3_0(0) <=> 0' 999.10/291.54 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 999.10/291.54 999.10/291.54 999.10/291.54 The following defined symbols remain to be analysed: 999.10/291.54 lt, times, plus, loop 999.10/291.54 999.10/291.54 They will be analysed ascendingly in the following order: 999.10/291.54 lt < loop 999.10/291.54 plus < times 999.10/291.54 times < loop 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (7) RewriteLemmaProof (LOWER BOUND(ID)) 999.10/291.54 Proved the following rewrite lemma: 999.10/291.54 lt(gen_0':s3_0(n5_0), gen_0':s3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 999.10/291.54 999.10/291.54 Induction Base: 999.10/291.54 lt(gen_0':s3_0(0), gen_0':s3_0(+(1, 0))) ->_R^Omega(1) 999.10/291.54 true 999.10/291.54 999.10/291.54 Induction Step: 999.10/291.54 lt(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(1, +(n5_0, 1)))) ->_R^Omega(1) 999.10/291.54 lt(gen_0':s3_0(n5_0), gen_0':s3_0(+(1, n5_0))) ->_IH 999.10/291.54 true 999.10/291.54 999.10/291.54 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (8) 999.10/291.54 Complex Obligation (BEST) 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (9) 999.10/291.54 Obligation: 999.10/291.54 Proved the lower bound n^1 for the following obligation: 999.10/291.54 999.10/291.54 TRS: 999.10/291.54 Rules: 999.10/291.54 lt(0', s(x)) -> true 999.10/291.54 lt(x, 0') -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0', y) -> 0' 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0', y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 Types: 999.10/291.54 lt :: 0':s -> 0':s -> true:false 999.10/291.54 0' :: 0':s 999.10/291.54 s :: 0':s -> 0':s 999.10/291.54 true :: true:false 999.10/291.54 false :: true:false 999.10/291.54 times :: 0':s -> 0':s -> 0':s 999.10/291.54 plus :: 0':s -> 0':s -> 0':s 999.10/291.54 fac :: 0':s -> 0':s 999.10/291.54 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 hole_true:false1_0 :: true:false 999.10/291.54 hole_0':s2_0 :: 0':s 999.10/291.54 gen_0':s3_0 :: Nat -> 0':s 999.10/291.54 999.10/291.54 999.10/291.54 Generator Equations: 999.10/291.54 gen_0':s3_0(0) <=> 0' 999.10/291.54 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 999.10/291.54 999.10/291.54 999.10/291.54 The following defined symbols remain to be analysed: 999.10/291.54 lt, times, plus, loop 999.10/291.54 999.10/291.54 They will be analysed ascendingly in the following order: 999.10/291.54 lt < loop 999.10/291.54 plus < times 999.10/291.54 times < loop 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (10) LowerBoundPropagationProof (FINISHED) 999.10/291.54 Propagated lower bound. 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (11) 999.10/291.54 BOUNDS(n^1, INF) 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (12) 999.10/291.54 Obligation: 999.10/291.54 TRS: 999.10/291.54 Rules: 999.10/291.54 lt(0', s(x)) -> true 999.10/291.54 lt(x, 0') -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0', y) -> 0' 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0', y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 Types: 999.10/291.54 lt :: 0':s -> 0':s -> true:false 999.10/291.54 0' :: 0':s 999.10/291.54 s :: 0':s -> 0':s 999.10/291.54 true :: true:false 999.10/291.54 false :: true:false 999.10/291.54 times :: 0':s -> 0':s -> 0':s 999.10/291.54 plus :: 0':s -> 0':s -> 0':s 999.10/291.54 fac :: 0':s -> 0':s 999.10/291.54 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.54 hole_true:false1_0 :: true:false 999.10/291.54 hole_0':s2_0 :: 0':s 999.10/291.54 gen_0':s3_0 :: Nat -> 0':s 999.10/291.54 999.10/291.54 999.10/291.54 Lemmas: 999.10/291.54 lt(gen_0':s3_0(n5_0), gen_0':s3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 999.10/291.54 999.10/291.54 999.10/291.54 Generator Equations: 999.10/291.54 gen_0':s3_0(0) <=> 0' 999.10/291.54 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 999.10/291.54 999.10/291.54 999.10/291.54 The following defined symbols remain to be analysed: 999.10/291.54 plus, times, loop 999.10/291.54 999.10/291.54 They will be analysed ascendingly in the following order: 999.10/291.54 plus < times 999.10/291.54 times < loop 999.10/291.54 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (13) RewriteLemmaProof (LOWER BOUND(ID)) 999.10/291.54 Proved the following rewrite lemma: 999.10/291.54 plus(gen_0':s3_0(n257_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n257_0, b)), rt in Omega(1 + n257_0) 999.10/291.54 999.10/291.54 Induction Base: 999.10/291.54 plus(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 999.10/291.54 gen_0':s3_0(b) 999.10/291.54 999.10/291.54 Induction Step: 999.10/291.54 plus(gen_0':s3_0(+(n257_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 999.10/291.54 s(plus(gen_0':s3_0(n257_0), gen_0':s3_0(b))) ->_IH 999.10/291.54 s(gen_0':s3_0(+(b, c258_0))) 999.10/291.54 999.10/291.54 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 999.10/291.54 ---------------------------------------- 999.10/291.54 999.10/291.54 (14) 999.10/291.54 Obligation: 999.10/291.54 TRS: 999.10/291.54 Rules: 999.10/291.54 lt(0', s(x)) -> true 999.10/291.54 lt(x, 0') -> false 999.10/291.54 lt(s(x), s(y)) -> lt(x, y) 999.10/291.54 times(0', y) -> 0' 999.10/291.54 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.54 plus(0', y) -> y 999.10/291.54 plus(s(x), y) -> s(plus(x, y)) 999.10/291.54 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.54 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.54 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.54 if(true, x, c, y) -> y 999.10/291.54 999.10/291.54 Types: 999.10/291.54 lt :: 0':s -> 0':s -> true:false 999.10/291.55 0' :: 0':s 999.10/291.55 s :: 0':s -> 0':s 999.10/291.55 true :: true:false 999.10/291.55 false :: true:false 999.10/291.55 times :: 0':s -> 0':s -> 0':s 999.10/291.55 plus :: 0':s -> 0':s -> 0':s 999.10/291.55 fac :: 0':s -> 0':s 999.10/291.55 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.55 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.55 hole_true:false1_0 :: true:false 999.10/291.55 hole_0':s2_0 :: 0':s 999.10/291.55 gen_0':s3_0 :: Nat -> 0':s 999.10/291.55 999.10/291.55 999.10/291.55 Lemmas: 999.10/291.55 lt(gen_0':s3_0(n5_0), gen_0':s3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 999.10/291.55 plus(gen_0':s3_0(n257_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n257_0, b)), rt in Omega(1 + n257_0) 999.10/291.55 999.10/291.55 999.10/291.55 Generator Equations: 999.10/291.55 gen_0':s3_0(0) <=> 0' 999.10/291.55 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 999.10/291.55 999.10/291.55 999.10/291.55 The following defined symbols remain to be analysed: 999.10/291.55 times, loop 999.10/291.55 999.10/291.55 They will be analysed ascendingly in the following order: 999.10/291.55 times < loop 999.10/291.55 999.10/291.55 ---------------------------------------- 999.10/291.55 999.10/291.55 (15) RewriteLemmaProof (LOWER BOUND(ID)) 999.10/291.55 Proved the following rewrite lemma: 999.10/291.55 times(gen_0':s3_0(n800_0), gen_0':s3_0(b)) -> gen_0':s3_0(*(n800_0, b)), rt in Omega(1 + b*n800_0 + n800_0) 999.10/291.55 999.10/291.55 Induction Base: 999.10/291.55 times(gen_0':s3_0(0), gen_0':s3_0(b)) ->_R^Omega(1) 999.10/291.55 0' 999.10/291.55 999.10/291.55 Induction Step: 999.10/291.55 times(gen_0':s3_0(+(n800_0, 1)), gen_0':s3_0(b)) ->_R^Omega(1) 999.10/291.55 plus(gen_0':s3_0(b), times(gen_0':s3_0(n800_0), gen_0':s3_0(b))) ->_IH 999.10/291.55 plus(gen_0':s3_0(b), gen_0':s3_0(*(c801_0, b))) ->_L^Omega(1 + b) 999.10/291.55 gen_0':s3_0(+(b, *(n800_0, b))) 999.10/291.55 999.10/291.55 We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). 999.10/291.55 ---------------------------------------- 999.10/291.55 999.10/291.55 (16) 999.10/291.55 Complex Obligation (BEST) 999.10/291.55 999.10/291.55 ---------------------------------------- 999.10/291.55 999.10/291.55 (17) 999.10/291.55 Obligation: 999.10/291.55 Proved the lower bound n^2 for the following obligation: 999.10/291.55 999.10/291.55 TRS: 999.10/291.55 Rules: 999.10/291.55 lt(0', s(x)) -> true 999.10/291.55 lt(x, 0') -> false 999.10/291.55 lt(s(x), s(y)) -> lt(x, y) 999.10/291.55 times(0', y) -> 0' 999.10/291.55 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.55 plus(0', y) -> y 999.10/291.55 plus(s(x), y) -> s(plus(x, y)) 999.10/291.55 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.55 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.55 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.55 if(true, x, c, y) -> y 999.10/291.55 999.10/291.55 Types: 999.10/291.55 lt :: 0':s -> 0':s -> true:false 999.10/291.55 0' :: 0':s 999.10/291.55 s :: 0':s -> 0':s 999.10/291.55 true :: true:false 999.10/291.55 false :: true:false 999.10/291.55 times :: 0':s -> 0':s -> 0':s 999.10/291.55 plus :: 0':s -> 0':s -> 0':s 999.10/291.55 fac :: 0':s -> 0':s 999.10/291.55 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.55 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.55 hole_true:false1_0 :: true:false 999.10/291.55 hole_0':s2_0 :: 0':s 999.10/291.55 gen_0':s3_0 :: Nat -> 0':s 999.10/291.55 999.10/291.55 999.10/291.55 Lemmas: 999.10/291.55 lt(gen_0':s3_0(n5_0), gen_0':s3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 999.10/291.55 plus(gen_0':s3_0(n257_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n257_0, b)), rt in Omega(1 + n257_0) 999.10/291.55 999.10/291.55 999.10/291.55 Generator Equations: 999.10/291.55 gen_0':s3_0(0) <=> 0' 999.10/291.55 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 999.10/291.55 999.10/291.55 999.10/291.55 The following defined symbols remain to be analysed: 999.10/291.55 times, loop 999.10/291.55 999.10/291.55 They will be analysed ascendingly in the following order: 999.10/291.55 times < loop 999.10/291.55 999.10/291.55 ---------------------------------------- 999.10/291.55 999.10/291.55 (18) LowerBoundPropagationProof (FINISHED) 999.10/291.55 Propagated lower bound. 999.10/291.55 ---------------------------------------- 999.10/291.55 999.10/291.55 (19) 999.10/291.55 BOUNDS(n^2, INF) 999.10/291.55 999.10/291.55 ---------------------------------------- 999.10/291.55 999.10/291.55 (20) 999.10/291.55 Obligation: 999.10/291.55 TRS: 999.10/291.55 Rules: 999.10/291.55 lt(0', s(x)) -> true 999.10/291.55 lt(x, 0') -> false 999.10/291.55 lt(s(x), s(y)) -> lt(x, y) 999.10/291.55 times(0', y) -> 0' 999.10/291.55 times(s(x), y) -> plus(y, times(x, y)) 999.10/291.55 plus(0', y) -> y 999.10/291.55 plus(s(x), y) -> s(plus(x, y)) 999.10/291.55 fac(x) -> loop(x, s(0'), s(0')) 999.10/291.55 loop(x, c, y) -> if(lt(x, c), x, c, y) 999.10/291.55 if(false, x, c, y) -> loop(x, s(c), times(y, s(c))) 999.10/291.55 if(true, x, c, y) -> y 999.10/291.55 999.10/291.55 Types: 999.10/291.55 lt :: 0':s -> 0':s -> true:false 999.10/291.55 0' :: 0':s 999.10/291.55 s :: 0':s -> 0':s 999.10/291.55 true :: true:false 999.10/291.55 false :: true:false 999.10/291.55 times :: 0':s -> 0':s -> 0':s 999.10/291.55 plus :: 0':s -> 0':s -> 0':s 999.10/291.55 fac :: 0':s -> 0':s 999.10/291.55 loop :: 0':s -> 0':s -> 0':s -> 0':s 999.10/291.55 if :: true:false -> 0':s -> 0':s -> 0':s -> 0':s 999.10/291.55 hole_true:false1_0 :: true:false 999.10/291.55 hole_0':s2_0 :: 0':s 999.10/291.55 gen_0':s3_0 :: Nat -> 0':s 999.10/291.55 999.10/291.55 999.10/291.55 Lemmas: 999.10/291.55 lt(gen_0':s3_0(n5_0), gen_0':s3_0(+(1, n5_0))) -> true, rt in Omega(1 + n5_0) 999.10/291.55 plus(gen_0':s3_0(n257_0), gen_0':s3_0(b)) -> gen_0':s3_0(+(n257_0, b)), rt in Omega(1 + n257_0) 999.10/291.55 times(gen_0':s3_0(n800_0), gen_0':s3_0(b)) -> gen_0':s3_0(*(n800_0, b)), rt in Omega(1 + b*n800_0 + n800_0) 999.10/291.55 999.10/291.55 999.10/291.55 Generator Equations: 999.10/291.55 gen_0':s3_0(0) <=> 0' 999.10/291.55 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 999.10/291.55 999.10/291.55 999.10/291.55 The following defined symbols remain to be analysed: 999.10/291.55 loop 999.10/291.60 EOF