/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 (full) 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), 105 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 104 ms] (8) BOUNDS(1, n^1) ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(0) -> cons(0) f(s(0)) -> f(p(s(0))) p(s(X)) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (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(0) -> 0 encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1) -> cons(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(0) -> cons(0) f(s(0)) -> f(p(s(0))) p(s(X)) -> X The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1) -> cons(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: f(0) -> cons(0) f(s(0)) -> f(p(s(0))) p(s(X)) -> X The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1) -> cons(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (5) RelTrsToTrsProof (UPPER BOUND(ID)) transformed relative TRS to TRS ---------------------------------------- (6) 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: f(0) -> cons(0) f(s(0)) -> f(p(s(0))) p(s(X)) -> X encArg(0) -> 0 encArg(cons(x_1)) -> cons(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1) -> cons(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (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] transitions: 00() -> 0 cons0(0) -> 0 s0(0) -> 0 cons_f0(0) -> 0 cons_p0(0) -> 0 f0(0) -> 1 p0(0) -> 2 encArg0(0) -> 3 encode_f0(0) -> 4 encode_00() -> 5 encode_cons0(0) -> 6 encode_s0(0) -> 7 encode_p0(0) -> 8 01() -> 9 cons1(9) -> 1 01() -> 12 s1(12) -> 11 p1(11) -> 10 f1(10) -> 1 01() -> 3 encArg1(0) -> 13 cons1(13) -> 3 encArg1(0) -> 14 s1(14) -> 3 encArg1(0) -> 15 f1(15) -> 3 encArg1(0) -> 16 p1(16) -> 3 f1(15) -> 4 01() -> 5 cons1(13) -> 6 s1(14) -> 7 p1(16) -> 8 01() -> 13 01() -> 14 01() -> 15 01() -> 16 cons1(13) -> 13 cons1(13) -> 14 cons1(13) -> 15 cons1(13) -> 16 s1(14) -> 13 s1(14) -> 14 s1(14) -> 15 s1(14) -> 16 f1(15) -> 13 f1(15) -> 14 f1(15) -> 15 f1(15) -> 16 p1(16) -> 13 p1(16) -> 14 p1(16) -> 15 p1(16) -> 16 02() -> 17 cons2(17) -> 1 cons2(17) -> 3 cons2(17) -> 4 cons2(17) -> 13 cons2(17) -> 14 cons2(17) -> 15 cons2(17) -> 16 02() -> 20 s2(20) -> 19 p2(19) -> 18 f2(18) -> 3 f2(18) -> 4 f2(18) -> 13 f2(18) -> 14 f2(18) -> 15 f2(18) -> 16 03() -> 21 cons3(21) -> 3 cons3(21) -> 4 cons3(21) -> 8 cons3(21) -> 13 cons3(21) -> 14 0 -> 2 12 -> 10 14 -> 3 14 -> 8 14 -> 13 14 -> 15 14 -> 16 20 -> 18 ---------------------------------------- (8) BOUNDS(1, n^1)