357.09/291.54 WORST_CASE(Omega(n^1), ?) 358.11/291.85 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 358.11/291.85 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 358.11/291.85 358.11/291.85 358.11/291.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 358.11/291.85 358.11/291.85 (0) CpxTRS 358.11/291.85 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 358.11/291.85 (2) CpxTRS 358.11/291.85 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 358.11/291.85 (4) typed CpxTrs 358.11/291.85 (5) OrderProof [LOWER BOUND(ID), 0 ms] 358.11/291.85 (6) typed CpxTrs 358.11/291.85 (7) RewriteLemmaProof [LOWER BOUND(ID), 311 ms] 358.11/291.85 (8) BEST 358.11/291.85 (9) proven lower bound 358.11/291.85 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 358.11/291.85 (11) BOUNDS(n^1, INF) 358.11/291.85 (12) typed CpxTrs 358.11/291.85 (13) RewriteLemmaProof [LOWER BOUND(ID), 75 ms] 358.11/291.85 (14) typed CpxTrs 358.11/291.85 (15) RewriteLemmaProof [LOWER BOUND(ID), 65 ms] 358.11/291.85 (16) typed CpxTrs 358.11/291.85 (17) RewriteLemmaProof [LOWER BOUND(ID), 127 ms] 358.11/291.85 (18) typed CpxTrs 358.11/291.85 358.11/291.85 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (0) 358.11/291.85 Obligation: 358.11/291.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 358.11/291.85 358.11/291.85 358.11/291.85 The TRS R consists of the following rules: 358.11/291.85 358.11/291.85 min(x, 0) -> 0 358.11/291.85 min(0, y) -> 0 358.11/291.85 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.85 max(x, 0) -> x 358.11/291.85 max(0, y) -> y 358.11/291.85 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.85 minus(x, 0) -> x 358.11/291.85 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.85 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.85 transform(x) -> s(s(x)) 358.11/291.85 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.85 transform(cons(x, y)) -> y 358.11/291.85 transform(s(x)) -> s(s(transform(x))) 358.11/291.85 cons(x, y) -> y 358.11/291.85 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.85 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.85 358.11/291.85 S is empty. 358.11/291.85 Rewrite Strategy: FULL 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 358.11/291.85 Renamed function symbols to avoid clashes with predefined symbol. 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (2) 358.11/291.85 Obligation: 358.11/291.85 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 358.11/291.85 358.11/291.85 358.11/291.85 The TRS R consists of the following rules: 358.11/291.85 358.11/291.85 min(x, 0') -> 0' 358.11/291.85 min(0', y) -> 0' 358.11/291.85 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.85 max(x, 0') -> x 358.11/291.85 max(0', y) -> y 358.11/291.85 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.85 minus(x, 0') -> x 358.11/291.85 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.85 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.85 transform(x) -> s(s(x)) 358.11/291.85 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.85 transform(cons(x, y)) -> y 358.11/291.85 transform(s(x)) -> s(s(transform(x))) 358.11/291.85 cons(x, y) -> y 358.11/291.85 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.85 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.85 358.11/291.85 S is empty. 358.11/291.85 Rewrite Strategy: FULL 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 358.11/291.85 Infered types. 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (4) 358.11/291.85 Obligation: 358.11/291.85 TRS: 358.11/291.85 Rules: 358.11/291.85 min(x, 0') -> 0' 358.11/291.85 min(0', y) -> 0' 358.11/291.85 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.85 max(x, 0') -> x 358.11/291.85 max(0', y) -> y 358.11/291.85 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.85 minus(x, 0') -> x 358.11/291.85 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.85 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.85 transform(x) -> s(s(x)) 358.11/291.85 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.85 transform(cons(x, y)) -> y 358.11/291.85 transform(s(x)) -> s(s(transform(x))) 358.11/291.85 cons(x, y) -> y 358.11/291.85 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.85 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.85 358.11/291.85 Types: 358.11/291.85 min :: 0':s -> 0':s -> 0':s 358.11/291.85 0' :: 0':s 358.11/291.85 s :: 0':s -> 0':s 358.11/291.85 max :: 0':s -> 0':s -> 0':s 358.11/291.85 minus :: 0':s -> 0':s -> 0':s 358.11/291.85 gcd :: 0':s -> 0':s -> gcd 358.11/291.85 transform :: 0':s -> 0':s 358.11/291.85 cons :: 0':s -> 0':s -> 0':s 358.11/291.85 hole_0':s1_0 :: 0':s 358.11/291.85 hole_gcd2_0 :: gcd 358.11/291.85 gen_0':s3_0 :: Nat -> 0':s 358.11/291.85 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (5) OrderProof (LOWER BOUND(ID)) 358.11/291.85 Heuristically decided to analyse the following defined symbols: 358.11/291.85 min, max, minus, gcd, transform, cons 358.11/291.85 358.11/291.85 They will be analysed ascendingly in the following order: 358.11/291.85 min < gcd 358.11/291.85 max < gcd 358.11/291.85 minus < gcd 358.11/291.85 transform < gcd 358.11/291.85 transform = cons 358.11/291.85 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (6) 358.11/291.85 Obligation: 358.11/291.85 TRS: 358.11/291.85 Rules: 358.11/291.85 min(x, 0') -> 0' 358.11/291.85 min(0', y) -> 0' 358.11/291.85 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.85 max(x, 0') -> x 358.11/291.85 max(0', y) -> y 358.11/291.85 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.85 minus(x, 0') -> x 358.11/291.85 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.85 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.85 transform(x) -> s(s(x)) 358.11/291.85 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.85 transform(cons(x, y)) -> y 358.11/291.85 transform(s(x)) -> s(s(transform(x))) 358.11/291.85 cons(x, y) -> y 358.11/291.85 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.85 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.85 358.11/291.85 Types: 358.11/291.85 min :: 0':s -> 0':s -> 0':s 358.11/291.85 0' :: 0':s 358.11/291.85 s :: 0':s -> 0':s 358.11/291.85 max :: 0':s -> 0':s -> 0':s 358.11/291.85 minus :: 0':s -> 0':s -> 0':s 358.11/291.85 gcd :: 0':s -> 0':s -> gcd 358.11/291.85 transform :: 0':s -> 0':s 358.11/291.85 cons :: 0':s -> 0':s -> 0':s 358.11/291.85 hole_0':s1_0 :: 0':s 358.11/291.85 hole_gcd2_0 :: gcd 358.11/291.85 gen_0':s3_0 :: Nat -> 0':s 358.11/291.85 358.11/291.85 358.11/291.85 Generator Equations: 358.11/291.85 gen_0':s3_0(0) <=> 0' 358.11/291.85 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 358.11/291.85 358.11/291.85 358.11/291.85 The following defined symbols remain to be analysed: 358.11/291.85 min, max, minus, gcd, transform, cons 358.11/291.85 358.11/291.85 They will be analysed ascendingly in the following order: 358.11/291.85 min < gcd 358.11/291.85 max < gcd 358.11/291.85 minus < gcd 358.11/291.85 transform < gcd 358.11/291.85 transform = cons 358.11/291.85 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (7) RewriteLemmaProof (LOWER BOUND(ID)) 358.11/291.85 Proved the following rewrite lemma: 358.11/291.85 min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 358.11/291.85 358.11/291.85 Induction Base: 358.11/291.85 min(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 358.11/291.85 0' 358.11/291.85 358.11/291.85 Induction Step: 358.11/291.85 min(gen_0':s3_0(+(n5_0, 1)), gen_0':s3_0(+(n5_0, 1))) ->_R^Omega(1) 358.11/291.85 s(min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0))) ->_IH 358.11/291.85 s(gen_0':s3_0(c6_0)) 358.11/291.85 358.11/291.85 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (8) 358.11/291.85 Complex Obligation (BEST) 358.11/291.85 358.11/291.85 ---------------------------------------- 358.11/291.85 358.11/291.85 (9) 358.11/291.85 Obligation: 358.11/291.85 Proved the lower bound n^1 for the following obligation: 358.11/291.85 358.11/291.85 TRS: 358.11/291.85 Rules: 358.11/291.85 min(x, 0') -> 0' 358.11/291.85 min(0', y) -> 0' 358.11/291.85 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.85 max(x, 0') -> x 358.11/291.85 max(0', y) -> y 358.11/291.85 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.85 minus(x, 0') -> x 358.11/291.85 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.85 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.85 transform(x) -> s(s(x)) 358.11/291.85 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.85 transform(cons(x, y)) -> y 358.11/291.85 transform(s(x)) -> s(s(transform(x))) 358.11/291.85 cons(x, y) -> y 358.11/291.85 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.85 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.85 358.11/291.85 Types: 358.11/291.85 min :: 0':s -> 0':s -> 0':s 358.11/291.86 0' :: 0':s 358.11/291.86 s :: 0':s -> 0':s 358.11/291.86 max :: 0':s -> 0':s -> 0':s 358.11/291.86 minus :: 0':s -> 0':s -> 0':s 358.11/291.86 gcd :: 0':s -> 0':s -> gcd 358.11/291.86 transform :: 0':s -> 0':s 358.11/291.86 cons :: 0':s -> 0':s -> 0':s 358.11/291.86 hole_0':s1_0 :: 0':s 358.11/291.86 hole_gcd2_0 :: gcd 358.11/291.86 gen_0':s3_0 :: Nat -> 0':s 358.11/291.86 358.11/291.86 358.11/291.86 Generator Equations: 358.11/291.86 gen_0':s3_0(0) <=> 0' 358.11/291.86 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 358.11/291.86 358.11/291.86 358.11/291.86 The following defined symbols remain to be analysed: 358.11/291.86 min, max, minus, gcd, transform, cons 358.11/291.86 358.11/291.86 They will be analysed ascendingly in the following order: 358.11/291.86 min < gcd 358.11/291.86 max < gcd 358.11/291.86 minus < gcd 358.11/291.86 transform < gcd 358.11/291.86 transform = cons 358.11/291.86 358.11/291.86 ---------------------------------------- 358.11/291.86 358.11/291.86 (10) LowerBoundPropagationProof (FINISHED) 358.11/291.86 Propagated lower bound. 358.11/291.86 ---------------------------------------- 358.11/291.86 358.11/291.86 (11) 358.11/291.86 BOUNDS(n^1, INF) 358.11/291.86 358.11/291.86 ---------------------------------------- 358.11/291.86 358.11/291.86 (12) 358.11/291.86 Obligation: 358.11/291.86 TRS: 358.11/291.86 Rules: 358.11/291.86 min(x, 0') -> 0' 358.11/291.86 min(0', y) -> 0' 358.11/291.86 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.86 max(x, 0') -> x 358.11/291.86 max(0', y) -> y 358.11/291.86 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.86 minus(x, 0') -> x 358.11/291.86 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.86 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.86 transform(x) -> s(s(x)) 358.11/291.86 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.86 transform(cons(x, y)) -> y 358.11/291.86 transform(s(x)) -> s(s(transform(x))) 358.11/291.86 cons(x, y) -> y 358.11/291.86 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.86 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.86 358.11/291.86 Types: 358.11/291.86 min :: 0':s -> 0':s -> 0':s 358.11/291.86 0' :: 0':s 358.11/291.86 s :: 0':s -> 0':s 358.11/291.86 max :: 0':s -> 0':s -> 0':s 358.11/291.86 minus :: 0':s -> 0':s -> 0':s 358.11/291.86 gcd :: 0':s -> 0':s -> gcd 358.11/291.86 transform :: 0':s -> 0':s 358.11/291.86 cons :: 0':s -> 0':s -> 0':s 358.11/291.86 hole_0':s1_0 :: 0':s 358.11/291.86 hole_gcd2_0 :: gcd 358.11/291.86 gen_0':s3_0 :: Nat -> 0':s 358.11/291.86 358.11/291.86 358.11/291.86 Lemmas: 358.11/291.86 min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 358.11/291.86 358.11/291.86 358.11/291.86 Generator Equations: 358.11/291.86 gen_0':s3_0(0) <=> 0' 358.11/291.86 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 358.11/291.86 358.11/291.86 358.11/291.86 The following defined symbols remain to be analysed: 358.11/291.86 max, minus, gcd, transform, cons 358.11/291.86 358.11/291.86 They will be analysed ascendingly in the following order: 358.11/291.86 max < gcd 358.11/291.86 minus < gcd 358.11/291.86 transform < gcd 358.11/291.86 transform = cons 358.11/291.86 358.11/291.86 ---------------------------------------- 358.11/291.86 358.11/291.86 (13) RewriteLemmaProof (LOWER BOUND(ID)) 358.11/291.86 Proved the following rewrite lemma: 358.11/291.86 max(gen_0':s3_0(n336_0), gen_0':s3_0(n336_0)) -> gen_0':s3_0(n336_0), rt in Omega(1 + n336_0) 358.11/291.86 358.11/291.86 Induction Base: 358.11/291.86 max(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 358.11/291.86 gen_0':s3_0(0) 358.11/291.86 358.11/291.86 Induction Step: 358.11/291.86 max(gen_0':s3_0(+(n336_0, 1)), gen_0':s3_0(+(n336_0, 1))) ->_R^Omega(1) 358.11/291.86 s(max(gen_0':s3_0(n336_0), gen_0':s3_0(n336_0))) ->_IH 358.11/291.86 s(gen_0':s3_0(c337_0)) 358.11/291.86 358.11/291.86 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 358.11/291.86 ---------------------------------------- 358.11/291.86 358.11/291.86 (14) 358.11/291.86 Obligation: 358.11/291.86 TRS: 358.11/291.86 Rules: 358.11/291.86 min(x, 0') -> 0' 358.11/291.86 min(0', y) -> 0' 358.11/291.86 min(s(x), s(y)) -> s(min(x, y)) 358.11/291.86 max(x, 0') -> x 358.11/291.86 max(0', y) -> y 358.11/291.86 max(s(x), s(y)) -> s(max(x, y)) 358.11/291.86 minus(x, 0') -> x 358.11/291.86 minus(s(x), s(y)) -> s(minus(x, y)) 358.11/291.86 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.11/291.86 transform(x) -> s(s(x)) 358.11/291.86 transform(cons(x, y)) -> cons(cons(x, x), x) 358.11/291.86 transform(cons(x, y)) -> y 358.11/291.86 transform(s(x)) -> s(s(transform(x))) 358.11/291.86 cons(x, y) -> y 358.11/291.86 cons(x, cons(y, s(z))) -> cons(y, x) 358.11/291.86 cons(cons(x, z), s(y)) -> transform(x) 358.11/291.86 358.11/291.86 Types: 358.11/291.86 min :: 0':s -> 0':s -> 0':s 358.11/291.86 0' :: 0':s 358.11/291.86 s :: 0':s -> 0':s 358.11/291.86 max :: 0':s -> 0':s -> 0':s 358.11/291.86 minus :: 0':s -> 0':s -> 0':s 358.11/291.86 gcd :: 0':s -> 0':s -> gcd 358.11/291.86 transform :: 0':s -> 0':s 358.11/291.86 cons :: 0':s -> 0':s -> 0':s 358.11/291.86 hole_0':s1_0 :: 0':s 358.11/291.86 hole_gcd2_0 :: gcd 358.11/291.86 gen_0':s3_0 :: Nat -> 0':s 358.11/291.86 358.11/291.86 358.11/291.86 Lemmas: 358.11/291.86 min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 358.11/291.86 max(gen_0':s3_0(n336_0), gen_0':s3_0(n336_0)) -> gen_0':s3_0(n336_0), rt in Omega(1 + n336_0) 358.11/291.86 358.11/291.86 358.11/291.86 Generator Equations: 358.11/291.86 gen_0':s3_0(0) <=> 0' 358.11/291.86 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 358.11/291.86 358.11/291.86 358.11/291.86 The following defined symbols remain to be analysed: 358.11/291.86 minus, gcd, transform, cons 358.11/291.86 358.11/291.86 They will be analysed ascendingly in the following order: 358.11/291.86 minus < gcd 358.11/291.86 transform < gcd 358.11/291.86 transform = cons 358.11/291.86 358.11/291.86 ---------------------------------------- 358.11/291.86 358.11/291.86 (15) RewriteLemmaProof (LOWER BOUND(ID)) 358.11/291.86 Proved the following rewrite lemma: 358.11/291.86 minus(gen_0':s3_0(n757_0), gen_0':s3_0(n757_0)) -> gen_0':s3_0(n757_0), rt in Omega(1 + n757_0) 358.11/291.86 358.11/291.86 Induction Base: 358.11/291.86 minus(gen_0':s3_0(0), gen_0':s3_0(0)) ->_R^Omega(1) 358.11/291.86 gen_0':s3_0(0) 358.11/291.86 358.11/291.86 Induction Step: 358.11/291.86 minus(gen_0':s3_0(+(n757_0, 1)), gen_0':s3_0(+(n757_0, 1))) ->_R^Omega(1) 358.39/291.86 s(minus(gen_0':s3_0(n757_0), gen_0':s3_0(n757_0))) ->_IH 358.39/291.86 s(gen_0':s3_0(c758_0)) 358.39/291.86 358.39/291.86 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 358.39/291.86 ---------------------------------------- 358.39/291.86 358.39/291.86 (16) 358.39/291.86 Obligation: 358.39/291.86 TRS: 358.39/291.86 Rules: 358.39/291.86 min(x, 0') -> 0' 358.39/291.86 min(0', y) -> 0' 358.39/291.86 min(s(x), s(y)) -> s(min(x, y)) 358.39/291.86 max(x, 0') -> x 358.39/291.86 max(0', y) -> y 358.39/291.86 max(s(x), s(y)) -> s(max(x, y)) 358.39/291.86 minus(x, 0') -> x 358.39/291.86 minus(s(x), s(y)) -> s(minus(x, y)) 358.39/291.86 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.39/291.86 transform(x) -> s(s(x)) 358.39/291.86 transform(cons(x, y)) -> cons(cons(x, x), x) 358.39/291.86 transform(cons(x, y)) -> y 358.39/291.86 transform(s(x)) -> s(s(transform(x))) 358.39/291.86 cons(x, y) -> y 358.39/291.86 cons(x, cons(y, s(z))) -> cons(y, x) 358.39/291.86 cons(cons(x, z), s(y)) -> transform(x) 358.39/291.86 358.39/291.86 Types: 358.39/291.86 min :: 0':s -> 0':s -> 0':s 358.39/291.86 0' :: 0':s 358.39/291.86 s :: 0':s -> 0':s 358.39/291.86 max :: 0':s -> 0':s -> 0':s 358.39/291.86 minus :: 0':s -> 0':s -> 0':s 358.39/291.86 gcd :: 0':s -> 0':s -> gcd 358.39/291.86 transform :: 0':s -> 0':s 358.39/291.86 cons :: 0':s -> 0':s -> 0':s 358.39/291.86 hole_0':s1_0 :: 0':s 358.39/291.86 hole_gcd2_0 :: gcd 358.39/291.86 gen_0':s3_0 :: Nat -> 0':s 358.39/291.86 358.39/291.86 358.39/291.86 Lemmas: 358.39/291.86 min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 358.39/291.86 max(gen_0':s3_0(n336_0), gen_0':s3_0(n336_0)) -> gen_0':s3_0(n336_0), rt in Omega(1 + n336_0) 358.39/291.86 minus(gen_0':s3_0(n757_0), gen_0':s3_0(n757_0)) -> gen_0':s3_0(n757_0), rt in Omega(1 + n757_0) 358.39/291.86 358.39/291.86 358.39/291.86 Generator Equations: 358.39/291.86 gen_0':s3_0(0) <=> 0' 358.39/291.86 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 358.39/291.86 358.39/291.86 358.39/291.86 The following defined symbols remain to be analysed: 358.39/291.86 cons, gcd, transform 358.39/291.86 358.39/291.86 They will be analysed ascendingly in the following order: 358.39/291.86 transform < gcd 358.39/291.86 transform = cons 358.39/291.86 358.39/291.86 ---------------------------------------- 358.39/291.86 358.39/291.86 (17) RewriteLemmaProof (LOWER BOUND(ID)) 358.39/291.86 Proved the following rewrite lemma: 358.39/291.86 transform(gen_0':s3_0(+(1, n1160_0))) -> *4_0, rt in Omega(n1160_0) 358.39/291.86 358.39/291.86 Induction Base: 358.39/291.86 transform(gen_0':s3_0(+(1, 0))) 358.39/291.86 358.39/291.86 Induction Step: 358.39/291.86 transform(gen_0':s3_0(+(1, +(n1160_0, 1)))) ->_R^Omega(1) 358.39/291.86 s(s(transform(gen_0':s3_0(+(1, n1160_0))))) ->_IH 358.39/291.86 s(s(*4_0)) 358.39/291.86 358.39/291.86 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 358.39/291.86 ---------------------------------------- 358.39/291.86 358.39/291.86 (18) 358.39/291.86 Obligation: 358.39/291.86 TRS: 358.39/291.86 Rules: 358.39/291.86 min(x, 0') -> 0' 358.39/291.86 min(0', y) -> 0' 358.39/291.86 min(s(x), s(y)) -> s(min(x, y)) 358.39/291.86 max(x, 0') -> x 358.39/291.86 max(0', y) -> y 358.39/291.86 max(s(x), s(y)) -> s(max(x, y)) 358.39/291.86 minus(x, 0') -> x 358.39/291.86 minus(s(x), s(y)) -> s(minus(x, y)) 358.39/291.86 gcd(s(x), s(y)) -> gcd(minus(max(x, y), min(x, transform(y))), s(min(x, y))) 358.39/291.86 transform(x) -> s(s(x)) 358.39/291.86 transform(cons(x, y)) -> cons(cons(x, x), x) 358.39/291.86 transform(cons(x, y)) -> y 358.39/291.86 transform(s(x)) -> s(s(transform(x))) 358.39/291.86 cons(x, y) -> y 358.39/291.86 cons(x, cons(y, s(z))) -> cons(y, x) 358.39/291.86 cons(cons(x, z), s(y)) -> transform(x) 358.39/291.86 358.39/291.86 Types: 358.39/291.86 min :: 0':s -> 0':s -> 0':s 358.39/291.86 0' :: 0':s 358.39/291.86 s :: 0':s -> 0':s 358.39/291.86 max :: 0':s -> 0':s -> 0':s 358.39/291.86 minus :: 0':s -> 0':s -> 0':s 358.39/291.86 gcd :: 0':s -> 0':s -> gcd 358.39/291.86 transform :: 0':s -> 0':s 358.39/291.86 cons :: 0':s -> 0':s -> 0':s 358.39/291.86 hole_0':s1_0 :: 0':s 358.39/291.86 hole_gcd2_0 :: gcd 358.39/291.86 gen_0':s3_0 :: Nat -> 0':s 358.39/291.86 358.39/291.86 358.39/291.86 Lemmas: 358.39/291.86 min(gen_0':s3_0(n5_0), gen_0':s3_0(n5_0)) -> gen_0':s3_0(n5_0), rt in Omega(1 + n5_0) 358.39/291.86 max(gen_0':s3_0(n336_0), gen_0':s3_0(n336_0)) -> gen_0':s3_0(n336_0), rt in Omega(1 + n336_0) 358.39/291.86 minus(gen_0':s3_0(n757_0), gen_0':s3_0(n757_0)) -> gen_0':s3_0(n757_0), rt in Omega(1 + n757_0) 358.39/291.86 transform(gen_0':s3_0(+(1, n1160_0))) -> *4_0, rt in Omega(n1160_0) 358.39/291.86 358.39/291.86 358.39/291.86 Generator Equations: 358.39/291.86 gen_0':s3_0(0) <=> 0' 358.39/291.86 gen_0':s3_0(+(x, 1)) <=> s(gen_0':s3_0(x)) 358.39/291.86 358.39/291.86 358.39/291.86 The following defined symbols remain to be analysed: 358.39/291.86 cons, gcd 358.39/291.86 358.39/291.86 They will be analysed ascendingly in the following order: 358.39/291.86 transform < gcd 358.39/291.86 transform = cons 358.42/291.89 EOF