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