/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), 185 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 438 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, n__f(s(0))) f(s(0)) -> f(p(s(0))) p(s(X)) -> X f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(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, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(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)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(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, n__f(s(0))) f(s(0)) -> f(p(s(0))) p(s(X)) -> X f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(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)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(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, n__f(s(0))) f(s(0)) -> f(p(s(0))) p(s(X)) -> X f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(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)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(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, n__f(s(0))) f(s(0)) -> f(p(s(0))) p(s(X)) -> X f(X) -> n__f(X) activate(n__f(X)) -> f(X) activate(X) -> X encArg(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(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)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(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, 9, 10, 11] transitions: 00() -> 0 cons0(0, 0) -> 0 n__f0(0) -> 0 s0(0) -> 0 cons_f0(0) -> 0 cons_p0(0) -> 0 cons_activate0(0) -> 0 f0(0) -> 1 p0(0) -> 2 activate0(0) -> 3 encArg0(0) -> 4 encode_f0(0) -> 5 encode_00() -> 6 encode_cons0(0, 0) -> 7 encode_n__f0(0) -> 8 encode_s0(0) -> 9 encode_p0(0) -> 10 encode_activate0(0) -> 11 01() -> 12 01() -> 15 s1(15) -> 14 n__f1(14) -> 13 cons1(12, 13) -> 1 s1(15) -> 17 p1(17) -> 16 f1(16) -> 1 n__f1(0) -> 1 f1(0) -> 3 01() -> 4 encArg1(0) -> 18 encArg1(0) -> 19 cons1(18, 19) -> 4 encArg1(0) -> 20 n__f1(20) -> 4 encArg1(0) -> 21 s1(21) -> 4 encArg1(0) -> 22 f1(22) -> 4 encArg1(0) -> 23 p1(23) -> 4 encArg1(0) -> 24 activate1(24) -> 4 f1(22) -> 5 01() -> 6 cons1(18, 19) -> 7 n__f1(20) -> 8 s1(21) -> 9 p1(23) -> 10 activate1(24) -> 11 cons1(12, 13) -> 3 f1(16) -> 3 n__f2(16) -> 1 n__f2(0) -> 3 n__f2(22) -> 4 n__f2(22) -> 5 01() -> 18 01() -> 19 01() -> 20 01() -> 21 01() -> 22 01() -> 23 01() -> 24 cons1(18, 19) -> 18 cons1(18, 19) -> 19 cons1(18, 19) -> 20 cons1(18, 19) -> 21 cons1(18, 19) -> 22 cons1(18, 19) -> 23 cons1(18, 19) -> 24 n__f1(20) -> 18 n__f1(20) -> 19 n__f1(20) -> 20 n__f1(20) -> 21 n__f1(20) -> 22 n__f1(20) -> 23 n__f1(20) -> 24 s1(21) -> 18 s1(21) -> 19 s1(21) -> 20 s1(21) -> 21 s1(21) -> 22 s1(21) -> 23 s1(21) -> 24 f1(22) -> 18 f1(22) -> 19 f1(22) -> 20 f1(22) -> 21 f1(22) -> 22 f1(22) -> 23 f1(22) -> 24 p1(23) -> 18 p1(23) -> 19 p1(23) -> 20 p1(23) -> 21 p1(23) -> 22 p1(23) -> 23 p1(23) -> 24 activate1(24) -> 18 activate1(24) -> 19 activate1(24) -> 20 activate1(24) -> 21 activate1(24) -> 22 activate1(24) -> 23 activate1(24) -> 24 02() -> 25 02() -> 28 s2(28) -> 27 n__f2(27) -> 26 cons2(25, 26) -> 1 cons2(25, 26) -> 3 cons2(25, 26) -> 4 cons2(25, 26) -> 5 cons2(25, 26) -> 11 cons2(25, 26) -> 18 cons2(25, 26) -> 19 cons2(25, 26) -> 20 cons2(25, 26) -> 21 cons2(25, 26) -> 22 cons2(25, 26) -> 23 cons2(25, 26) -> 24 s2(28) -> 30 p2(30) -> 29 f2(29) -> 4 f2(29) -> 5 f2(29) -> 11 f2(29) -> 18 f2(29) -> 19 f2(29) -> 20 f2(29) -> 21 f2(29) -> 22 f2(29) -> 23 f2(29) -> 24 n__f2(16) -> 3 n__f2(22) -> 11 n__f2(22) -> 18 n__f2(22) -> 19 n__f2(22) -> 20 n__f2(22) -> 21 f2(20) -> 4 f2(20) -> 11 f2(20) -> 18 f2(20) -> 19 f2(20) -> 20 f2(20) -> 21 f2(22) -> 4 f2(22) -> 10 f2(22) -> 11 f2(22) -> 18 f2(22) -> 19 f2(22) -> 20 f2(22) -> 21 n__f3(29) -> 4 n__f3(20) -> 4 n__f3(29) -> 5 n__f3(29) -> 10 n__f3(20) -> 10 n__f3(29) -> 11 n__f3(20) -> 11 n__f3(29) -> 18 n__f3(20) -> 18 n__f3(29) -> 19 n__f3(20) -> 19 n__f3(29) -> 20 n__f3(20) -> 20 n__f3(29) -> 21 n__f3(20) -> 21 03() -> 31 03() -> 34 s3(34) -> 33 n__f3(33) -> 32 cons3(31, 32) -> 4 cons3(31, 32) -> 5 cons3(31, 32) -> 10 cons3(31, 32) -> 11 cons3(31, 32) -> 18 cons3(31, 32) -> 19 cons3(31, 32) -> 20 cons3(31, 32) -> 21 n__f3(22) -> 4 n__f3(22) -> 10 n__f3(22) -> 11 n__f3(22) -> 18 n__f3(22) -> 19 n__f3(22) -> 20 n__f3(22) -> 21 0 -> 2 0 -> 3 15 -> 16 24 -> 4 24 -> 11 24 -> 18 24 -> 19 24 -> 20 24 -> 21 21 -> 4 21 -> 10 21 -> 11 21 -> 18 21 -> 19 21 -> 20 21 -> 22 21 -> 23 21 -> 24 28 -> 29 ---------------------------------------- (8) BOUNDS(1, n^1)