/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), 407 ms] (4) CpxRelTRS (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] (6) CdtProblem (7) CdtLeafRemovalProof [ComplexityIfPolyImplication, 3 ms] (8) CdtProblem (9) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtGraphSplitRhsProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtLeafRemovalProof [ComplexityIfPolyImplication, 0 ms] (14) CdtProblem (15) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 18 ms] (16) CdtProblem (17) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 337 ms] (18) CdtProblem (19) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 141 ms] (20) CdtProblem (21) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 104 ms] (22) CdtProblem (23) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 106 ms] (24) CdtProblem (25) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 109 ms] (26) CdtProblem (27) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (28) BOUNDS(1, 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: primes -> sieve(from(s(s(0)))) from(X) -> cons(X, n__from(s(X))) head(cons(X, Y)) -> X tail(cons(X, Y)) -> activate(Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) from(X) -> n__from(X) filter(X1, X2) -> n__filter(X1, X2) cons(X1, X2) -> n__cons(X1, X2) activate(n__from(X)) -> from(X) activate(n__filter(X1, X2)) -> filter(X1, X2) activate(n__cons(X1, X2)) -> cons(X1, X2) 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(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(n__from(x_1)) -> n__from(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(divides(x_1, x_2)) -> divides(encArg(x_1), encArg(x_2)) encArg(n__filter(x_1, x_2)) -> n__filter(encArg(x_1), encArg(x_2)) encArg(n__cons(x_1, x_2)) -> n__cons(encArg(x_1), encArg(x_2)) encArg(cons_primes) -> primes encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_filter(x_1, x_2)) -> filter(encArg(x_1), encArg(x_2)) encArg(cons_sieve(x_1)) -> sieve(encArg(x_1)) encArg(cons_cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_primes -> primes encode_sieve(x_1) -> sieve(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__from(x_1) -> n__from(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_false -> false encode_filter(x_1, x_2) -> filter(encArg(x_1), encArg(x_2)) encode_divides(x_1, x_2) -> divides(encArg(x_1), encArg(x_2)) encode_n__filter(x_1, x_2) -> n__filter(encArg(x_1), encArg(x_2)) encode_n__cons(x_1, x_2) -> n__cons(encArg(x_1), encArg(x_2)) ---------------------------------------- (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: primes -> sieve(from(s(s(0)))) from(X) -> cons(X, n__from(s(X))) head(cons(X, Y)) -> X tail(cons(X, Y)) -> activate(Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) from(X) -> n__from(X) filter(X1, X2) -> n__filter(X1, X2) cons(X1, X2) -> n__cons(X1, X2) activate(n__from(X)) -> from(X) activate(n__filter(X1, X2)) -> filter(X1, X2) activate(n__cons(X1, X2)) -> cons(X1, X2) activate(X) -> X The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(n__from(x_1)) -> n__from(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(divides(x_1, x_2)) -> divides(encArg(x_1), encArg(x_2)) encArg(n__filter(x_1, x_2)) -> n__filter(encArg(x_1), encArg(x_2)) encArg(n__cons(x_1, x_2)) -> n__cons(encArg(x_1), encArg(x_2)) encArg(cons_primes) -> primes encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_filter(x_1, x_2)) -> filter(encArg(x_1), encArg(x_2)) encArg(cons_sieve(x_1)) -> sieve(encArg(x_1)) encArg(cons_cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_primes -> primes encode_sieve(x_1) -> sieve(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__from(x_1) -> n__from(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_false -> false encode_filter(x_1, x_2) -> filter(encArg(x_1), encArg(x_2)) encode_divides(x_1, x_2) -> divides(encArg(x_1), encArg(x_2)) encode_n__filter(x_1, x_2) -> n__filter(encArg(x_1), encArg(x_2)) encode_n__cons(x_1, x_2) -> n__cons(encArg(x_1), encArg(x_2)) 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: primes -> sieve(from(s(s(0)))) from(X) -> cons(X, n__from(s(X))) head(cons(X, Y)) -> X tail(cons(X, Y)) -> activate(Y) if(true, X, Y) -> activate(X) if(false, X, Y) -> activate(Y) filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) from(X) -> n__from(X) filter(X1, X2) -> n__filter(X1, X2) cons(X1, X2) -> n__cons(X1, X2) activate(n__from(X)) -> from(X) activate(n__filter(X1, X2)) -> filter(X1, X2) activate(n__cons(X1, X2)) -> cons(X1, X2) activate(X) -> X The (relative) TRS S consists of the following rules: encArg(s(x_1)) -> s(encArg(x_1)) encArg(0) -> 0 encArg(n__from(x_1)) -> n__from(encArg(x_1)) encArg(true) -> true encArg(false) -> false encArg(divides(x_1, x_2)) -> divides(encArg(x_1), encArg(x_2)) encArg(n__filter(x_1, x_2)) -> n__filter(encArg(x_1), encArg(x_2)) encArg(n__cons(x_1, x_2)) -> n__cons(encArg(x_1), encArg(x_2)) encArg(cons_primes) -> primes encArg(cons_from(x_1)) -> from(encArg(x_1)) encArg(cons_head(x_1)) -> head(encArg(x_1)) encArg(cons_tail(x_1)) -> tail(encArg(x_1)) encArg(cons_if(x_1, x_2, x_3)) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encArg(cons_filter(x_1, x_2)) -> filter(encArg(x_1), encArg(x_2)) encArg(cons_sieve(x_1)) -> sieve(encArg(x_1)) encArg(cons_cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_primes -> primes encode_sieve(x_1) -> sieve(encArg(x_1)) encode_from(x_1) -> from(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__from(x_1) -> n__from(encArg(x_1)) encode_head(x_1) -> head(encArg(x_1)) encode_tail(x_1) -> tail(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) encode_if(x_1, x_2, x_3) -> if(encArg(x_1), encArg(x_2), encArg(x_3)) encode_true -> true encode_false -> false encode_filter(x_1, x_2) -> filter(encArg(x_1), encArg(x_2)) encode_divides(x_1, x_2) -> divides(encArg(x_1), encArg(x_2)) encode_n__filter(x_1, x_2) -> n__filter(encArg(x_1), encArg(x_2)) encode_n__cons(x_1, x_2) -> n__cons(encArg(x_1), encArg(x_2)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) encode_primes -> primes encode_sieve(z0) -> sieve(encArg(z0)) encode_from(z0) -> from(encArg(z0)) encode_s(z0) -> s(encArg(z0)) encode_0 -> 0 encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1)) encode_n__from(z0) -> n__from(encArg(z0)) encode_head(z0) -> head(encArg(z0)) encode_tail(z0) -> tail(encArg(z0)) encode_activate(z0) -> activate(encArg(z0)) encode_if(z0, z1, z2) -> if(encArg(z0), encArg(z1), encArg(z2)) encode_true -> true encode_false -> false encode_filter(z0, z1) -> filter(encArg(z0), encArg(z1)) encode_divides(z0, z1) -> divides(encArg(z0), encArg(z1)) encode_n__filter(z0, z1) -> n__filter(encArg(z0), encArg(z1)) encode_n__cons(z0, z1) -> n__cons(encArg(z0), encArg(z1)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 tail(cons(z0, z1)) -> activate(z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(s(s(z0)), cons(z1, z2)) -> if(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))) filter(z0, z1) -> n__filter(z0, z1) sieve(cons(z0, z1)) -> cons(z0, n__filter(z0, sieve(activate(z1)))) cons(z0, z1) -> n__cons(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(0) -> c1 ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(true) -> c3 ENCARG(false) -> c4 ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_head(z0)) -> c10(HEAD(encArg(z0)), ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(TAIL(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_sieve(z0)) -> c14(SIEVE(encArg(z0)), ENCARG(z0)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) ENCODE_PRIMES -> c17(PRIMES) ENCODE_SIEVE(z0) -> c18(SIEVE(encArg(z0)), ENCARG(z0)) ENCODE_FROM(z0) -> c19(FROM(encArg(z0)), ENCARG(z0)) ENCODE_S(z0) -> c20(ENCARG(z0)) ENCODE_0 -> c21 ENCODE_CONS(z0, z1) -> c22(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_N__FROM(z0) -> c23(ENCARG(z0)) ENCODE_HEAD(z0) -> c24(HEAD(encArg(z0)), ENCARG(z0)) ENCODE_TAIL(z0) -> c25(TAIL(encArg(z0)), ENCARG(z0)) ENCODE_ACTIVATE(z0) -> c26(ACTIVATE(encArg(z0)), ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c27(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_TRUE -> c28 ENCODE_FALSE -> c29 ENCODE_FILTER(z0, z1) -> c30(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_DIVIDES(z0, z1) -> c31(ENCARG(z0), ENCARG(z1)) ENCODE_N__FILTER(z0, z1) -> c32(ENCARG(z0), ENCARG(z1)) ENCODE_N__CONS(z0, z1) -> c33(ENCARG(z0), ENCARG(z1)) PRIMES -> c34(SIEVE(from(s(s(0)))), FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 HEAD(cons(z0, z1)) -> c37 TAIL(cons(z0, z1)) -> c38(ACTIVATE(z1)) IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(s(s(z0)), cons(z1, z2)) -> c41(IF(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))), ACTIVATE(z2), SIEVE(z1)) FILTER(z0, z1) -> c42 SIEVE(cons(z0, z1)) -> c43(CONS(z0, n__filter(z0, sieve(activate(z1)))), SIEVE(activate(z1)), ACTIVATE(z1)) CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 S tuples: PRIMES -> c34(SIEVE(from(s(s(0)))), FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 HEAD(cons(z0, z1)) -> c37 TAIL(cons(z0, z1)) -> c38(ACTIVATE(z1)) IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(s(s(z0)), cons(z1, z2)) -> c41(IF(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))), ACTIVATE(z2), SIEVE(z1)) FILTER(z0, z1) -> c42 SIEVE(cons(z0, z1)) -> c43(CONS(z0, n__filter(z0, sieve(activate(z1)))), SIEVE(activate(z1)), ACTIVATE(z1)) CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 K tuples:none Defined Rule Symbols: primes, from_1, head_1, tail_1, if_3, filter_2, sieve_1, cons_2, activate_1, encArg_1, encode_primes, encode_sieve_1, encode_from_1, encode_s_1, encode_0, encode_cons_2, encode_n__from_1, encode_head_1, encode_tail_1, encode_activate_1, encode_if_3, encode_true, encode_false, encode_filter_2, encode_divides_2, encode_n__filter_2, encode_n__cons_2 Defined Pair Symbols: ENCARG_1, ENCODE_PRIMES, ENCODE_SIEVE_1, ENCODE_FROM_1, ENCODE_S_1, ENCODE_0, ENCODE_CONS_2, ENCODE_N__FROM_1, ENCODE_HEAD_1, ENCODE_TAIL_1, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_TRUE, ENCODE_FALSE, ENCODE_FILTER_2, ENCODE_DIVIDES_2, ENCODE_N__FILTER_2, ENCODE_N__CONS_2, PRIMES, FROM_1, HEAD_1, TAIL_1, IF_3, FILTER_2, SIEVE_1, CONS_2, ACTIVATE_1 Compound Symbols: c_1, c1, c2_1, c3, c4, c5_2, c6_2, c7_2, c8_1, c9_2, c10_2, c11_2, c12_4, c13_3, c14_2, c15_3, c16_2, c17_1, c18_2, c19_2, c20_1, c21, c22_3, c23_1, c24_2, c25_2, c26_2, c27_4, c28, c29, c30_3, c31_2, c32_2, c33_2, c34_2, c35_1, c36, c37, c38_1, c39_1, c40_1, c41_3, c42, c43_3, c44, c45_1, c46_1, c47_1, c48 ---------------------------------------- (7) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 9 leading nodes: ENCODE_S(z0) -> c20(ENCARG(z0)) ENCODE_N__FROM(z0) -> c23(ENCARG(z0)) ENCODE_DIVIDES(z0, z1) -> c31(ENCARG(z0), ENCARG(z1)) ENCODE_N__FILTER(z0, z1) -> c32(ENCARG(z0), ENCARG(z1)) ENCODE_N__CONS(z0, z1) -> c33(ENCARG(z0), ENCARG(z1)) ENCODE_PRIMES -> c17(PRIMES) TAIL(cons(z0, z1)) -> c38(ACTIVATE(z1)) FILTER(s(s(z0)), cons(z1, z2)) -> c41(IF(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))), ACTIVATE(z2), SIEVE(z1)) SIEVE(cons(z0, z1)) -> c43(CONS(z0, n__filter(z0, sieve(activate(z1)))), SIEVE(activate(z1)), ACTIVATE(z1)) Removed 7 trailing nodes: ENCARG(false) -> c4 ENCARG(true) -> c3 ENCARG(0) -> c1 ENCODE_TRUE -> c28 HEAD(cons(z0, z1)) -> c37 ENCODE_0 -> c21 ENCODE_FALSE -> c29 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) encode_primes -> primes encode_sieve(z0) -> sieve(encArg(z0)) encode_from(z0) -> from(encArg(z0)) encode_s(z0) -> s(encArg(z0)) encode_0 -> 0 encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1)) encode_n__from(z0) -> n__from(encArg(z0)) encode_head(z0) -> head(encArg(z0)) encode_tail(z0) -> tail(encArg(z0)) encode_activate(z0) -> activate(encArg(z0)) encode_if(z0, z1, z2) -> if(encArg(z0), encArg(z1), encArg(z2)) encode_true -> true encode_false -> false encode_filter(z0, z1) -> filter(encArg(z0), encArg(z1)) encode_divides(z0, z1) -> divides(encArg(z0), encArg(z1)) encode_n__filter(z0, z1) -> n__filter(encArg(z0), encArg(z1)) encode_n__cons(z0, z1) -> n__cons(encArg(z0), encArg(z1)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 tail(cons(z0, z1)) -> activate(z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(s(s(z0)), cons(z1, z2)) -> if(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))) filter(z0, z1) -> n__filter(z0, z1) sieve(cons(z0, z1)) -> cons(z0, n__filter(z0, sieve(activate(z1)))) cons(z0, z1) -> n__cons(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_head(z0)) -> c10(HEAD(encArg(z0)), ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(TAIL(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_sieve(z0)) -> c14(SIEVE(encArg(z0)), ENCARG(z0)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) ENCODE_SIEVE(z0) -> c18(SIEVE(encArg(z0)), ENCARG(z0)) ENCODE_FROM(z0) -> c19(FROM(encArg(z0)), ENCARG(z0)) ENCODE_CONS(z0, z1) -> c22(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_HEAD(z0) -> c24(HEAD(encArg(z0)), ENCARG(z0)) ENCODE_TAIL(z0) -> c25(TAIL(encArg(z0)), ENCARG(z0)) ENCODE_ACTIVATE(z0) -> c26(ACTIVATE(encArg(z0)), ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c27(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_FILTER(z0, z1) -> c30(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) PRIMES -> c34(SIEVE(from(s(s(0)))), FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 S tuples: PRIMES -> c34(SIEVE(from(s(s(0)))), FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 K tuples:none Defined Rule Symbols: primes, from_1, head_1, tail_1, if_3, filter_2, sieve_1, cons_2, activate_1, encArg_1, encode_primes, encode_sieve_1, encode_from_1, encode_s_1, encode_0, encode_cons_2, encode_n__from_1, encode_head_1, encode_tail_1, encode_activate_1, encode_if_3, encode_true, encode_false, encode_filter_2, encode_divides_2, encode_n__filter_2, encode_n__cons_2 Defined Pair Symbols: ENCARG_1, ENCODE_SIEVE_1, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_HEAD_1, ENCODE_TAIL_1, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2, PRIMES, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c10_2, c11_2, c12_4, c13_3, c14_2, c15_3, c16_2, c18_2, c19_2, c22_3, c24_2, c25_2, c26_2, c27_4, c30_3, c34_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48 ---------------------------------------- (9) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 7 trailing tuple parts ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) encode_primes -> primes encode_sieve(z0) -> sieve(encArg(z0)) encode_from(z0) -> from(encArg(z0)) encode_s(z0) -> s(encArg(z0)) encode_0 -> 0 encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1)) encode_n__from(z0) -> n__from(encArg(z0)) encode_head(z0) -> head(encArg(z0)) encode_tail(z0) -> tail(encArg(z0)) encode_activate(z0) -> activate(encArg(z0)) encode_if(z0, z1, z2) -> if(encArg(z0), encArg(z1), encArg(z2)) encode_true -> true encode_false -> false encode_filter(z0, z1) -> filter(encArg(z0), encArg(z1)) encode_divides(z0, z1) -> divides(encArg(z0), encArg(z1)) encode_n__filter(z0, z1) -> n__filter(encArg(z0), encArg(z1)) encode_n__cons(z0, z1) -> n__cons(encArg(z0), encArg(z1)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 tail(cons(z0, z1)) -> activate(z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(s(s(z0)), cons(z1, z2)) -> if(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))) filter(z0, z1) -> n__filter(z0, z1) sieve(cons(z0, z1)) -> cons(z0, n__filter(z0, sieve(activate(z1)))) cons(z0, z1) -> n__cons(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) ENCODE_FROM(z0) -> c19(FROM(encArg(z0)), ENCARG(z0)) ENCODE_CONS(z0, z1) -> c22(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCODE_ACTIVATE(z0) -> c26(ACTIVATE(encArg(z0)), ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c27(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCODE_FILTER(z0, z1) -> c30(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) ENCODE_SIEVE(z0) -> c18(ENCARG(z0)) ENCODE_HEAD(z0) -> c24(ENCARG(z0)) ENCODE_TAIL(z0) -> c25(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) S tuples: FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 PRIMES -> c34(FROM(s(s(0)))) K tuples:none Defined Rule Symbols: primes, from_1, head_1, tail_1, if_3, filter_2, sieve_1, cons_2, activate_1, encArg_1, encode_primes, encode_sieve_1, encode_from_1, encode_s_1, encode_0, encode_cons_2, encode_n__from_1, encode_head_1, encode_tail_1, encode_activate_1, encode_if_3, encode_true, encode_false, encode_filter_2, encode_divides_2, encode_n__filter_2, encode_n__cons_2 Defined Pair Symbols: ENCARG_1, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, ENCODE_SIEVE_1, ENCODE_HEAD_1, ENCODE_TAIL_1, PRIMES Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c19_2, c22_3, c26_2, c27_4, c30_3, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c18_1, c24_1, c25_1, c34_1 ---------------------------------------- (11) CdtGraphSplitRhsProof (BOTH BOUNDS(ID, ID)) Split RHS of tuples not part of any SCC ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) encode_primes -> primes encode_sieve(z0) -> sieve(encArg(z0)) encode_from(z0) -> from(encArg(z0)) encode_s(z0) -> s(encArg(z0)) encode_0 -> 0 encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1)) encode_n__from(z0) -> n__from(encArg(z0)) encode_head(z0) -> head(encArg(z0)) encode_tail(z0) -> tail(encArg(z0)) encode_activate(z0) -> activate(encArg(z0)) encode_if(z0, z1, z2) -> if(encArg(z0), encArg(z1), encArg(z2)) encode_true -> true encode_false -> false encode_filter(z0, z1) -> filter(encArg(z0), encArg(z1)) encode_divides(z0, z1) -> divides(encArg(z0), encArg(z1)) encode_n__filter(z0, z1) -> n__filter(encArg(z0), encArg(z1)) encode_n__cons(z0, z1) -> n__cons(encArg(z0), encArg(z1)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 tail(cons(z0, z1)) -> activate(z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(s(s(z0)), cons(z1, z2)) -> if(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))) filter(z0, z1) -> n__filter(z0, z1) sieve(cons(z0, z1)) -> cons(z0, n__filter(z0, sieve(activate(z1)))) cons(z0, z1) -> n__cons(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) ENCODE_SIEVE(z0) -> c18(ENCARG(z0)) ENCODE_HEAD(z0) -> c24(ENCARG(z0)) ENCODE_TAIL(z0) -> c25(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_FROM(z0) -> c1(ENCARG(z0)) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_CONS(z0, z1) -> c1(ENCARG(z0)) ENCODE_CONS(z0, z1) -> c1(ENCARG(z1)) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_ACTIVATE(z0) -> c1(ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_IF(z0, z1, z2) -> c1(ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c1(ENCARG(z1)) ENCODE_IF(z0, z1, z2) -> c1(ENCARG(z2)) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) ENCODE_FILTER(z0, z1) -> c1(ENCARG(z0)) ENCODE_FILTER(z0, z1) -> c1(ENCARG(z1)) S tuples: FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 PRIMES -> c34(FROM(s(s(0)))) K tuples:none Defined Rule Symbols: primes, from_1, head_1, tail_1, if_3, filter_2, sieve_1, cons_2, activate_1, encArg_1, encode_primes, encode_sieve_1, encode_from_1, encode_s_1, encode_0, encode_cons_2, encode_n__from_1, encode_head_1, encode_tail_1, encode_activate_1, encode_if_3, encode_true, encode_false, encode_filter_2, encode_divides_2, encode_n__filter_2, encode_n__cons_2 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, ENCODE_SIEVE_1, ENCODE_HEAD_1, ENCODE_TAIL_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c18_1, c24_1, c25_1, c34_1, c1_1 ---------------------------------------- (13) CdtLeafRemovalProof (ComplexityIfPolyImplication) Removed 12 leading nodes: ENCODE_SIEVE(z0) -> c18(ENCARG(z0)) ENCODE_HEAD(z0) -> c24(ENCARG(z0)) ENCODE_TAIL(z0) -> c25(ENCARG(z0)) ENCODE_FROM(z0) -> c1(ENCARG(z0)) ENCODE_CONS(z0, z1) -> c1(ENCARG(z0)) ENCODE_CONS(z0, z1) -> c1(ENCARG(z1)) ENCODE_ACTIVATE(z0) -> c1(ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c1(ENCARG(z0)) ENCODE_IF(z0, z1, z2) -> c1(ENCARG(z1)) ENCODE_IF(z0, z1, z2) -> c1(ENCARG(z2)) ENCODE_FILTER(z0, z1) -> c1(ENCARG(z0)) ENCODE_FILTER(z0, z1) -> c1(ENCARG(z1)) ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) encode_primes -> primes encode_sieve(z0) -> sieve(encArg(z0)) encode_from(z0) -> from(encArg(z0)) encode_s(z0) -> s(encArg(z0)) encode_0 -> 0 encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1)) encode_n__from(z0) -> n__from(encArg(z0)) encode_head(z0) -> head(encArg(z0)) encode_tail(z0) -> tail(encArg(z0)) encode_activate(z0) -> activate(encArg(z0)) encode_if(z0, z1, z2) -> if(encArg(z0), encArg(z1), encArg(z2)) encode_true -> true encode_false -> false encode_filter(z0, z1) -> filter(encArg(z0), encArg(z1)) encode_divides(z0, z1) -> divides(encArg(z0), encArg(z1)) encode_n__filter(z0, z1) -> n__filter(encArg(z0), encArg(z1)) encode_n__cons(z0, z1) -> n__cons(encArg(z0), encArg(z1)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) head(cons(z0, z1)) -> z0 tail(cons(z0, z1)) -> activate(z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(s(s(z0)), cons(z1, z2)) -> if(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))) filter(z0, z1) -> n__filter(z0, z1) sieve(cons(z0, z1)) -> cons(z0, n__filter(z0, sieve(activate(z1)))) cons(z0, z1) -> n__cons(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples: FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 PRIMES -> c34(FROM(s(s(0)))) K tuples:none Defined Rule Symbols: primes, from_1, head_1, tail_1, if_3, filter_2, sieve_1, cons_2, activate_1, encArg_1, encode_primes, encode_sieve_1, encode_from_1, encode_s_1, encode_0, encode_cons_2, encode_n__from_1, encode_head_1, encode_tail_1, encode_activate_1, encode_if_3, encode_true, encode_false, encode_filter_2, encode_divides_2, encode_n__filter_2, encode_n__cons_2 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (15) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: encode_primes -> primes encode_sieve(z0) -> sieve(encArg(z0)) encode_from(z0) -> from(encArg(z0)) encode_s(z0) -> s(encArg(z0)) encode_0 -> 0 encode_cons(z0, z1) -> cons(encArg(z0), encArg(z1)) encode_n__from(z0) -> n__from(encArg(z0)) encode_head(z0) -> head(encArg(z0)) encode_tail(z0) -> tail(encArg(z0)) encode_activate(z0) -> activate(encArg(z0)) encode_if(z0, z1, z2) -> if(encArg(z0), encArg(z1), encArg(z2)) encode_true -> true encode_false -> false encode_filter(z0, z1) -> filter(encArg(z0), encArg(z1)) encode_divides(z0, z1) -> divides(encArg(z0), encArg(z1)) encode_n__filter(z0, z1) -> n__filter(encArg(z0), encArg(z1)) encode_n__cons(z0, z1) -> n__cons(encArg(z0), encArg(z1)) head(cons(z0, z1)) -> z0 tail(cons(z0, z1)) -> activate(z1) filter(s(s(z0)), cons(z1, z2)) -> if(divides(s(s(z0)), z1), n__filter(s(s(z0)), activate(z2)), n__cons(z1, n__filter(z0, sieve(z1)))) sieve(cons(z0, z1)) -> cons(z0, n__filter(z0, sieve(activate(z1)))) ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) cons(z0, z1) -> n__cons(z0, z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(z0, z1) -> n__filter(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples: FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 PRIMES -> c34(FROM(s(s(0)))) K tuples:none Defined Rule Symbols: encArg_1, primes, from_1, cons_2, if_3, filter_2, activate_1 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (17) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) We considered the (Usable) Rules:none And the Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(ACTIVATE(x_1)) = 0 POL(CONS(x_1, x_2)) = 0 POL(ENCARG(x_1)) = [2]x_1 POL(ENCODE_ACTIVATE(x_1)) = 0 POL(ENCODE_CONS(x_1, x_2)) = x_1 POL(ENCODE_FILTER(x_1, x_2)) = x_2 POL(ENCODE_FROM(x_1)) = [1] POL(ENCODE_IF(x_1, x_2, x_3)) = [1] POL(FILTER(x_1, x_2)) = 0 POL(FROM(x_1)) = 0 POL(IF(x_1, x_2, x_3)) = [1] POL(PRIMES) = 0 POL(activate(x_1)) = [3] + [3]x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c14(x_1)) = x_1 POL(c15(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c16(x_1, x_2)) = x_1 + x_2 POL(c2(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36) = 0 POL(c39(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42) = 0 POL(c44) = 0 POL(c45(x_1)) = x_1 POL(c46(x_1)) = x_1 POL(c47(x_1)) = x_1 POL(c48) = 0 POL(c5(x_1, x_2)) = x_1 + x_2 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = [3] + x_1 POL(cons_activate(x_1)) = x_1 POL(cons_cons(x_1, x_2)) = x_1 + x_2 POL(cons_filter(x_1, x_2)) = x_1 + x_2 POL(cons_from(x_1)) = x_1 POL(cons_head(x_1)) = [3] + x_1 POL(cons_if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(cons_primes) = 0 POL(cons_sieve(x_1)) = [3] + x_1 POL(cons_tail(x_1)) = [3] + x_1 POL(divides(x_1, x_2)) = x_1 + x_2 POL(encArg(x_1)) = [3]x_1 POL(false) = 0 POL(filter(x_1, x_2)) = [3] + [3]x_1 + [3]x_2 POL(from(x_1)) = [3] POL(head(x_1)) = [3] + x_1 POL(if(x_1, x_2, x_3)) = [3] + [3]x_1 + [3]x_2 + [3]x_3 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__filter(x_1, x_2)) = x_1 + x_2 POL(n__from(x_1)) = x_1 POL(primes) = [3] POL(s(x_1)) = x_1 POL(sieve(x_1)) = [3] POL(tail(x_1)) = [3] + x_1 POL(true) = 0 ---------------------------------------- (18) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) cons(z0, z1) -> n__cons(z0, z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(z0, z1) -> n__filter(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples: FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 PRIMES -> c34(FROM(s(s(0)))) K tuples: IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) Defined Rule Symbols: encArg_1, primes, from_1, cons_2, if_3, filter_2, activate_1 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (19) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. PRIMES -> c34(FROM(s(s(0)))) We considered the (Usable) Rules:none And the Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = 0 POL(ACTIVATE(x_1)) = 0 POL(CONS(x_1, x_2)) = 0 POL(ENCARG(x_1)) = x_1 POL(ENCODE_ACTIVATE(x_1)) = [1] + x_1 POL(ENCODE_CONS(x_1, x_2)) = 0 POL(ENCODE_FILTER(x_1, x_2)) = 0 POL(ENCODE_FROM(x_1)) = [1] POL(ENCODE_IF(x_1, x_2, x_3)) = 0 POL(FILTER(x_1, x_2)) = 0 POL(FROM(x_1)) = 0 POL(IF(x_1, x_2, x_3)) = 0 POL(PRIMES) = [1] POL(activate(x_1)) = [3] + [3]x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c14(x_1)) = x_1 POL(c15(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c16(x_1, x_2)) = x_1 + x_2 POL(c2(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36) = 0 POL(c39(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42) = 0 POL(c44) = 0 POL(c45(x_1)) = x_1 POL(c46(x_1)) = x_1 POL(c47(x_1)) = x_1 POL(c48) = 0 POL(c5(x_1, x_2)) = x_1 + x_2 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = [3] + x_1 POL(cons_activate(x_1)) = x_1 POL(cons_cons(x_1, x_2)) = x_1 + x_2 POL(cons_filter(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_from(x_1)) = x_1 POL(cons_head(x_1)) = [3] + x_1 POL(cons_if(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(cons_primes) = [1] POL(cons_sieve(x_1)) = [3] + x_1 POL(cons_tail(x_1)) = [3] + x_1 POL(divides(x_1, x_2)) = x_1 + x_2 POL(encArg(x_1)) = [3]x_1 POL(false) = 0 POL(filter(x_1, x_2)) = [3] + [3]x_1 + [3]x_2 POL(from(x_1)) = [3] POL(head(x_1)) = [3] + x_1 POL(if(x_1, x_2, x_3)) = [3] + [3]x_1 + [3]x_2 + [3]x_3 POL(n__cons(x_1, x_2)) = x_1 + x_2 POL(n__filter(x_1, x_2)) = x_1 + x_2 POL(n__from(x_1)) = x_1 POL(primes) = [3] POL(s(x_1)) = x_1 POL(sieve(x_1)) = [3] POL(tail(x_1)) = [3] + x_1 POL(true) = 0 ---------------------------------------- (20) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) cons(z0, z1) -> n__cons(z0, z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(z0, z1) -> n__filter(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples: FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 K tuples: IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) PRIMES -> c34(FROM(s(s(0)))) Defined Rule Symbols: encArg_1, primes, from_1, cons_2, if_3, filter_2, activate_1 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (21) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 FILTER(z0, z1) -> c42 ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 We considered the (Usable) Rules:none And the Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ACTIVATE(x_1)) = [1] POL(CONS(x_1, x_2)) = 0 POL(ENCARG(x_1)) = x_1 POL(ENCODE_ACTIVATE(x_1)) = [1] POL(ENCODE_CONS(x_1, x_2)) = x_2 POL(ENCODE_FILTER(x_1, x_2)) = [1] + x_1 POL(ENCODE_FROM(x_1)) = [1] POL(ENCODE_IF(x_1, x_2, x_3)) = [1] POL(FILTER(x_1, x_2)) = [1] POL(FROM(x_1)) = [1] POL(IF(x_1, x_2, x_3)) = [1] POL(PRIMES) = [1] POL(activate(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c14(x_1)) = x_1 POL(c15(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c16(x_1, x_2)) = x_1 + x_2 POL(c2(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36) = 0 POL(c39(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42) = 0 POL(c44) = 0 POL(c45(x_1)) = x_1 POL(c46(x_1)) = x_1 POL(c47(x_1)) = x_1 POL(c48) = 0 POL(c5(x_1, x_2)) = x_1 + x_2 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_activate(x_1)) = [1] + x_1 POL(cons_cons(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_filter(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_from(x_1)) = [1] + x_1 POL(cons_head(x_1)) = [1] + x_1 POL(cons_if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(cons_primes) = [1] POL(cons_sieve(x_1)) = [1] + x_1 POL(cons_tail(x_1)) = [1] + x_1 POL(divides(x_1, x_2)) = [1] + x_1 + x_2 POL(encArg(x_1)) = [1] + x_1 POL(false) = [1] POL(filter(x_1, x_2)) = [1] + x_1 + x_2 POL(from(x_1)) = [1] + x_1 POL(head(x_1)) = [1] + x_1 POL(if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(n__cons(x_1, x_2)) = [1] + x_1 + x_2 POL(n__filter(x_1, x_2)) = [1] + x_1 + x_2 POL(n__from(x_1)) = [1] + x_1 POL(primes) = [1] POL(s(x_1)) = [1] + x_1 POL(sieve(x_1)) = [1] + x_1 POL(tail(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (22) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) cons(z0, z1) -> n__cons(z0, z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(z0, z1) -> n__filter(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples: CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) K tuples: IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) PRIMES -> c34(FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 FILTER(z0, z1) -> c42 ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 Defined Rule Symbols: encArg_1, primes, from_1, cons_2, if_3, filter_2, activate_1 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (23) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. CONS(z0, z1) -> c44 ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) We considered the (Usable) Rules:none And the Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ACTIVATE(x_1)) = [1] POL(CONS(x_1, x_2)) = [1] POL(ENCARG(x_1)) = x_1 POL(ENCODE_ACTIVATE(x_1)) = [1] POL(ENCODE_CONS(x_1, x_2)) = [1] + x_2 POL(ENCODE_FILTER(x_1, x_2)) = x_1 POL(ENCODE_FROM(x_1)) = [1] + x_1 POL(ENCODE_IF(x_1, x_2, x_3)) = [1] POL(FILTER(x_1, x_2)) = 0 POL(FROM(x_1)) = [1] POL(IF(x_1, x_2, x_3)) = [1] POL(PRIMES) = [1] POL(activate(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c14(x_1)) = x_1 POL(c15(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c16(x_1, x_2)) = x_1 + x_2 POL(c2(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36) = 0 POL(c39(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42) = 0 POL(c44) = 0 POL(c45(x_1)) = x_1 POL(c46(x_1)) = x_1 POL(c47(x_1)) = x_1 POL(c48) = 0 POL(c5(x_1, x_2)) = x_1 + x_2 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_activate(x_1)) = [1] + x_1 POL(cons_cons(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_filter(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_from(x_1)) = [1] + x_1 POL(cons_head(x_1)) = [1] + x_1 POL(cons_if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(cons_primes) = [1] POL(cons_sieve(x_1)) = [1] + x_1 POL(cons_tail(x_1)) = [1] + x_1 POL(divides(x_1, x_2)) = [1] + x_1 + x_2 POL(encArg(x_1)) = [1] + x_1 POL(false) = [1] POL(filter(x_1, x_2)) = [1] + x_1 + x_2 POL(from(x_1)) = [1] + x_1 POL(head(x_1)) = [1] + x_1 POL(if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(n__cons(x_1, x_2)) = [1] + x_1 + x_2 POL(n__filter(x_1, x_2)) = [1] + x_1 + x_2 POL(n__from(x_1)) = [1] + x_1 POL(primes) = [1] POL(s(x_1)) = [1] + x_1 POL(sieve(x_1)) = [1] + x_1 POL(tail(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (24) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) cons(z0, z1) -> n__cons(z0, z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(z0, z1) -> n__filter(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples: ACTIVATE(n__from(z0)) -> c45(FROM(z0)) K tuples: IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) PRIMES -> c34(FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 FILTER(z0, z1) -> c42 ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 CONS(z0, z1) -> c44 ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) Defined Rule Symbols: encArg_1, primes, from_1, cons_2, if_3, filter_2, activate_1 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (25) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. ACTIVATE(n__from(z0)) -> c45(FROM(z0)) We considered the (Usable) Rules:none And the Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ACTIVATE(x_1)) = [1] POL(CONS(x_1, x_2)) = 0 POL(ENCARG(x_1)) = x_1 POL(ENCODE_ACTIVATE(x_1)) = [1] POL(ENCODE_CONS(x_1, x_2)) = x_2 POL(ENCODE_FILTER(x_1, x_2)) = [1] POL(ENCODE_FROM(x_1)) = x_1 POL(ENCODE_IF(x_1, x_2, x_3)) = [1] POL(FILTER(x_1, x_2)) = [1] POL(FROM(x_1)) = 0 POL(IF(x_1, x_2, x_3)) = [1] POL(PRIMES) = [1] POL(activate(x_1)) = [1] + x_1 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 POL(c13(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c14(x_1)) = x_1 POL(c15(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c16(x_1, x_2)) = x_1 + x_2 POL(c2(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36) = 0 POL(c39(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c42) = 0 POL(c44) = 0 POL(c45(x_1)) = x_1 POL(c46(x_1)) = x_1 POL(c47(x_1)) = x_1 POL(c48) = 0 POL(c5(x_1, x_2)) = x_1 + x_2 POL(c6(x_1, x_2)) = x_1 + x_2 POL(c7(x_1, x_2)) = x_1 + x_2 POL(c8(x_1)) = x_1 POL(c9(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_activate(x_1)) = [1] + x_1 POL(cons_cons(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_filter(x_1, x_2)) = [1] + x_1 + x_2 POL(cons_from(x_1)) = [1] + x_1 POL(cons_head(x_1)) = [1] + x_1 POL(cons_if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(cons_primes) = [1] POL(cons_sieve(x_1)) = [1] + x_1 POL(cons_tail(x_1)) = [1] + x_1 POL(divides(x_1, x_2)) = [1] + x_1 + x_2 POL(encArg(x_1)) = [1] + x_1 POL(false) = [1] POL(filter(x_1, x_2)) = [1] + x_1 + x_2 POL(from(x_1)) = [1] + x_1 POL(head(x_1)) = [1] + x_1 POL(if(x_1, x_2, x_3)) = [1] + x_1 + x_2 + x_3 POL(n__cons(x_1, x_2)) = [1] + x_1 + x_2 POL(n__filter(x_1, x_2)) = [1] + x_1 + x_2 POL(n__from(x_1)) = [1] + x_1 POL(primes) = [1] POL(s(x_1)) = [1] + x_1 POL(sieve(x_1)) = [1] + x_1 POL(tail(x_1)) = [1] + x_1 POL(true) = [1] ---------------------------------------- (26) Obligation: Complexity Dependency Tuples Problem Rules: encArg(s(z0)) -> s(encArg(z0)) encArg(0) -> 0 encArg(n__from(z0)) -> n__from(encArg(z0)) encArg(true) -> true encArg(false) -> false encArg(divides(z0, z1)) -> divides(encArg(z0), encArg(z1)) encArg(n__filter(z0, z1)) -> n__filter(encArg(z0), encArg(z1)) encArg(n__cons(z0, z1)) -> n__cons(encArg(z0), encArg(z1)) encArg(cons_primes) -> primes encArg(cons_from(z0)) -> from(encArg(z0)) encArg(cons_head(z0)) -> head(encArg(z0)) encArg(cons_tail(z0)) -> tail(encArg(z0)) encArg(cons_if(z0, z1, z2)) -> if(encArg(z0), encArg(z1), encArg(z2)) encArg(cons_filter(z0, z1)) -> filter(encArg(z0), encArg(z1)) encArg(cons_sieve(z0)) -> sieve(encArg(z0)) encArg(cons_cons(z0, z1)) -> cons(encArg(z0), encArg(z1)) encArg(cons_activate(z0)) -> activate(encArg(z0)) primes -> sieve(from(s(s(0)))) from(z0) -> cons(z0, n__from(s(z0))) from(z0) -> n__from(z0) cons(z0, z1) -> n__cons(z0, z1) if(true, z0, z1) -> activate(z0) if(false, z0, z1) -> activate(z1) filter(z0, z1) -> n__filter(z0, z1) activate(n__from(z0)) -> from(z0) activate(n__filter(z0, z1)) -> filter(z0, z1) activate(n__cons(z0, z1)) -> cons(z0, z1) activate(z0) -> z0 Tuples: ENCARG(s(z0)) -> c(ENCARG(z0)) ENCARG(n__from(z0)) -> c2(ENCARG(z0)) ENCARG(divides(z0, z1)) -> c5(ENCARG(z0), ENCARG(z1)) ENCARG(n__filter(z0, z1)) -> c6(ENCARG(z0), ENCARG(z1)) ENCARG(n__cons(z0, z1)) -> c7(ENCARG(z0), ENCARG(z1)) ENCARG(cons_primes) -> c8(PRIMES) ENCARG(cons_from(z0)) -> c9(FROM(encArg(z0)), ENCARG(z0)) ENCARG(cons_if(z0, z1, z2)) -> c12(IF(encArg(z0), encArg(z1), encArg(z2)), ENCARG(z0), ENCARG(z1), ENCARG(z2)) ENCARG(cons_filter(z0, z1)) -> c13(FILTER(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_cons(z0, z1)) -> c15(CONS(encArg(z0), encArg(z1)), ENCARG(z0), ENCARG(z1)) ENCARG(cons_activate(z0)) -> c16(ACTIVATE(encArg(z0)), ENCARG(z0)) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) FILTER(z0, z1) -> c42 CONS(z0, z1) -> c44 ACTIVATE(n__from(z0)) -> c45(FROM(z0)) ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 ENCARG(cons_head(z0)) -> c10(ENCARG(z0)) ENCARG(cons_tail(z0)) -> c11(ENCARG(z0)) ENCARG(cons_sieve(z0)) -> c14(ENCARG(z0)) PRIMES -> c34(FROM(s(s(0)))) ENCODE_FROM(z0) -> c1(FROM(encArg(z0))) ENCODE_CONS(z0, z1) -> c1(CONS(encArg(z0), encArg(z1))) ENCODE_ACTIVATE(z0) -> c1(ACTIVATE(encArg(z0))) ENCODE_IF(z0, z1, z2) -> c1(IF(encArg(z0), encArg(z1), encArg(z2))) ENCODE_FILTER(z0, z1) -> c1(FILTER(encArg(z0), encArg(z1))) S tuples:none K tuples: IF(true, z0, z1) -> c39(ACTIVATE(z0)) IF(false, z0, z1) -> c40(ACTIVATE(z1)) PRIMES -> c34(FROM(s(s(0)))) FROM(z0) -> c35(CONS(z0, n__from(s(z0)))) FROM(z0) -> c36 FILTER(z0, z1) -> c42 ACTIVATE(n__cons(z0, z1)) -> c47(CONS(z0, z1)) ACTIVATE(z0) -> c48 CONS(z0, z1) -> c44 ACTIVATE(n__filter(z0, z1)) -> c46(FILTER(z0, z1)) ACTIVATE(n__from(z0)) -> c45(FROM(z0)) Defined Rule Symbols: encArg_1, primes, from_1, cons_2, if_3, filter_2, activate_1 Defined Pair Symbols: ENCARG_1, FROM_1, IF_3, FILTER_2, CONS_2, ACTIVATE_1, PRIMES, ENCODE_FROM_1, ENCODE_CONS_2, ENCODE_ACTIVATE_1, ENCODE_IF_3, ENCODE_FILTER_2 Compound Symbols: c_1, c2_1, c5_2, c6_2, c7_2, c8_1, c9_2, c12_4, c13_3, c15_3, c16_2, c35_1, c36, c39_1, c40_1, c42, c44, c45_1, c46_1, c47_1, c48, c10_1, c11_1, c14_1, c34_1, c1_1 ---------------------------------------- (27) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (28) BOUNDS(1, 1)