/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES 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 proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] (9) YES (10) QDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) QDP (13) QDPSizeChangeProof [EQUIVALENT, 0 ms] (14) YES (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] (24) YES (25) QDP (26) MRRProof [EQUIVALENT, 48 ms] (27) QDP (28) QDPOrderProof [EQUIVALENT, 112 ms] (29) QDP (30) DependencyGraphProof [EQUIVALENT, 0 ms] (31) AND (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) QDPOrderProof [EQUIVALENT, 0 ms] (36) QDP (37) PisEmptyProof [EQUIVALENT, 0 ms] (38) YES (39) QDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) QDP (42) QDPSizeChangeProof [EQUIVALENT, 0 ms] (43) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(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: ACTIVE(f(0)) -> MARK(cons(0, f(s(0)))) ACTIVE(f(0)) -> CONS(0, f(s(0))) ACTIVE(f(0)) -> F(s(0)) ACTIVE(f(0)) -> S(0) ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) ACTIVE(f(s(0))) -> F(p(s(0))) ACTIVE(f(s(0))) -> P(s(0)) ACTIVE(p(s(0))) -> MARK(0) MARK(f(X)) -> ACTIVE(f(mark(X))) MARK(f(X)) -> F(mark(X)) MARK(f(X)) -> MARK(X) MARK(0) -> ACTIVE(0) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> CONS(mark(X1), X2) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> S(mark(X)) MARK(s(X)) -> MARK(X) MARK(p(X)) -> ACTIVE(p(mark(X))) MARK(p(X)) -> P(mark(X)) MARK(p(X)) -> MARK(X) F(mark(X)) -> F(X) F(active(X)) -> F(X) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) S(mark(X)) -> S(X) S(active(X)) -> S(X) P(mark(X)) -> P(X) P(active(X)) -> P(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(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 5 SCCs with 11 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: P(active(X)) -> P(X) P(mark(X)) -> P(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) 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. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: P(active(X)) -> P(X) P(mark(X)) -> P(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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: *P(active(X)) -> P(X) The graph contains the following edges 1 > 1 *P(mark(X)) -> P(X) The graph contains the following edges 1 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: S(active(X)) -> S(X) S(mark(X)) -> S(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: S(active(X)) -> S(X) S(mark(X)) -> S(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) 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: *S(active(X)) -> S(X) The graph contains the following edges 1 > 1 *S(mark(X)) -> S(X) The graph contains the following edges 1 > 1 ---------------------------------------- (14) YES ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) 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: *CONS(X1, mark(X2)) -> CONS(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *CONS(mark(X1), X2) -> CONS(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *CONS(active(X1), X2) -> CONS(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *CONS(X1, active(X2)) -> CONS(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: F(active(X)) -> F(X) F(mark(X)) -> F(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: F(active(X)) -> F(X) F(mark(X)) -> F(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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: *F(active(X)) -> F(X) The graph contains the following edges 1 > 1 *F(mark(X)) -> F(X) The graph contains the following edges 1 > 1 ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(f(0)) -> MARK(cons(0, f(s(0)))) MARK(cons(X1, X2)) -> MARK(X1) MARK(f(X)) -> ACTIVE(f(mark(X))) ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) MARK(f(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(p(X)) -> ACTIVE(p(mark(X))) MARK(p(X)) -> MARK(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: MARK(f(X)) -> MARK(X) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = x_1 POL(MARK(x_1)) = x_1 POL(active(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(f(x_1)) = 2 + 2*x_1 POL(mark(x_1)) = x_1 POL(p(x_1)) = x_1 POL(s(x_1)) = x_1 ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(f(0)) -> MARK(cons(0, f(s(0)))) MARK(cons(X1, X2)) -> MARK(X1) MARK(f(X)) -> ACTIVE(f(mark(X))) ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(p(X)) -> ACTIVE(p(mark(X))) MARK(p(X)) -> MARK(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(f(0)) -> MARK(cons(0, f(s(0)))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 cons(x1, x2) = x1 ACTIVE(x1) = x1 mark(x1) = x1 f(x1) = f 0 = 0 s(x1) = x1 p(x1) = x1 active(x1) = x1 Knuth-Bendix order [KBO] with precedence:f > 0 and weight map: 0=1 f=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) f(active(X)) -> f(X) f(mark(X)) -> f(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) p(active(X)) -> p(X) p(mark(X)) -> p(X) active(p(s(0))) -> mark(0) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> MARK(X1) MARK(f(X)) -> ACTIVE(f(mark(X))) ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(p(X)) -> ACTIVE(p(mark(X))) MARK(p(X)) -> MARK(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (31) Complex Obligation (AND) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) MARK(f(X)) -> ACTIVE(f(mark(X))) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule MARK(f(X)) -> ACTIVE(f(mark(X))) we obtained the following new rules [LPAR04]: (MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0))))),MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0))))) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(f(s(0))) -> MARK(f(p(s(0)))) MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0))))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. ACTIVE(x1) = x1 f(x1) = x1 s(x1) = s MARK(x1) = MARK p(x1) = p mark(x1) = x1 active(x1) = x1 cons(x1, x2) = cons 0 = 0 Knuth-Bendix order [KBO] with precedence:s > MARK > p > 0 > cons and weight map: s=1 0=1 p=1 cons=1 MARK=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(p(X)) -> active(p(mark(X))) f(active(X)) -> f(X) f(mark(X)) -> f(X) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) mark(f(X)) -> active(f(mark(X))) mark(s(X)) -> active(s(mark(X))) mark(0) -> active(0) s(active(X)) -> s(X) s(mark(X)) -> s(X) active(p(s(0))) -> mark(0) cons(X1, mark(X2)) -> cons(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) p(active(X)) -> p(X) p(mark(X)) -> p(X) ---------------------------------------- (36) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (38) YES ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(p(X)) -> MARK(X) The TRS R consists of the following rules: active(f(0)) -> mark(cons(0, f(s(0)))) active(f(s(0))) -> mark(f(p(s(0)))) active(p(s(0))) -> mark(0) mark(f(X)) -> active(f(mark(X))) mark(0) -> active(0) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(p(X)) -> active(p(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) p(mark(X)) -> p(X) p(active(X)) -> p(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) 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. ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(p(X)) -> MARK(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) 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: *MARK(s(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(cons(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(p(X)) -> MARK(X) The graph contains the following edges 1 > 1 ---------------------------------------- (43) YES