/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 (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), 174 ms] (4) CpxRelTRS (5) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] (6) CpxTRS (7) CpxTrsMatchBoundsTAProof [FINISHED, 291 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: zeros -> cons(0, n__zeros) tail(cons(X, XS)) -> activate(XS) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X 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(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(0) -> 0 encArg(n__zeros) -> n__zeros encArg(cons_zeros) -> zeros encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_zeros -> zeros encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_n__zeros -> n__zeros encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) ---------------------------------------- (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: zeros -> cons(0, n__zeros) tail(cons(X, XS)) -> activate(XS) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(0) -> 0 encArg(n__zeros) -> n__zeros encArg(cons_zeros) -> zeros encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_zeros -> zeros encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_n__zeros -> n__zeros encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) 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: zeros -> cons(0, n__zeros) tail(cons(X, XS)) -> activate(XS) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(0) -> 0 encArg(n__zeros) -> n__zeros encArg(cons_zeros) -> zeros encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_zeros -> zeros encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_n__zeros -> n__zeros encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) 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: zeros -> cons(0, n__zeros) tail(cons(X, XS)) -> activate(XS) zeros -> n__zeros activate(n__zeros) -> zeros activate(X) -> X encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(0) -> 0 encArg(n__zeros) -> n__zeros encArg(cons_zeros) -> zeros encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_zeros -> zeros encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_n__zeros -> n__zeros encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) 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, 6, 7, 8, 9, 10] transitions: cons0(0, 0) -> 0 00() -> 0 n__zeros0() -> 0 cons_zeros0() -> 0 cons_tail0(0) -> 0 cons_activate0(0) -> 0 zeros0() -> 1 tail0(0) -> 2 activate0(0) -> 3 encArg0(0) -> 4 encode_zeros0() -> 5 encode_cons0(0, 0) -> 6 encode_00() -> 7 encode_n__zeros0() -> 8 encode_tail0(0) -> 9 encode_activate0(0) -> 10 01() -> 11 n__zeros1() -> 12 cons1(11, 12) -> 1 activate1(0) -> 2 n__zeros1() -> 1 zeros1() -> 3 encArg1(0) -> 13 encArg1(0) -> 14 cons1(13, 14) -> 4 01() -> 4 n__zeros1() -> 4 zeros1() -> 4 encArg1(0) -> 15 tail1(15) -> 4 encArg1(0) -> 16 activate1(16) -> 4 zeros1() -> 5 cons1(13, 14) -> 6 01() -> 7 n__zeros1() -> 8 tail1(15) -> 9 activate1(16) -> 10 02() -> 17 n__zeros2() -> 18 cons2(17, 18) -> 3 cons2(17, 18) -> 4 cons2(17, 18) -> 5 n__zeros2() -> 3 n__zeros2() -> 4 n__zeros2() -> 5 zeros1() -> 2 cons1(13, 14) -> 13 cons1(13, 14) -> 14 cons1(13, 14) -> 15 cons1(13, 14) -> 16 01() -> 13 01() -> 14 01() -> 15 01() -> 16 n__zeros1() -> 13 n__zeros1() -> 14 n__zeros1() -> 15 n__zeros1() -> 16 zeros1() -> 13 zeros1() -> 14 zeros1() -> 15 zeros1() -> 16 tail1(15) -> 13 tail1(15) -> 14 tail1(15) -> 15 tail1(15) -> 16 activate1(16) -> 13 activate1(16) -> 14 activate1(16) -> 15 activate1(16) -> 16 cons2(17, 18) -> 2 cons2(17, 18) -> 10 cons2(17, 18) -> 13 cons2(17, 18) -> 14 cons2(17, 18) -> 15 cons2(17, 18) -> 16 activate2(14) -> 4 activate2(14) -> 9 activate2(14) -> 10 activate2(14) -> 13 activate2(14) -> 14 activate2(14) -> 15 activate2(14) -> 16 n__zeros2() -> 2 n__zeros2() -> 10 n__zeros2() -> 13 n__zeros2() -> 14 n__zeros2() -> 15 n__zeros2() -> 16 zeros2() -> 4 zeros2() -> 10 zeros2() -> 13 zeros2() -> 14 zeros2() -> 15 zeros2() -> 16 activate2(18) -> 4 activate2(18) -> 9 activate2(18) -> 10 activate2(18) -> 13 activate2(18) -> 14 activate2(18) -> 15 activate2(18) -> 16 03() -> 19 n__zeros3() -> 20 cons3(19, 20) -> 4 cons3(19, 20) -> 10 cons3(19, 20) -> 13 cons3(19, 20) -> 14 cons3(19, 20) -> 15 cons3(19, 20) -> 16 n__zeros3() -> 4 n__zeros3() -> 10 n__zeros3() -> 13 n__zeros3() -> 14 n__zeros3() -> 15 n__zeros3() -> 16 zeros2() -> 9 zeros3() -> 4 zeros3() -> 9 zeros3() -> 10 zeros3() -> 13 zeros3() -> 14 zeros3() -> 15 zeros3() -> 16 04() -> 21 n__zeros4() -> 22 cons4(21, 22) -> 4 cons4(21, 22) -> 9 cons4(21, 22) -> 10 cons4(21, 22) -> 13 cons4(21, 22) -> 14 activate2(20) -> 4 activate2(20) -> 9 activate2(20) -> 10 activate2(20) -> 13 activate2(20) -> 14 n__zeros4() -> 4 n__zeros4() -> 9 n__zeros4() -> 10 n__zeros4() -> 13 n__zeros4() -> 14 activate2(22) -> 4 activate2(22) -> 9 activate2(22) -> 10 activate2(22) -> 13 activate2(22) -> 14 0 -> 3 0 -> 2 16 -> 4 16 -> 10 16 -> 13 16 -> 14 16 -> 15 14 -> 4 14 -> 9 14 -> 10 14 -> 13 14 -> 15 14 -> 16 18 -> 4 18 -> 9 18 -> 10 18 -> 13 18 -> 14 20 -> 4 20 -> 9 20 -> 10 20 -> 13 20 -> 14 22 -> 4 22 -> 9 22 -> 10 22 -> 13 22 -> 14 ---------------------------------------- (8) BOUNDS(1, n^1)