YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 74 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QReductionProof [EQUIVALENT, 0 ms] (25) QDP (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) QDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) QDP (38) QReductionProof [EQUIVALENT, 0 ms] (39) QDP (40) QDPSizeChangeProof [EQUIVALENT, 0 ms] (41) YES (42) QDP (43) UsableRulesProof [EQUIVALENT, 0 ms] (44) QDP (45) QReductionProof [EQUIVALENT, 0 ms] (46) QDP (47) QDPSizeChangeProof [EQUIVALENT, 0 ms] (48) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) active(h(X)) -> mark(c(d(X))) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(active(x_1)) = x_1 POL(c(x_1)) = x_1 POL(d(x_1)) = x_1 POL(f(x_1)) = x_1 POL(g(x_1)) = x_1 POL(h(x_1)) = 1 + x_1 POL(mark(x_1)) = x_1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(h(X)) -> mark(c(d(X))) ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(f(f(X))) -> MARK(c(f(g(f(X))))) ACTIVE(f(f(X))) -> C(f(g(f(X)))) ACTIVE(f(f(X))) -> F(g(f(X))) ACTIVE(f(f(X))) -> G(f(X)) ACTIVE(c(X)) -> MARK(d(X)) ACTIVE(c(X)) -> D(X) MARK(f(X)) -> ACTIVE(f(mark(X))) MARK(f(X)) -> F(mark(X)) MARK(f(X)) -> MARK(X) MARK(c(X)) -> ACTIVE(c(X)) MARK(g(X)) -> ACTIVE(g(X)) MARK(d(X)) -> ACTIVE(d(X)) MARK(h(X)) -> ACTIVE(h(mark(X))) MARK(h(X)) -> H(mark(X)) MARK(h(X)) -> MARK(X) F(mark(X)) -> F(X) F(active(X)) -> F(X) C(mark(X)) -> C(X) C(active(X)) -> C(X) G(mark(X)) -> G(X) G(active(X)) -> G(X) D(mark(X)) -> D(X) D(active(X)) -> D(X) H(mark(X)) -> H(X) H(active(X)) -> H(X) The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 13 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: H(active(X)) -> H(X) H(mark(X)) -> H(X) The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: H(active(X)) -> H(X) H(mark(X)) -> H(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: H(active(X)) -> H(X) H(mark(X)) -> H(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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: *H(active(X)) -> H(X) The graph contains the following edges 1 > 1 *H(mark(X)) -> H(X) The graph contains the following edges 1 > 1 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: D(active(X)) -> D(X) D(mark(X)) -> D(X) The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: D(active(X)) -> D(X) D(mark(X)) -> D(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: D(active(X)) -> D(X) D(mark(X)) -> D(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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: *D(active(X)) -> D(X) The graph contains the following edges 1 > 1 *D(mark(X)) -> D(X) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: G(active(X)) -> G(X) G(mark(X)) -> G(X) The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: G(active(X)) -> G(X) G(mark(X)) -> G(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: G(active(X)) -> G(X) G(mark(X)) -> G(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) 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: *G(active(X)) -> G(X) The graph contains the following edges 1 > 1 *G(mark(X)) -> G(X) The graph contains the following edges 1 > 1 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: C(active(X)) -> C(X) C(mark(X)) -> C(X) The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: C(active(X)) -> C(X) C(mark(X)) -> C(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: C(active(X)) -> C(X) C(mark(X)) -> C(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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: *C(active(X)) -> C(X) The graph contains the following edges 1 > 1 *C(mark(X)) -> C(X) The graph contains the following edges 1 > 1 ---------------------------------------- (34) YES ---------------------------------------- (35) 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(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (37) 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. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) ---------------------------------------- (39) 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. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) 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 ---------------------------------------- (41) YES ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(h(X)) -> MARK(X) MARK(f(X)) -> MARK(X) The TRS R consists of the following rules: active(f(f(X))) -> mark(c(f(g(f(X))))) active(c(X)) -> mark(d(X)) mark(f(X)) -> active(f(mark(X))) mark(c(X)) -> active(c(X)) mark(g(X)) -> active(g(X)) mark(d(X)) -> active(d(X)) mark(h(X)) -> active(h(mark(X))) f(mark(X)) -> f(X) f(active(X)) -> f(X) c(mark(X)) -> c(X) c(active(X)) -> c(X) g(mark(X)) -> g(X) g(active(X)) -> g(X) d(mark(X)) -> d(X) d(active(X)) -> d(X) h(mark(X)) -> h(X) h(active(X)) -> h(X) The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(h(X)) -> MARK(X) MARK(f(X)) -> MARK(X) R is empty. The set Q consists of the following terms: active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) f(mark(x0)) f(active(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. active(f(f(x0))) active(c(x0)) active(h(x0)) mark(f(x0)) mark(c(x0)) mark(g(x0)) mark(d(x0)) mark(h(x0)) c(mark(x0)) c(active(x0)) g(mark(x0)) g(active(x0)) d(mark(x0)) d(active(x0)) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(h(X)) -> MARK(X) MARK(f(X)) -> MARK(X) R is empty. The set Q consists of the following terms: f(mark(x0)) f(active(x0)) h(mark(x0)) h(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) 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(h(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(f(X)) -> MARK(X) The graph contains the following edges 1 > 1 ---------------------------------------- (48) YES