/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), 183 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 141 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: a(x, y) -> b(x, b(0, c(y))) c(b(y, c(x))) -> c(c(b(a(0, 0), y))) b(y, 0) -> y 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_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_b(x_1, x_2) -> b(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_c(x_1) -> c(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: a(x, y) -> b(x, b(0, c(y))) c(b(y, c(x))) -> c(c(b(a(0, 0), y))) b(y, 0) -> y The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_b(x_1, x_2) -> b(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_c(x_1) -> c(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: a(x, y) -> b(x, b(0, c(y))) c(b(y, c(x))) -> c(c(b(a(0, 0), y))) b(y, 0) -> y The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_b(x_1, x_2) -> b(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_c(x_1) -> c(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: a(x, y) -> b(x, b(0, c(y))) c(b(y, c(x))) -> c(c(b(a(0, 0), y))) b(y, 0) -> y encArg(0) -> 0 encArg(cons_a(x_1, x_2)) -> a(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) encode_b(x_1, x_2) -> b(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_c(x_1) -> c(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 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, 7, 8] transitions: 00() -> 0 cons_a0(0, 0) -> 0 cons_c0(0) -> 0 cons_b0(0, 0) -> 0 a0(0, 0) -> 1 c0(0) -> 2 b0(0, 0) -> 3 encArg0(0) -> 4 encode_a0(0, 0) -> 5 encode_b0(0, 0) -> 6 encode_00() -> 7 encode_c0(0) -> 8 01() -> 10 c1(0) -> 11 b1(10, 11) -> 9 b1(0, 9) -> 1 01() -> 4 encArg1(0) -> 12 encArg1(0) -> 13 a1(12, 13) -> 4 encArg1(0) -> 14 c1(14) -> 4 encArg1(0) -> 15 encArg1(0) -> 16 b1(15, 16) -> 4 a1(12, 13) -> 5 b1(15, 16) -> 6 01() -> 7 c1(14) -> 8 02() -> 18 c2(13) -> 19 b2(18, 19) -> 17 b2(12, 17) -> 4 b2(12, 17) -> 5 01() -> 12 01() -> 13 01() -> 14 01() -> 15 01() -> 16 a1(12, 13) -> 12 a1(12, 13) -> 13 a1(12, 13) -> 14 a1(12, 13) -> 15 a1(12, 13) -> 16 c1(14) -> 12 c1(14) -> 13 c1(14) -> 14 c1(14) -> 15 c1(14) -> 16 b1(15, 16) -> 12 b1(15, 16) -> 13 b1(15, 16) -> 14 b1(15, 16) -> 15 b1(15, 16) -> 16 b2(12, 17) -> 12 b2(12, 17) -> 13 b2(12, 17) -> 14 b2(12, 17) -> 15 b2(12, 17) -> 16 02() -> 23 02() -> 24 a2(23, 24) -> 22 b2(22, 15) -> 21 c2(21) -> 20 c2(20) -> 4 c2(20) -> 8 c2(20) -> 12 c2(20) -> 13 c2(20) -> 14 c2(20) -> 15 c2(20) -> 19 b2(22, 22) -> 21 c2(20) -> 20 03() -> 28 03() -> 29 a3(28, 29) -> 27 b3(27, 22) -> 26 c3(26) -> 25 c3(25) -> 20 03() -> 31 c3(24) -> 32 b3(31, 32) -> 30 b3(23, 30) -> 22 04() -> 34 c4(29) -> 35 b4(34, 35) -> 33 b4(28, 33) -> 27 0 -> 3 15 -> 4 15 -> 6 15 -> 12 15 -> 13 15 -> 14 15 -> 16 22 -> 21 ---------------------------------------- (8) BOUNDS(1, n^1)