/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 28 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) QDPOrderProof [EQUIVALENT, 38 ms] (27) QDP (28) QDPOrderProof [EQUIVALENT, 0 ms] (29) QDP (30) QDPOrderProof [EQUIVALENT, 30 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) QDP (34) UsableRulesProof [EQUIVALENT, 0 ms] (35) QDP (36) QDPSizeChangeProof [EQUIVALENT, 0 ms] (37) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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(first(0, X)) -> MARK(nil) ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z)) ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z) ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) ACTIVE(from(X)) -> CONS(X, from(s(X))) ACTIVE(from(X)) -> FROM(s(X)) ACTIVE(from(X)) -> S(X) MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2)) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) MARK(0) -> ACTIVE(0) MARK(nil) -> ACTIVE(nil) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> S(mark(X)) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> CONS(mark(X1), X2) MARK(cons(X1, X2)) -> MARK(X1) MARK(from(X)) -> ACTIVE(from(mark(X))) MARK(from(X)) -> FROM(mark(X)) MARK(from(X)) -> MARK(X) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) S(mark(X)) -> S(X) S(active(X)) -> S(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) FROM(mark(X)) -> FROM(X) FROM(active(X)) -> FROM(X) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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 12 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: FROM(active(X)) -> FROM(X) FROM(mark(X)) -> FROM(X) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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: FROM(active(X)) -> FROM(X) FROM(mark(X)) -> FROM(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: *FROM(active(X)) -> FROM(X) The graph contains the following edges 1 > 1 *FROM(mark(X)) -> FROM(X) The graph contains the following edges 1 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) 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(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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: 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. ---------------------------------------- (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: *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 ---------------------------------------- (14) YES ---------------------------------------- (15) 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(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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: 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. ---------------------------------------- (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: *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 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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: FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) 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: *FIRST(X1, mark(X2)) -> FIRST(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *FIRST(mark(X1), X2) -> FIRST(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *FIRST(active(X1), X2) -> FIRST(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *FIRST(X1, active(X2)) -> FIRST(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> MARK(X1) MARK(from(X)) -> ACTIVE(from(mark(X))) MARK(from(X)) -> MARK(X) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. ACTIVE(x1) = x1 first(x1, x2) = first(x1, x2) s(x1) = x1 cons(x1, x2) = x1 MARK(x1) = x1 mark(x1) = x1 from(x1) = x1 active(x1) = x1 0 = 0 nil = nil Knuth-Bendix order [KBO] with precedence:trivial and weight map: 0=2 first_2=2 nil=4 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) 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) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) mark(0) -> active(0) mark(nil) -> active(nil) s(active(X)) -> s(X) s(mark(X)) -> s(X) from(active(X)) -> from(X) from(mark(X)) -> from(X) active(first(0, X)) -> mark(nil) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> MARK(X1) MARK(from(X)) -> ACTIVE(from(mark(X))) MARK(from(X)) -> MARK(X) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(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. MARK(s(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 first(x1, x2) = x2 ACTIVE(x1) = x1 mark(x1) = x1 from(x1) = x1 cons(x1, x2) = x1 s(x1) = s(x1) active(x1) = x1 0 = 0 nil = nil Knuth-Bendix order [KBO] with precedence:trivial and weight map: s_1=1 0=2 nil=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) mark(0) -> active(0) mark(nil) -> active(nil) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) from(active(X)) -> from(X) from(mark(X)) -> from(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) active(first(0, X)) -> mark(nil) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> MARK(X1) MARK(from(X)) -> ACTIVE(from(mark(X))) MARK(from(X)) -> MARK(X) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) MARK(from(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 first(x1, x2) = x2 ACTIVE(x1) = x1 mark(x1) = x1 from(x1) = from(x1) cons(x1, x2) = x1 s(x1) = s active(x1) = x1 0 = 0 nil = nil Knuth-Bendix order [KBO] with precedence:trivial and weight map: s=2 0=2 from_1=1 nil=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) mark(0) -> active(0) mark(nil) -> active(nil) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) from(active(X)) -> from(X) from(mark(X)) -> from(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) active(first(0, X)) -> mark(nil) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) MARK(cons(X1, X2)) -> MARK(X1) MARK(from(X)) -> ACTIVE(from(mark(X))) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(0) -> active(0) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(from(X)) -> active(from(mark(X))) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(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) from(mark(X)) -> from(X) from(active(X)) -> from(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) 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. ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> MARK(X1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) 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(cons(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 ---------------------------------------- (37) YES