/export/starexec/sandbox/solver/bin/starexec_run_complexity /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) DependencyGraphProof [UPPER BOUND(ID), 0 ms] (2) CpxTRS (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (4) CpxTRS (5) CpxTrsMatchBoundsTAProof [FINISHED, 291 ms] (6) BOUNDS(1, n^1) (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTRS (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) typed CpxTrs (11) OrderProof [LOWER BOUND(ID), 0 ms] (12) typed CpxTrs (13) RewriteLemmaProof [LOWER BOUND(ID), 450 ms] (14) BEST (15) proven lower bound (16) LowerBoundPropagationProof [FINISHED, 0 ms] (17) BOUNDS(n^1, INF) (18) typed CpxTrs (19) RewriteLemmaProof [LOWER BOUND(ID), 53 ms] (20) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: minus(n__0, Y) -> 0 minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0, n__s(Y)) -> 0 div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) DependencyGraphProof (UPPER BOUND(ID)) The following rules are not reachable from basic terms in the dependency graph and can be removed: div(0, n__s(Y)) -> 0 div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: minus(n__0, Y) -> 0 minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) RelTrsToTrsProof (UPPER BOUND(ID)) transformed relative TRS to TRS ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: minus(n__0, Y) -> 0 minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0 -> n__0 s(X) -> n__s(X) activate(n__0) -> 0 activate(n__s(X)) -> s(X) activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (5) CpxTrsMatchBoundsTAProof (FINISHED) A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 4. The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: final states : [1, 2, 3, 4, 5, 6] transitions: n__00() -> 0 n__s0(0) -> 0 true0() -> 0 false0() -> 0 minus0(0, 0) -> 1 geq0(0, 0) -> 2 if0(0, 0, 0) -> 3 00() -> 4 s0(0) -> 5 activate0(0) -> 6 01() -> 1 activate1(0) -> 7 activate1(0) -> 8 minus1(7, 8) -> 1 true1() -> 2 false1() -> 2 activate1(0) -> 9 activate1(0) -> 10 geq1(9, 10) -> 2 activate1(0) -> 3 n__01() -> 4 n__s1(0) -> 5 01() -> 6 s1(0) -> 6 n__02() -> 1 n__02() -> 6 n__s2(0) -> 6 01() -> 3 01() -> 7 01() -> 8 01() -> 9 01() -> 10 s1(0) -> 3 s1(0) -> 7 s1(0) -> 8 s1(0) -> 9 s1(0) -> 10 n__02() -> 3 n__02() -> 7 n__02() -> 8 n__02() -> 9 n__02() -> 10 n__s2(0) -> 3 n__s2(0) -> 7 n__s2(0) -> 8 n__s2(0) -> 9 n__s2(0) -> 10 02() -> 1 activate2(0) -> 11 activate2(0) -> 12 minus2(11, 12) -> 1 true2() -> 2 false2() -> 2 activate2(0) -> 13 activate2(0) -> 14 geq2(13, 14) -> 2 n__03() -> 1 01() -> 11 01() -> 12 01() -> 13 01() -> 14 s1(0) -> 11 s1(0) -> 12 s1(0) -> 13 s1(0) -> 14 n__02() -> 11 n__02() -> 12 n__02() -> 13 n__02() -> 14 n__s2(0) -> 11 n__s2(0) -> 12 n__s2(0) -> 13 n__s2(0) -> 14 03() -> 1 activate3(0) -> 15 activate3(0) -> 16 minus3(15, 16) -> 1 true3() -> 2 false3() -> 2 activate3(0) -> 17 activate3(0) -> 18 geq3(17, 18) -> 2 n__04() -> 1 01() -> 15 01() -> 16 01() -> 17 01() -> 18 s1(0) -> 15 s1(0) -> 16 s1(0) -> 17 s1(0) -> 18 n__02() -> 15 n__02() -> 16 n__02() -> 17 n__02() -> 18 n__s2(0) -> 15 n__s2(0) -> 16 n__s2(0) -> 17 n__s2(0) -> 18 0 -> 6 0 -> 3 0 -> 7 0 -> 8 0 -> 9 0 -> 10 0 -> 11 0 -> 12 0 -> 13 0 -> 14 0 -> 15 0 -> 16 0 -> 17 0 -> 18 ---------------------------------------- (6) BOUNDS(1, n^1) ---------------------------------------- (7) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (8) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: minus(n__0, Y) -> 0' minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0', n__s(Y)) -> 0' div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0' -> n__0 s(X) -> n__s(X) activate(n__0) -> 0' activate(n__s(X)) -> s(X) activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: TRS: Rules: minus(n__0, Y) -> 0' minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0', n__s(Y)) -> 0' div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0' -> n__0 s(X) -> n__s(X) activate(n__0) -> 0' activate(n__s(X)) -> s(X) activate(X) -> X Types: minus :: n__0:n__s -> n__0:n__s -> n__0:n__s n__0 :: n__0:n__s 0' :: n__0:n__s n__s :: n__0:n__s -> n__0:n__s activate :: n__0:n__s -> n__0:n__s geq :: n__0:n__s -> n__0:n__s -> true:false true :: true:false false :: true:false div :: n__0:n__s -> n__0:n__s -> n__0:n__s s :: n__0:n__s -> n__0:n__s if :: true:false -> n__0:n__s -> n__0:n__s -> n__0:n__s hole_n__0:n__s1_1 :: n__0:n__s hole_true:false2_1 :: true:false gen_n__0:n__s3_1 :: Nat -> n__0:n__s ---------------------------------------- (11) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: minus, geq, div They will be analysed ascendingly in the following order: minus < div geq < div ---------------------------------------- (12) Obligation: TRS: Rules: minus(n__0, Y) -> 0' minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0', n__s(Y)) -> 0' div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0' -> n__0 s(X) -> n__s(X) activate(n__0) -> 0' activate(n__s(X)) -> s(X) activate(X) -> X Types: minus :: n__0:n__s -> n__0:n__s -> n__0:n__s n__0 :: n__0:n__s 0' :: n__0:n__s n__s :: n__0:n__s -> n__0:n__s activate :: n__0:n__s -> n__0:n__s geq :: n__0:n__s -> n__0:n__s -> true:false true :: true:false false :: true:false div :: n__0:n__s -> n__0:n__s -> n__0:n__s s :: n__0:n__s -> n__0:n__s if :: true:false -> n__0:n__s -> n__0:n__s -> n__0:n__s hole_n__0:n__s1_1 :: n__0:n__s hole_true:false2_1 :: true:false gen_n__0:n__s3_1 :: Nat -> n__0:n__s Generator Equations: gen_n__0:n__s3_1(0) <=> n__0 gen_n__0:n__s3_1(+(x, 1)) <=> n__s(gen_n__0:n__s3_1(x)) The following defined symbols remain to be analysed: minus, geq, div They will be analysed ascendingly in the following order: minus < div geq < div ---------------------------------------- (13) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: minus(gen_n__0:n__s3_1(+(2, n5_1)), gen_n__0:n__s3_1(+(1, n5_1))) -> minus(gen_n__0:n__s3_1(1), gen_n__0:n__s3_1(0)), rt in Omega(1 + n5_1) Induction Base: minus(gen_n__0:n__s3_1(+(2, 0)), gen_n__0:n__s3_1(+(1, 0))) ->_R^Omega(1) minus(activate(gen_n__0:n__s3_1(1)), activate(gen_n__0:n__s3_1(0))) ->_R^Omega(1) minus(gen_n__0:n__s3_1(1), activate(gen_n__0:n__s3_1(0))) ->_R^Omega(1) minus(gen_n__0:n__s3_1(1), gen_n__0:n__s3_1(0)) Induction Step: minus(gen_n__0:n__s3_1(+(2, +(n5_1, 1))), gen_n__0:n__s3_1(+(1, +(n5_1, 1)))) ->_R^Omega(1) minus(activate(gen_n__0:n__s3_1(+(2, n5_1))), activate(gen_n__0:n__s3_1(+(1, n5_1)))) ->_R^Omega(1) minus(gen_n__0:n__s3_1(+(2, n5_1)), activate(gen_n__0:n__s3_1(+(1, n5_1)))) ->_R^Omega(1) minus(gen_n__0:n__s3_1(+(2, n5_1)), gen_n__0:n__s3_1(+(1, n5_1))) ->_IH minus(gen_n__0:n__s3_1(1), gen_n__0:n__s3_1(0)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (14) Complex Obligation (BEST) ---------------------------------------- (15) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: minus(n__0, Y) -> 0' minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0', n__s(Y)) -> 0' div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0' -> n__0 s(X) -> n__s(X) activate(n__0) -> 0' activate(n__s(X)) -> s(X) activate(X) -> X Types: minus :: n__0:n__s -> n__0:n__s -> n__0:n__s n__0 :: n__0:n__s 0' :: n__0:n__s n__s :: n__0:n__s -> n__0:n__s activate :: n__0:n__s -> n__0:n__s geq :: n__0:n__s -> n__0:n__s -> true:false true :: true:false false :: true:false div :: n__0:n__s -> n__0:n__s -> n__0:n__s s :: n__0:n__s -> n__0:n__s if :: true:false -> n__0:n__s -> n__0:n__s -> n__0:n__s hole_n__0:n__s1_1 :: n__0:n__s hole_true:false2_1 :: true:false gen_n__0:n__s3_1 :: Nat -> n__0:n__s Generator Equations: gen_n__0:n__s3_1(0) <=> n__0 gen_n__0:n__s3_1(+(x, 1)) <=> n__s(gen_n__0:n__s3_1(x)) The following defined symbols remain to be analysed: minus, geq, div They will be analysed ascendingly in the following order: minus < div geq < div ---------------------------------------- (16) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (17) BOUNDS(n^1, INF) ---------------------------------------- (18) Obligation: TRS: Rules: minus(n__0, Y) -> 0' minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0', n__s(Y)) -> 0' div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0' -> n__0 s(X) -> n__s(X) activate(n__0) -> 0' activate(n__s(X)) -> s(X) activate(X) -> X Types: minus :: n__0:n__s -> n__0:n__s -> n__0:n__s n__0 :: n__0:n__s 0' :: n__0:n__s n__s :: n__0:n__s -> n__0:n__s activate :: n__0:n__s -> n__0:n__s geq :: n__0:n__s -> n__0:n__s -> true:false true :: true:false false :: true:false div :: n__0:n__s -> n__0:n__s -> n__0:n__s s :: n__0:n__s -> n__0:n__s if :: true:false -> n__0:n__s -> n__0:n__s -> n__0:n__s hole_n__0:n__s1_1 :: n__0:n__s hole_true:false2_1 :: true:false gen_n__0:n__s3_1 :: Nat -> n__0:n__s Lemmas: minus(gen_n__0:n__s3_1(+(2, n5_1)), gen_n__0:n__s3_1(+(1, n5_1))) -> minus(gen_n__0:n__s3_1(1), gen_n__0:n__s3_1(0)), rt in Omega(1 + n5_1) Generator Equations: gen_n__0:n__s3_1(0) <=> n__0 gen_n__0:n__s3_1(+(x, 1)) <=> n__s(gen_n__0:n__s3_1(x)) The following defined symbols remain to be analysed: geq, div They will be analysed ascendingly in the following order: geq < div ---------------------------------------- (19) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: geq(gen_n__0:n__s3_1(n2498_1), gen_n__0:n__s3_1(+(1, n2498_1))) -> false, rt in Omega(1 + n2498_1) Induction Base: geq(gen_n__0:n__s3_1(0), gen_n__0:n__s3_1(+(1, 0))) ->_R^Omega(1) false Induction Step: geq(gen_n__0:n__s3_1(+(n2498_1, 1)), gen_n__0:n__s3_1(+(1, +(n2498_1, 1)))) ->_R^Omega(1) geq(activate(gen_n__0:n__s3_1(n2498_1)), activate(gen_n__0:n__s3_1(+(1, n2498_1)))) ->_R^Omega(1) geq(gen_n__0:n__s3_1(n2498_1), activate(gen_n__0:n__s3_1(+(1, n2498_1)))) ->_R^Omega(1) geq(gen_n__0:n__s3_1(n2498_1), gen_n__0:n__s3_1(+(1, n2498_1))) ->_IH false We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (20) Obligation: TRS: Rules: minus(n__0, Y) -> 0' minus(n__s(X), n__s(Y)) -> minus(activate(X), activate(Y)) geq(X, n__0) -> true geq(n__0, n__s(Y)) -> false geq(n__s(X), n__s(Y)) -> geq(activate(X), activate(Y)) div(0', n__s(Y)) -> 0' div(s(X), n__s(Y)) -> if(geq(X, activate(Y)), n__s(div(minus(X, activate(Y)), n__s(activate(Y)))), n__0) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) 0' -> n__0 s(X) -> n__s(X) activate(n__0) -> 0' activate(n__s(X)) -> s(X) activate(X) -> X Types: minus :: n__0:n__s -> n__0:n__s -> n__0:n__s n__0 :: n__0:n__s 0' :: n__0:n__s n__s :: n__0:n__s -> n__0:n__s activate :: n__0:n__s -> n__0:n__s geq :: n__0:n__s -> n__0:n__s -> true:false true :: true:false false :: true:false div :: n__0:n__s -> n__0:n__s -> n__0:n__s s :: n__0:n__s -> n__0:n__s if :: true:false -> n__0:n__s -> n__0:n__s -> n__0:n__s hole_n__0:n__s1_1 :: n__0:n__s hole_true:false2_1 :: true:false gen_n__0:n__s3_1 :: Nat -> n__0:n__s Lemmas: minus(gen_n__0:n__s3_1(+(2, n5_1)), gen_n__0:n__s3_1(+(1, n5_1))) -> minus(gen_n__0:n__s3_1(1), gen_n__0:n__s3_1(0)), rt in Omega(1 + n5_1) geq(gen_n__0:n__s3_1(n2498_1), gen_n__0:n__s3_1(+(1, n2498_1))) -> false, rt in Omega(1 + n2498_1) Generator Equations: gen_n__0:n__s3_1(0) <=> n__0 gen_n__0:n__s3_1(+(x, 1)) <=> n__s(gen_n__0:n__s3_1(x)) The following defined symbols remain to be analysed: div