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