/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 255 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 356 ms] (8) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: terms(N) -> cons(recip(sqr(N))) sqr(0) -> 0 sqr(s) -> s dbl(0) -> 0 dbl(s) -> s add(0, X) -> X add(s, Y) -> s first(0, X) -> nil first(s, cons(Y)) -> cons(Y) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(recip(x_1)) -> recip(encArg(x_1)) encArg(0) -> 0 encArg(s) -> s encArg(nil) -> nil encArg(cons_terms(x_1)) -> terms(encArg(x_1)) encArg(cons_sqr(x_1)) -> sqr(encArg(x_1)) encArg(cons_dbl(x_1)) -> dbl(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_first(x_1, x_2)) -> first(encArg(x_1), encArg(x_2)) encode_terms(x_1) -> terms(encArg(x_1)) encode_cons(x_1) -> cons(encArg(x_1)) encode_recip(x_1) -> recip(encArg(x_1)) encode_sqr(x_1) -> sqr(encArg(x_1)) encode_0 -> 0 encode_s -> s encode_dbl(x_1) -> dbl(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_first(x_1, x_2) -> first(encArg(x_1), encArg(x_2)) encode_nil -> nil ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: terms(N) -> cons(recip(sqr(N))) sqr(0) -> 0 sqr(s) -> s dbl(0) -> 0 dbl(s) -> s add(0, X) -> X add(s, Y) -> s first(0, X) -> nil first(s, cons(Y)) -> cons(Y) The (relative) TRS S consists of the following rules: encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(recip(x_1)) -> recip(encArg(x_1)) encArg(0) -> 0 encArg(s) -> s encArg(nil) -> nil encArg(cons_terms(x_1)) -> terms(encArg(x_1)) encArg(cons_sqr(x_1)) -> sqr(encArg(x_1)) encArg(cons_dbl(x_1)) -> dbl(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_first(x_1, x_2)) -> first(encArg(x_1), encArg(x_2)) encode_terms(x_1) -> terms(encArg(x_1)) encode_cons(x_1) -> cons(encArg(x_1)) encode_recip(x_1) -> recip(encArg(x_1)) encode_sqr(x_1) -> sqr(encArg(x_1)) encode_0 -> 0 encode_s -> s encode_dbl(x_1) -> dbl(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_first(x_1, x_2) -> first(encArg(x_1), encArg(x_2)) encode_nil -> nil Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: terms(N) -> cons(recip(sqr(N))) sqr(0) -> 0 sqr(s) -> s dbl(0) -> 0 dbl(s) -> s add(0, X) -> X add(s, Y) -> s first(0, X) -> nil first(s, cons(Y)) -> cons(Y) The (relative) TRS S consists of the following rules: encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(recip(x_1)) -> recip(encArg(x_1)) encArg(0) -> 0 encArg(s) -> s encArg(nil) -> nil encArg(cons_terms(x_1)) -> terms(encArg(x_1)) encArg(cons_sqr(x_1)) -> sqr(encArg(x_1)) encArg(cons_dbl(x_1)) -> dbl(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_first(x_1, x_2)) -> first(encArg(x_1), encArg(x_2)) encode_terms(x_1) -> terms(encArg(x_1)) encode_cons(x_1) -> cons(encArg(x_1)) encode_recip(x_1) -> recip(encArg(x_1)) encode_sqr(x_1) -> sqr(encArg(x_1)) encode_0 -> 0 encode_s -> s encode_dbl(x_1) -> dbl(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_first(x_1, x_2) -> first(encArg(x_1), encArg(x_2)) encode_nil -> nil Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToTrsProof (UPPER BOUND(ID)) transformed relative TRS to TRS ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: terms(N) -> cons(recip(sqr(N))) sqr(0) -> 0 sqr(s) -> s dbl(0) -> 0 dbl(s) -> s add(0, X) -> X add(s, Y) -> s first(0, X) -> nil first(s, cons(Y)) -> cons(Y) encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(recip(x_1)) -> recip(encArg(x_1)) encArg(0) -> 0 encArg(s) -> s encArg(nil) -> nil encArg(cons_terms(x_1)) -> terms(encArg(x_1)) encArg(cons_sqr(x_1)) -> sqr(encArg(x_1)) encArg(cons_dbl(x_1)) -> dbl(encArg(x_1)) encArg(cons_add(x_1, x_2)) -> add(encArg(x_1), encArg(x_2)) encArg(cons_first(x_1, x_2)) -> first(encArg(x_1), encArg(x_2)) encode_terms(x_1) -> terms(encArg(x_1)) encode_cons(x_1) -> cons(encArg(x_1)) encode_recip(x_1) -> recip(encArg(x_1)) encode_sqr(x_1) -> sqr(encArg(x_1)) encode_0 -> 0 encode_s -> s encode_dbl(x_1) -> dbl(encArg(x_1)) encode_add(x_1, x_2) -> add(encArg(x_1), encArg(x_2)) encode_first(x_1, x_2) -> first(encArg(x_1), encArg(x_2)) encode_nil -> nil S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (7) 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 3. 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, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] transitions: cons0(0) -> 0 recip0(0) -> 0 00() -> 0 s0() -> 0 nil0() -> 0 cons_terms0(0) -> 0 cons_sqr0(0) -> 0 cons_dbl0(0) -> 0 cons_add0(0, 0) -> 0 cons_first0(0, 0) -> 0 terms0(0) -> 1 sqr0(0) -> 2 dbl0(0) -> 3 add0(0, 0) -> 4 first0(0, 0) -> 5 encArg0(0) -> 6 encode_terms0(0) -> 7 encode_cons0(0) -> 8 encode_recip0(0) -> 9 encode_sqr0(0) -> 10 encode_00() -> 11 encode_s0() -> 12 encode_dbl0(0) -> 13 encode_add0(0, 0) -> 14 encode_first0(0, 0) -> 15 encode_nil0() -> 16 sqr1(0) -> 18 recip1(18) -> 17 cons1(17) -> 1 01() -> 2 s1() -> 2 01() -> 3 s1() -> 3 s1() -> 4 nil1() -> 5 cons1(0) -> 5 encArg1(0) -> 19 cons1(19) -> 6 encArg1(0) -> 20 recip1(20) -> 6 01() -> 6 s1() -> 6 nil1() -> 6 encArg1(0) -> 21 terms1(21) -> 6 encArg1(0) -> 22 sqr1(22) -> 6 encArg1(0) -> 23 dbl1(23) -> 6 encArg1(0) -> 24 encArg1(0) -> 25 add1(24, 25) -> 6 encArg1(0) -> 26 encArg1(0) -> 27 first1(26, 27) -> 6 terms1(21) -> 7 cons1(19) -> 8 recip1(20) -> 9 sqr1(22) -> 10 01() -> 11 s1() -> 12 dbl1(23) -> 13 add1(24, 25) -> 14 first1(26, 27) -> 15 nil1() -> 16 sqr2(21) -> 29 recip2(29) -> 28 cons2(28) -> 6 cons2(28) -> 7 01() -> 18 s1() -> 18 cons1(19) -> 19 cons1(19) -> 20 cons1(19) -> 21 cons1(19) -> 22 cons1(19) -> 23 cons1(19) -> 24 cons1(19) -> 25 cons1(19) -> 26 cons1(19) -> 27 recip1(20) -> 19 recip1(20) -> 20 recip1(20) -> 21 recip1(20) -> 22 recip1(20) -> 23 recip1(20) -> 24 recip1(20) -> 25 recip1(20) -> 26 recip1(20) -> 27 01() -> 19 01() -> 20 01() -> 21 01() -> 22 01() -> 23 01() -> 24 01() -> 25 01() -> 26 01() -> 27 s1() -> 19 s1() -> 20 s1() -> 21 s1() -> 22 s1() -> 23 s1() -> 24 s1() -> 25 s1() -> 26 s1() -> 27 nil1() -> 19 nil1() -> 20 nil1() -> 21 nil1() -> 22 nil1() -> 23 nil1() -> 24 nil1() -> 25 nil1() -> 26 nil1() -> 27 terms1(21) -> 19 terms1(21) -> 20 terms1(21) -> 21 terms1(21) -> 22 terms1(21) -> 23 terms1(21) -> 24 terms1(21) -> 25 terms1(21) -> 26 terms1(21) -> 27 sqr1(22) -> 19 sqr1(22) -> 20 sqr1(22) -> 21 sqr1(22) -> 22 sqr1(22) -> 23 sqr1(22) -> 24 sqr1(22) -> 25 sqr1(22) -> 26 sqr1(22) -> 27 dbl1(23) -> 19 dbl1(23) -> 20 dbl1(23) -> 21 dbl1(23) -> 22 dbl1(23) -> 23 dbl1(23) -> 24 dbl1(23) -> 25 dbl1(23) -> 26 dbl1(23) -> 27 add1(24, 25) -> 19 add1(24, 25) -> 20 add1(24, 25) -> 21 add1(24, 25) -> 22 add1(24, 25) -> 23 add1(24, 25) -> 24 add1(24, 25) -> 25 add1(24, 25) -> 26 add1(24, 25) -> 27 first1(26, 27) -> 19 first1(26, 27) -> 20 first1(26, 27) -> 21 first1(26, 27) -> 22 first1(26, 27) -> 23 first1(26, 27) -> 24 first1(26, 27) -> 25 first1(26, 27) -> 26 first1(26, 27) -> 27 cons2(28) -> 19 cons2(28) -> 20 cons2(28) -> 21 cons2(28) -> 22 cons2(28) -> 23 cons2(28) -> 24 cons2(28) -> 25 cons2(28) -> 26 cons2(28) -> 27 02() -> 6 02() -> 10 02() -> 19 02() -> 20 02() -> 21 02() -> 22 02() -> 23 02() -> 24 02() -> 25 02() -> 26 02() -> 27 s2() -> 6 s2() -> 10 s2() -> 19 s2() -> 20 s2() -> 21 s2() -> 22 s2() -> 23 s2() -> 24 s2() -> 25 s2() -> 26 s2() -> 27 02() -> 13 s2() -> 13 nil2() -> 6 nil2() -> 15 nil2() -> 19 nil2() -> 20 nil2() -> 21 nil2() -> 22 nil2() -> 23 nil2() -> 24 nil2() -> 25 cons2(19) -> 6 cons2(19) -> 15 cons2(19) -> 19 cons2(19) -> 20 cons2(19) -> 21 cons2(19) -> 22 cons2(19) -> 23 cons2(19) -> 24 cons2(19) -> 25 02() -> 29 s2() -> 29 cons2(28) -> 15 03() -> 29 s3() -> 29 0 -> 4 25 -> 6 25 -> 14 25 -> 19 25 -> 20 25 -> 21 25 -> 22 25 -> 23 25 -> 24 25 -> 26 25 -> 27 ---------------------------------------- (8) BOUNDS(1, n^1)