302.73/291.48 WORST_CASE(Omega(n^1), ?) 302.73/291.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 302.73/291.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 302.73/291.49 302.73/291.49 302.73/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 302.73/291.49 302.73/291.49 (0) CpxTRS 302.73/291.49 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 302.73/291.49 (2) CpxTRS 302.73/291.49 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 302.73/291.49 (4) typed CpxTrs 302.73/291.49 (5) OrderProof [LOWER BOUND(ID), 0 ms] 302.73/291.49 (6) typed CpxTrs 302.73/291.49 (7) RewriteLemmaProof [LOWER BOUND(ID), 280 ms] 302.73/291.49 (8) BEST 302.73/291.49 (9) proven lower bound 302.73/291.49 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 302.73/291.49 (11) BOUNDS(n^1, INF) 302.73/291.49 (12) typed CpxTrs 302.73/291.49 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (0) 302.73/291.49 Obligation: 302.73/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 302.73/291.49 302.73/291.49 302.73/291.49 The TRS R consists of the following rules: 302.73/291.49 302.73/291.49 cond1(true, x, y) -> cond2(gr(x, y), x, y) 302.73/291.49 cond2(true, x, y) -> cond3(gr(x, 0), x, y) 302.73/291.49 cond2(false, x, y) -> cond4(gr(y, 0), x, y) 302.73/291.49 cond3(true, x, y) -> cond3(gr(x, 0), p(x), y) 302.73/291.49 cond3(false, x, y) -> cond1(and(gr(x, 0), gr(y, 0)), x, y) 302.73/291.49 cond4(true, x, y) -> cond4(gr(y, 0), x, p(y)) 302.73/291.49 cond4(false, x, y) -> cond1(and(gr(x, 0), gr(y, 0)), x, y) 302.73/291.49 gr(0, x) -> false 302.73/291.49 gr(s(x), 0) -> true 302.73/291.49 gr(s(x), s(y)) -> gr(x, y) 302.73/291.49 and(true, true) -> true 302.73/291.49 and(false, x) -> false 302.73/291.49 and(x, false) -> false 302.73/291.49 p(0) -> 0 302.73/291.49 p(s(x)) -> x 302.73/291.49 302.73/291.49 S is empty. 302.73/291.49 Rewrite Strategy: FULL 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 302.73/291.49 Renamed function symbols to avoid clashes with predefined symbol. 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (2) 302.73/291.49 Obligation: 302.73/291.49 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 302.73/291.49 302.73/291.49 302.73/291.49 The TRS R consists of the following rules: 302.73/291.49 302.73/291.49 cond1(true, x, y) -> cond2(gr(x, y), x, y) 302.73/291.49 cond2(true, x, y) -> cond3(gr(x, 0'), x, y) 302.73/291.49 cond2(false, x, y) -> cond4(gr(y, 0'), x, y) 302.73/291.49 cond3(true, x, y) -> cond3(gr(x, 0'), p(x), y) 302.73/291.49 cond3(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 cond4(true, x, y) -> cond4(gr(y, 0'), x, p(y)) 302.73/291.49 cond4(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 gr(0', x) -> false 302.73/291.49 gr(s(x), 0') -> true 302.73/291.49 gr(s(x), s(y)) -> gr(x, y) 302.73/291.49 and(true, true) -> true 302.73/291.49 and(false, x) -> false 302.73/291.49 and(x, false) -> false 302.73/291.49 p(0') -> 0' 302.73/291.49 p(s(x)) -> x 302.73/291.49 302.73/291.49 S is empty. 302.73/291.49 Rewrite Strategy: FULL 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 302.73/291.49 Infered types. 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (4) 302.73/291.49 Obligation: 302.73/291.49 TRS: 302.73/291.49 Rules: 302.73/291.49 cond1(true, x, y) -> cond2(gr(x, y), x, y) 302.73/291.49 cond2(true, x, y) -> cond3(gr(x, 0'), x, y) 302.73/291.49 cond2(false, x, y) -> cond4(gr(y, 0'), x, y) 302.73/291.49 cond3(true, x, y) -> cond3(gr(x, 0'), p(x), y) 302.73/291.49 cond3(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 cond4(true, x, y) -> cond4(gr(y, 0'), x, p(y)) 302.73/291.49 cond4(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 gr(0', x) -> false 302.73/291.49 gr(s(x), 0') -> true 302.73/291.49 gr(s(x), s(y)) -> gr(x, y) 302.73/291.49 and(true, true) -> true 302.73/291.49 and(false, x) -> false 302.73/291.49 and(x, false) -> false 302.73/291.49 p(0') -> 0' 302.73/291.49 p(s(x)) -> x 302.73/291.49 302.73/291.49 Types: 302.73/291.49 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 true :: true:false 302.73/291.49 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 gr :: 0':s -> 0':s -> true:false 302.73/291.49 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 0' :: 0':s 302.73/291.49 false :: true:false 302.73/291.49 cond4 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 p :: 0':s -> 0':s 302.73/291.49 and :: true:false -> true:false -> true:false 302.73/291.49 s :: 0':s -> 0':s 302.73/291.49 hole_cond1:cond2:cond3:cond41_0 :: cond1:cond2:cond3:cond4 302.73/291.49 hole_true:false2_0 :: true:false 302.73/291.49 hole_0':s3_0 :: 0':s 302.73/291.49 gen_0':s4_0 :: Nat -> 0':s 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (5) OrderProof (LOWER BOUND(ID)) 302.73/291.49 Heuristically decided to analyse the following defined symbols: 302.73/291.49 cond1, cond2, gr, cond3, cond4 302.73/291.49 302.73/291.49 They will be analysed ascendingly in the following order: 302.73/291.49 cond1 = cond2 302.73/291.49 gr < cond1 302.73/291.49 cond1 = cond3 302.73/291.49 cond1 = cond4 302.73/291.49 gr < cond2 302.73/291.49 cond2 = cond3 302.73/291.49 cond2 = cond4 302.73/291.49 gr < cond3 302.73/291.49 gr < cond4 302.73/291.49 cond3 = cond4 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (6) 302.73/291.49 Obligation: 302.73/291.49 TRS: 302.73/291.49 Rules: 302.73/291.49 cond1(true, x, y) -> cond2(gr(x, y), x, y) 302.73/291.49 cond2(true, x, y) -> cond3(gr(x, 0'), x, y) 302.73/291.49 cond2(false, x, y) -> cond4(gr(y, 0'), x, y) 302.73/291.49 cond3(true, x, y) -> cond3(gr(x, 0'), p(x), y) 302.73/291.49 cond3(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 cond4(true, x, y) -> cond4(gr(y, 0'), x, p(y)) 302.73/291.49 cond4(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 gr(0', x) -> false 302.73/291.49 gr(s(x), 0') -> true 302.73/291.49 gr(s(x), s(y)) -> gr(x, y) 302.73/291.49 and(true, true) -> true 302.73/291.49 and(false, x) -> false 302.73/291.49 and(x, false) -> false 302.73/291.49 p(0') -> 0' 302.73/291.49 p(s(x)) -> x 302.73/291.49 302.73/291.49 Types: 302.73/291.49 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 true :: true:false 302.73/291.49 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 gr :: 0':s -> 0':s -> true:false 302.73/291.49 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 0' :: 0':s 302.73/291.49 false :: true:false 302.73/291.49 cond4 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 p :: 0':s -> 0':s 302.73/291.49 and :: true:false -> true:false -> true:false 302.73/291.49 s :: 0':s -> 0':s 302.73/291.49 hole_cond1:cond2:cond3:cond41_0 :: cond1:cond2:cond3:cond4 302.73/291.49 hole_true:false2_0 :: true:false 302.73/291.49 hole_0':s3_0 :: 0':s 302.73/291.49 gen_0':s4_0 :: Nat -> 0':s 302.73/291.49 302.73/291.49 302.73/291.49 Generator Equations: 302.73/291.49 gen_0':s4_0(0) <=> 0' 302.73/291.49 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 302.73/291.49 302.73/291.49 302.73/291.49 The following defined symbols remain to be analysed: 302.73/291.49 gr, cond1, cond2, cond3, cond4 302.73/291.49 302.73/291.49 They will be analysed ascendingly in the following order: 302.73/291.49 cond1 = cond2 302.73/291.49 gr < cond1 302.73/291.49 cond1 = cond3 302.73/291.49 cond1 = cond4 302.73/291.49 gr < cond2 302.73/291.49 cond2 = cond3 302.73/291.49 cond2 = cond4 302.73/291.49 gr < cond3 302.73/291.49 gr < cond4 302.73/291.49 cond3 = cond4 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (7) RewriteLemmaProof (LOWER BOUND(ID)) 302.73/291.49 Proved the following rewrite lemma: 302.73/291.49 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 302.73/291.49 302.73/291.49 Induction Base: 302.73/291.49 gr(gen_0':s4_0(0), gen_0':s4_0(0)) ->_R^Omega(1) 302.73/291.49 false 302.73/291.49 302.73/291.49 Induction Step: 302.73/291.49 gr(gen_0':s4_0(+(n6_0, 1)), gen_0':s4_0(+(n6_0, 1))) ->_R^Omega(1) 302.73/291.49 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) ->_IH 302.73/291.49 false 302.73/291.49 302.73/291.49 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (8) 302.73/291.49 Complex Obligation (BEST) 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (9) 302.73/291.49 Obligation: 302.73/291.49 Proved the lower bound n^1 for the following obligation: 302.73/291.49 302.73/291.49 TRS: 302.73/291.49 Rules: 302.73/291.49 cond1(true, x, y) -> cond2(gr(x, y), x, y) 302.73/291.49 cond2(true, x, y) -> cond3(gr(x, 0'), x, y) 302.73/291.49 cond2(false, x, y) -> cond4(gr(y, 0'), x, y) 302.73/291.49 cond3(true, x, y) -> cond3(gr(x, 0'), p(x), y) 302.73/291.49 cond3(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 cond4(true, x, y) -> cond4(gr(y, 0'), x, p(y)) 302.73/291.49 cond4(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 gr(0', x) -> false 302.73/291.49 gr(s(x), 0') -> true 302.73/291.49 gr(s(x), s(y)) -> gr(x, y) 302.73/291.49 and(true, true) -> true 302.73/291.49 and(false, x) -> false 302.73/291.49 and(x, false) -> false 302.73/291.49 p(0') -> 0' 302.73/291.49 p(s(x)) -> x 302.73/291.49 302.73/291.49 Types: 302.73/291.49 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 true :: true:false 302.73/291.49 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 gr :: 0':s -> 0':s -> true:false 302.73/291.49 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 0' :: 0':s 302.73/291.49 false :: true:false 302.73/291.49 cond4 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 p :: 0':s -> 0':s 302.73/291.49 and :: true:false -> true:false -> true:false 302.73/291.49 s :: 0':s -> 0':s 302.73/291.49 hole_cond1:cond2:cond3:cond41_0 :: cond1:cond2:cond3:cond4 302.73/291.49 hole_true:false2_0 :: true:false 302.73/291.49 hole_0':s3_0 :: 0':s 302.73/291.49 gen_0':s4_0 :: Nat -> 0':s 302.73/291.49 302.73/291.49 302.73/291.49 Generator Equations: 302.73/291.49 gen_0':s4_0(0) <=> 0' 302.73/291.49 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 302.73/291.49 302.73/291.49 302.73/291.49 The following defined symbols remain to be analysed: 302.73/291.49 gr, cond1, cond2, cond3, cond4 302.73/291.49 302.73/291.49 They will be analysed ascendingly in the following order: 302.73/291.49 cond1 = cond2 302.73/291.49 gr < cond1 302.73/291.49 cond1 = cond3 302.73/291.49 cond1 = cond4 302.73/291.49 gr < cond2 302.73/291.49 cond2 = cond3 302.73/291.49 cond2 = cond4 302.73/291.49 gr < cond3 302.73/291.49 gr < cond4 302.73/291.49 cond3 = cond4 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (10) LowerBoundPropagationProof (FINISHED) 302.73/291.49 Propagated lower bound. 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (11) 302.73/291.49 BOUNDS(n^1, INF) 302.73/291.49 302.73/291.49 ---------------------------------------- 302.73/291.49 302.73/291.49 (12) 302.73/291.49 Obligation: 302.73/291.49 TRS: 302.73/291.49 Rules: 302.73/291.49 cond1(true, x, y) -> cond2(gr(x, y), x, y) 302.73/291.49 cond2(true, x, y) -> cond3(gr(x, 0'), x, y) 302.73/291.49 cond2(false, x, y) -> cond4(gr(y, 0'), x, y) 302.73/291.49 cond3(true, x, y) -> cond3(gr(x, 0'), p(x), y) 302.73/291.49 cond3(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 cond4(true, x, y) -> cond4(gr(y, 0'), x, p(y)) 302.73/291.49 cond4(false, x, y) -> cond1(and(gr(x, 0'), gr(y, 0')), x, y) 302.73/291.49 gr(0', x) -> false 302.73/291.49 gr(s(x), 0') -> true 302.73/291.49 gr(s(x), s(y)) -> gr(x, y) 302.73/291.49 and(true, true) -> true 302.73/291.49 and(false, x) -> false 302.73/291.49 and(x, false) -> false 302.73/291.49 p(0') -> 0' 302.73/291.49 p(s(x)) -> x 302.73/291.49 302.73/291.49 Types: 302.73/291.49 cond1 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 true :: true:false 302.73/291.49 cond2 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 gr :: 0':s -> 0':s -> true:false 302.73/291.49 cond3 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 0' :: 0':s 302.73/291.49 false :: true:false 302.73/291.49 cond4 :: true:false -> 0':s -> 0':s -> cond1:cond2:cond3:cond4 302.73/291.49 p :: 0':s -> 0':s 302.73/291.49 and :: true:false -> true:false -> true:false 302.73/291.49 s :: 0':s -> 0':s 302.73/291.49 hole_cond1:cond2:cond3:cond41_0 :: cond1:cond2:cond3:cond4 302.73/291.49 hole_true:false2_0 :: true:false 302.73/291.49 hole_0':s3_0 :: 0':s 302.73/291.49 gen_0':s4_0 :: Nat -> 0':s 302.73/291.49 302.73/291.49 302.73/291.49 Lemmas: 302.73/291.49 gr(gen_0':s4_0(n6_0), gen_0':s4_0(n6_0)) -> false, rt in Omega(1 + n6_0) 302.73/291.49 302.73/291.49 302.73/291.49 Generator Equations: 302.73/291.49 gen_0':s4_0(0) <=> 0' 302.73/291.49 gen_0':s4_0(+(x, 1)) <=> s(gen_0':s4_0(x)) 302.73/291.49 302.73/291.49 302.73/291.49 The following defined symbols remain to be analysed: 302.73/291.49 cond2, cond1, cond3, cond4 302.73/291.49 302.73/291.49 They will be analysed ascendingly in the following order: 302.73/291.49 cond1 = cond2 302.73/291.49 cond1 = cond3 302.73/291.49 cond1 = cond4 302.73/291.49 cond2 = cond3 302.73/291.49 cond2 = cond4 302.73/291.49 cond3 = cond4 302.85/291.56 EOF