/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(?, O(n^1)) proof of /export/starexec/sandbox2/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), 177 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 89 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: b(b(0, y), x) -> y c(c(c(y))) -> c(c(a(a(c(b(0, y)), 0), 0))) a(y, 0) -> b(y, 0) 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_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_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)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) ---------------------------------------- (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: b(b(0, y), x) -> y c(c(c(y))) -> c(c(a(a(c(b(0, y)), 0), 0))) a(y, 0) -> b(y, 0) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_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)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) 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: b(b(0, y), x) -> y c(c(c(y))) -> c(c(a(a(c(b(0, y)), 0), 0))) a(y, 0) -> b(y, 0) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_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)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) 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: b(b(0, y), x) -> y c(c(c(y))) -> c(c(a(a(c(b(0, y)), 0), 0))) a(y, 0) -> b(y, 0) encArg(0) -> 0 encArg(cons_b(x_1, x_2)) -> b(encArg(x_1), encArg(x_2)) encArg(cons_c(x_1)) -> c(encArg(x_1)) encArg(cons_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)) encode_a(x_1, x_2) -> a(encArg(x_1), encArg(x_2)) 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 cons_b0(0, 0) -> 0 cons_c0(0) -> 0 cons_a0(0, 0) -> 0 b0(0, 0) -> 1 c0(0) -> 2 a0(0, 0) -> 3 encArg0(0) -> 4 encode_b0(0, 0) -> 5 encode_00() -> 6 encode_c0(0) -> 7 encode_a0(0, 0) -> 8 01() -> 9 b1(0, 9) -> 3 01() -> 4 encArg1(0) -> 10 encArg1(0) -> 11 b1(10, 11) -> 4 encArg1(0) -> 12 c1(12) -> 4 encArg1(0) -> 13 encArg1(0) -> 14 a1(13, 14) -> 4 b1(10, 11) -> 5 01() -> 6 c1(12) -> 7 a1(13, 14) -> 8 01() -> 10 01() -> 11 01() -> 12 01() -> 13 01() -> 14 b1(10, 11) -> 10 b1(10, 11) -> 11 b1(10, 11) -> 12 b1(10, 11) -> 13 b1(10, 11) -> 14 c1(12) -> 10 c1(12) -> 11 c1(12) -> 12 c1(12) -> 13 c1(12) -> 14 a1(13, 14) -> 10 a1(13, 14) -> 11 a1(13, 14) -> 12 a1(13, 14) -> 13 a1(13, 14) -> 14 02() -> 15 b2(13, 15) -> 4 b2(13, 15) -> 8 b2(13, 15) -> 10 b2(13, 15) -> 11 b2(13, 15) -> 12 b2(13, 15) -> 13 b2(13, 15) -> 14 02() -> 21 b2(21, 12) -> 20 c2(20) -> 19 02() -> 22 a2(19, 22) -> 18 a2(18, 22) -> 17 c2(17) -> 16 c2(16) -> 4 c2(16) -> 7 c2(16) -> 10 c2(16) -> 11 b2(21, 16) -> 20 b2(21, 17) -> 20 03() -> 23 b3(19, 23) -> 18 b3(18, 23) -> 17 11 -> 4 11 -> 5 11 -> 10 11 -> 12 11 -> 13 11 -> 14 11 -> 8 15 -> 4 15 -> 5 15 -> 10 15 -> 11 ---------------------------------------- (8) BOUNDS(1, n^1)