309.99/291.48 WORST_CASE(Omega(n^1), ?) 309.99/291.49 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 309.99/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 309.99/291.49 309.99/291.49 309.99/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 309.99/291.49 309.99/291.49 (0) CpxTRS 309.99/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 309.99/291.49 (2) CpxTRS 309.99/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 309.99/291.49 (4) typed CpxTrs 309.99/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 309.99/291.49 (6) typed CpxTrs 309.99/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 324 ms] 309.99/291.49 (8) BEST 309.99/291.49 (9) proven lower bound 309.99/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 309.99/291.49 (11) BOUNDS(n^1, INF) 309.99/291.49 (12) typed CpxTrs 309.99/291.49 (13) RewriteLemmaProof [LOWER BOUND(ID), 58 ms] 309.99/291.49 (14) typed CpxTrs 309.99/291.49 (15) RewriteLemmaProof [LOWER BOUND(ID), 13 ms] 309.99/291.49 (16) typed CpxTrs 309.99/291.49 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (0) 309.99/291.49 Obligation: 309.99/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 309.99/291.49 309.99/291.49 309.99/291.49 The TRS R consists of the following rules: 309.99/291.49 309.99/291.49 min(x, 0) -> 0 309.99/291.49 min(0, y) -> 0 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0) -> x 309.99/291.49 max(0, y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0) -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0) -> s(x) 309.99/291.49 gcd(0, s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 S is empty. 309.99/291.49 Rewrite Strategy: FULL 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 309.99/291.49 Renamed function symbols to avoid clashes with predefined symbol. 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (2) 309.99/291.49 Obligation: 309.99/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 309.99/291.49 309.99/291.49 309.99/291.49 The TRS R consists of the following rules: 309.99/291.49 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 S is empty. 309.99/291.49 Rewrite Strategy: FULL 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 309.99/291.49 Infered types. 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (4) 309.99/291.49 Obligation: 309.99/291.49 TRS: 309.99/291.49 Rules: 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 Types: 309.99/291.49 min :: 0':s -> 0':s -> 0':s 309.99/291.49 0' :: 0':s 309.99/291.49 s :: 0':s -> 0':s 309.99/291.49 max :: 0':s -> 0':s -> 0':s 309.99/291.49 - :: 0':s -> 0':s -> 0':s 309.99/291.49 gcd :: 0':s -> 0':s -> 0':s 309.99/291.49 hole_0':s1_0 :: 0':s 309.99/291.49 gen_0':s2_0 :: Nat -> 0':s 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (5) OrderProof (LOWER BOUND(ID)) 309.99/291.49 Heuristically decided to analyse the following defined symbols: 309.99/291.49 min, max, -, gcd 309.99/291.49 309.99/291.49 They will be analysed ascendingly in the following order: 309.99/291.49 min < gcd 309.99/291.49 max < gcd 309.99/291.49 - < gcd 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (6) 309.99/291.49 Obligation: 309.99/291.49 TRS: 309.99/291.49 Rules: 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 Types: 309.99/291.49 min :: 0':s -> 0':s -> 0':s 309.99/291.49 0' :: 0':s 309.99/291.49 s :: 0':s -> 0':s 309.99/291.49 max :: 0':s -> 0':s -> 0':s 309.99/291.49 - :: 0':s -> 0':s -> 0':s 309.99/291.49 gcd :: 0':s -> 0':s -> 0':s 309.99/291.49 hole_0':s1_0 :: 0':s 309.99/291.49 gen_0':s2_0 :: Nat -> 0':s 309.99/291.49 309.99/291.49 309.99/291.49 Generator Equations: 309.99/291.49 gen_0':s2_0(0) <=> 0' 309.99/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 309.99/291.49 309.99/291.49 309.99/291.49 The following defined symbols remain to be analysed: 309.99/291.49 min, max, -, gcd 309.99/291.49 309.99/291.49 They will be analysed ascendingly in the following order: 309.99/291.49 min < gcd 309.99/291.49 max < gcd 309.99/291.49 - < gcd 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 309.99/291.49 Proved the following rewrite lemma: 309.99/291.49 min(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) -> gen_0':s2_0(n4_0), rt in Omega(1 + n4_0) 309.99/291.49 309.99/291.49 Induction Base: 309.99/291.49 min(gen_0':s2_0(0), gen_0':s2_0(0)) ->_R^Omega(1) 309.99/291.49 0' 309.99/291.49 309.99/291.49 Induction Step: 309.99/291.49 min(gen_0':s2_0(+(n4_0, 1)), gen_0':s2_0(+(n4_0, 1))) ->_R^Omega(1) 309.99/291.49 s(min(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0))) ->_IH 309.99/291.49 s(gen_0':s2_0(c5_0)) 309.99/291.49 309.99/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (8) 309.99/291.49 Complex Obligation (BEST) 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (9) 309.99/291.49 Obligation: 309.99/291.49 Proved the lower bound n^1 for the following obligation: 309.99/291.49 309.99/291.49 TRS: 309.99/291.49 Rules: 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 Types: 309.99/291.49 min :: 0':s -> 0':s -> 0':s 309.99/291.49 0' :: 0':s 309.99/291.49 s :: 0':s -> 0':s 309.99/291.49 max :: 0':s -> 0':s -> 0':s 309.99/291.49 - :: 0':s -> 0':s -> 0':s 309.99/291.49 gcd :: 0':s -> 0':s -> 0':s 309.99/291.49 hole_0':s1_0 :: 0':s 309.99/291.49 gen_0':s2_0 :: Nat -> 0':s 309.99/291.49 309.99/291.49 309.99/291.49 Generator Equations: 309.99/291.49 gen_0':s2_0(0) <=> 0' 309.99/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 309.99/291.49 309.99/291.49 309.99/291.49 The following defined symbols remain to be analysed: 309.99/291.49 min, max, -, gcd 309.99/291.49 309.99/291.49 They will be analysed ascendingly in the following order: 309.99/291.49 min < gcd 309.99/291.49 max < gcd 309.99/291.49 - < gcd 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (10) LowerBoundPropagationProof (FINISHED) 309.99/291.49 Propagated lower bound. 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (11) 309.99/291.49 BOUNDS(n^1, INF) 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (12) 309.99/291.49 Obligation: 309.99/291.49 TRS: 309.99/291.49 Rules: 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 Types: 309.99/291.49 min :: 0':s -> 0':s -> 0':s 309.99/291.49 0' :: 0':s 309.99/291.49 s :: 0':s -> 0':s 309.99/291.49 max :: 0':s -> 0':s -> 0':s 309.99/291.49 - :: 0':s -> 0':s -> 0':s 309.99/291.49 gcd :: 0':s -> 0':s -> 0':s 309.99/291.49 hole_0':s1_0 :: 0':s 309.99/291.49 gen_0':s2_0 :: Nat -> 0':s 309.99/291.49 309.99/291.49 309.99/291.49 Lemmas: 309.99/291.49 min(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) -> gen_0':s2_0(n4_0), rt in Omega(1 + n4_0) 309.99/291.49 309.99/291.49 309.99/291.49 Generator Equations: 309.99/291.49 gen_0':s2_0(0) <=> 0' 309.99/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 309.99/291.49 309.99/291.49 309.99/291.49 The following defined symbols remain to be analysed: 309.99/291.49 max, -, gcd 309.99/291.49 309.99/291.49 They will be analysed ascendingly in the following order: 309.99/291.49 max < gcd 309.99/291.49 - < gcd 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (13) RewriteLemmaProof (LOWER BOUND(ID)) 309.99/291.49 Proved the following rewrite lemma: 309.99/291.49 max(gen_0':s2_0(n300_0), gen_0':s2_0(n300_0)) -> gen_0':s2_0(n300_0), rt in Omega(1 + n300_0) 309.99/291.49 309.99/291.49 Induction Base: 309.99/291.49 max(gen_0':s2_0(0), gen_0':s2_0(0)) ->_R^Omega(1) 309.99/291.49 gen_0':s2_0(0) 309.99/291.49 309.99/291.49 Induction Step: 309.99/291.49 max(gen_0':s2_0(+(n300_0, 1)), gen_0':s2_0(+(n300_0, 1))) ->_R^Omega(1) 309.99/291.49 s(max(gen_0':s2_0(n300_0), gen_0':s2_0(n300_0))) ->_IH 309.99/291.49 s(gen_0':s2_0(c301_0)) 309.99/291.49 309.99/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (14) 309.99/291.49 Obligation: 309.99/291.49 TRS: 309.99/291.49 Rules: 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 Types: 309.99/291.49 min :: 0':s -> 0':s -> 0':s 309.99/291.49 0' :: 0':s 309.99/291.49 s :: 0':s -> 0':s 309.99/291.49 max :: 0':s -> 0':s -> 0':s 309.99/291.49 - :: 0':s -> 0':s -> 0':s 309.99/291.49 gcd :: 0':s -> 0':s -> 0':s 309.99/291.49 hole_0':s1_0 :: 0':s 309.99/291.49 gen_0':s2_0 :: Nat -> 0':s 309.99/291.49 309.99/291.49 309.99/291.49 Lemmas: 309.99/291.49 min(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) -> gen_0':s2_0(n4_0), rt in Omega(1 + n4_0) 309.99/291.49 max(gen_0':s2_0(n300_0), gen_0':s2_0(n300_0)) -> gen_0':s2_0(n300_0), rt in Omega(1 + n300_0) 309.99/291.49 309.99/291.49 309.99/291.49 Generator Equations: 309.99/291.49 gen_0':s2_0(0) <=> 0' 309.99/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 309.99/291.49 309.99/291.49 309.99/291.49 The following defined symbols remain to be analysed: 309.99/291.49 -, gcd 309.99/291.49 309.99/291.49 They will be analysed ascendingly in the following order: 309.99/291.49 - < gcd 309.99/291.49 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (15) RewriteLemmaProof (LOWER BOUND(ID)) 309.99/291.49 Proved the following rewrite lemma: 309.99/291.49 -(gen_0':s2_0(n676_0), gen_0':s2_0(n676_0)) -> gen_0':s2_0(0), rt in Omega(1 + n676_0) 309.99/291.49 309.99/291.49 Induction Base: 309.99/291.49 -(gen_0':s2_0(0), gen_0':s2_0(0)) ->_R^Omega(1) 309.99/291.49 gen_0':s2_0(0) 309.99/291.49 309.99/291.49 Induction Step: 309.99/291.49 -(gen_0':s2_0(+(n676_0, 1)), gen_0':s2_0(+(n676_0, 1))) ->_R^Omega(1) 309.99/291.49 -(gen_0':s2_0(n676_0), gen_0':s2_0(n676_0)) ->_IH 309.99/291.49 gen_0':s2_0(0) 309.99/291.49 309.99/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 309.99/291.49 ---------------------------------------- 309.99/291.49 309.99/291.49 (16) 309.99/291.49 Obligation: 309.99/291.49 TRS: 309.99/291.49 Rules: 309.99/291.49 min(x, 0') -> 0' 309.99/291.49 min(0', y) -> 0' 309.99/291.49 min(s(x), s(y)) -> s(min(x, y)) 309.99/291.49 max(x, 0') -> x 309.99/291.49 max(0', y) -> y 309.99/291.49 max(s(x), s(y)) -> s(max(x, y)) 309.99/291.49 -(x, 0') -> x 309.99/291.49 -(s(x), s(y)) -> -(x, y) 309.99/291.49 gcd(s(x), 0') -> s(x) 309.99/291.49 gcd(0', s(x)) -> s(x) 309.99/291.49 gcd(s(x), s(y)) -> gcd(-(max(x, y), min(x, y)), s(min(x, y))) 309.99/291.49 309.99/291.49 Types: 309.99/291.49 min :: 0':s -> 0':s -> 0':s 309.99/291.49 0' :: 0':s 309.99/291.49 s :: 0':s -> 0':s 309.99/291.49 max :: 0':s -> 0':s -> 0':s 309.99/291.49 - :: 0':s -> 0':s -> 0':s 309.99/291.49 gcd :: 0':s -> 0':s -> 0':s 309.99/291.49 hole_0':s1_0 :: 0':s 309.99/291.49 gen_0':s2_0 :: Nat -> 0':s 309.99/291.49 309.99/291.49 309.99/291.49 Lemmas: 309.99/291.49 min(gen_0':s2_0(n4_0), gen_0':s2_0(n4_0)) -> gen_0':s2_0(n4_0), rt in Omega(1 + n4_0) 309.99/291.49 max(gen_0':s2_0(n300_0), gen_0':s2_0(n300_0)) -> gen_0':s2_0(n300_0), rt in Omega(1 + n300_0) 309.99/291.49 -(gen_0':s2_0(n676_0), gen_0':s2_0(n676_0)) -> gen_0':s2_0(0), rt in Omega(1 + n676_0) 309.99/291.49 309.99/291.49 309.99/291.49 Generator Equations: 309.99/291.49 gen_0':s2_0(0) <=> 0' 309.99/291.49 gen_0':s2_0(+(x, 1)) <=> s(gen_0':s2_0(x)) 309.99/291.49 309.99/291.49 309.99/291.49 The following defined symbols remain to be analysed: 309.99/291.49 gcd 309.99/291.52 EOF