/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- NO proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be disproven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 19 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 59 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) AND (9) QDP (10) TransformationProof [EQUIVALENT, 0 ms] (11) QDP (12) TransformationProof [EQUIVALENT, 0 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) QDP (16) TransformationProof [EQUIVALENT, 0 ms] (17) QDP (18) DependencyGraphProof [EQUIVALENT, 0 ms] (19) QDP (20) QDPOrderProof [EQUIVALENT, 0 ms] (21) QDP (22) QDPOrderProof [EQUIVALENT, 0 ms] (23) QDP (24) NonTerminationLoopProof [COMPLETE, 0 ms] (25) NO (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) QDPSizeChangeProof [EQUIVALENT, 0 ms] (30) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: 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 Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: PRIMES -> SIEVE(from(s(s(0)))) PRIMES -> FROM(s(s(0))) FROM(X) -> CONS(X, n__from(s(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)))) FILTER(s(s(X)), cons(Y, Z)) -> ACTIVATE(Z) FILTER(s(s(X)), cons(Y, Z)) -> SIEVE(Y) SIEVE(cons(X, Y)) -> CONS(X, n__filter(X, sieve(activate(Y)))) SIEVE(cons(X, Y)) -> SIEVE(activate(Y)) SIEVE(cons(X, Y)) -> ACTIVATE(Y) ACTIVATE(n__from(X)) -> FROM(X) ACTIVATE(n__filter(X1, X2)) -> FILTER(X1, X2) ACTIVATE(n__cons(X1, X2)) -> CONS(X1, X2) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 10 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__filter(X1, X2)) -> FILTER(X1, X2) FILTER(s(s(X)), cons(Y, Z)) -> ACTIVATE(Z) FILTER(s(s(X)), cons(Y, Z)) -> SIEVE(Y) SIEVE(cons(X, Y)) -> SIEVE(activate(Y)) SIEVE(cons(X, Y)) -> ACTIVATE(Y) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SIEVE(cons(X, Y)) -> ACTIVATE(Y) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( SIEVE_1(x_1) ) = x_1 + 2 POL( activate_1(x_1) ) = x_1 + 1 POL( n__from_1(x_1) ) = 2x_1 POL( from_1(x_1) ) = 2x_1 + 1 POL( n__filter_2(x_1, x_2) ) = max{0, x_2 - 1} POL( filter_2(x_1, x_2) ) = x_2 POL( n__cons_2(x_1, x_2) ) = x_1 + 2x_2 POL( cons_2(x_1, x_2) ) = x_1 + 2x_2 + 1 POL( s_1(x_1) ) = 0 POL( if_3(x_1, ..., x_3) ) = max{0, -2} POL( divides_2(x_1, x_2) ) = max{0, 2x_2 - 2} POL( sieve_1(x_1) ) = max{0, 2x_1 - 1} POL( ACTIVATE_1(x_1) ) = 2x_1 + 2 POL( FILTER_2(x_1, x_2) ) = 2x_2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 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 filter(X1, X2) -> n__filter(X1, X2) 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)))) cons(X1, X2) -> n__cons(X1, X2) from(X) -> cons(X, n__from(s(X))) from(X) -> n__from(X) ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVATE(n__filter(X1, X2)) -> FILTER(X1, X2) FILTER(s(s(X)), cons(Y, Z)) -> ACTIVATE(Z) FILTER(s(s(X)), cons(Y, Z)) -> SIEVE(Y) SIEVE(cons(X, Y)) -> SIEVE(activate(Y)) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (8) Complex Obligation (AND) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(X, Y)) -> SIEVE(activate(Y)) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule SIEVE(cons(X, Y)) -> SIEVE(activate(Y)) at position [0] we obtained the following new rules [LPAR04]: (SIEVE(cons(y0, n__from(x0))) -> SIEVE(from(x0)),SIEVE(cons(y0, n__from(x0))) -> SIEVE(from(x0))) (SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(filter(x0, x1)),SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(filter(x0, x1))) (SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)),SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1))) (SIEVE(cons(y0, x0)) -> SIEVE(x0),SIEVE(cons(y0, x0)) -> SIEVE(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__from(x0))) -> SIEVE(from(x0)) SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(filter(x0, x1)) SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) SIEVE(cons(y0, x0)) -> SIEVE(x0) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule SIEVE(cons(y0, n__from(x0))) -> SIEVE(from(x0)) at position [0] we obtained the following new rules [LPAR04]: (SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))),SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0))))) (SIEVE(cons(y0, n__from(x0))) -> SIEVE(n__from(x0)),SIEVE(cons(y0, n__from(x0))) -> SIEVE(n__from(x0))) ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(filter(x0, x1)) SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) SIEVE(cons(y0, x0)) -> SIEVE(x0) SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))) SIEVE(cons(y0, n__from(x0))) -> SIEVE(n__from(x0)) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(filter(x0, x1)) SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) SIEVE(cons(y0, x0)) -> SIEVE(x0) SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(filter(x0, x1)) at position [0] we obtained the following new rules [LPAR04]: (SIEVE(cons(y0, n__filter(s(s(x0)), cons(x1, x2)))) -> SIEVE(if(divides(s(s(x0)), x1), n__filter(s(s(x0)), activate(x2)), n__cons(x1, n__filter(x0, sieve(x1))))),SIEVE(cons(y0, n__filter(s(s(x0)), cons(x1, x2)))) -> SIEVE(if(divides(s(s(x0)), x1), n__filter(s(s(x0)), activate(x2)), n__cons(x1, n__filter(x0, sieve(x1)))))) (SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(n__filter(x0, x1)),SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(n__filter(x0, x1))) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) SIEVE(cons(y0, x0)) -> SIEVE(x0) SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))) SIEVE(cons(y0, n__filter(s(s(x0)), cons(x1, x2)))) -> SIEVE(if(divides(s(s(x0)), x1), n__filter(s(s(x0)), activate(x2)), n__cons(x1, n__filter(x0, sieve(x1))))) SIEVE(cons(y0, n__filter(x0, x1))) -> SIEVE(n__filter(x0, x1)) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) SIEVE(cons(y0, x0)) -> SIEVE(x0) SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SIEVE(cons(y0, x0)) -> SIEVE(x0) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. SIEVE(x1) = x1 cons(x1, x2) = cons(x2) n__cons(x1, x2) = x2 n__from(x1) = n__from Knuth-Bendix order [KBO] with precedence:trivial and weight map: cons_1=1 n__from=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: cons(X1, X2) -> n__cons(X1, X2) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. SIEVE(cons(y0, n__cons(x0, x1))) -> SIEVE(cons(x0, x1)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. SIEVE(x1) = x1 cons(x1, x2) = cons(x2) n__cons(x1, x2) = n__cons(x2) n__from(x1) = n__from Knuth-Bendix order [KBO] with precedence:trivial and weight map: cons_1=2 n__from=1 n__cons_1=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: cons(X1, X2) -> n__cons(X1, X2) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: SIEVE(cons(y0, n__from(x0))) -> SIEVE(cons(x0, n__from(s(x0)))) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) NonTerminationLoopProof (COMPLETE) We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. Found a loop by semiunifying a rule from P directly. s = SIEVE(cons(y0, n__from(x0))) evaluates to t =SIEVE(cons(x0, n__from(s(x0)))) Thus s starts an infinite chain as s semiunifies with t with the following substitutions: * Matcher: [y0 / x0, x0 / s(x0)] * Semiunifier: [ ] -------------------------------------------------------------------------------- Rewriting sequence The DP semiunifies directly so there is only one rewrite step from SIEVE(cons(y0, n__from(x0))) to SIEVE(cons(x0, n__from(s(x0)))). ---------------------------------------- (25) NO ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: FILTER(s(s(X)), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__filter(X1, X2)) -> FILTER(X1, X2) 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 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: FILTER(s(s(X)), cons(Y, Z)) -> ACTIVATE(Z) ACTIVATE(n__filter(X1, X2)) -> FILTER(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ACTIVATE(n__filter(X1, X2)) -> FILTER(X1, X2) The graph contains the following edges 1 > 1, 1 > 2 *FILTER(s(s(X)), cons(Y, Z)) -> ACTIVATE(Z) The graph contains the following edges 2 > 1 ---------------------------------------- (30) YES