/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSRRRProof [EQUIVALENT, 120 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 26 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 16 ms] (6) QTRS (7) DependencyPairsProof [EQUIVALENT, 5 ms] (8) QDP (9) DependencyGraphProof [EQUIVALENT, 0 ms] (10) AND (11) QDP (12) UsableRulesProof [EQUIVALENT, 0 ms] (13) QDP (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] (15) YES (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] (25) YES (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) QDPSizeChangeProof [EQUIVALENT, 0 ms] (30) YES (31) QDP (32) UsableRulesProof [EQUIVALENT, 0 ms] (33) QDP (34) QDPSizeChangeProof [EQUIVALENT, 0 ms] (35) YES (36) QDP (37) UsableRulesProof [EQUIVALENT, 0 ms] (38) QDP (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] (40) YES (41) QDP (42) MRRProof [EQUIVALENT, 29 ms] (43) QDP (44) MRRProof [EQUIVALENT, 39 ms] (45) QDP (46) MRRProof [EQUIVALENT, 30 ms] (47) QDP (48) TransformationProof [EQUIVALENT, 0 ms] (49) QDP (50) DependencyGraphProof [EQUIVALENT, 0 ms] (51) QDP (52) QDPOrderProof [EQUIVALENT, 108 ms] (53) QDP (54) QDPOrderProof [EQUIVALENT, 10 ms] (55) QDP (56) QDPOrderProof [EQUIVALENT, 0 ms] (57) QDP (58) PisEmptyProof [EQUIVALENT, 0 ms] (59) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(nats) -> mark(adx(zeros)) active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) active(hd(cons(X, Y))) -> mark(X) active(tl(cons(X, Y))) -> mark(Y) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(active(x_1)) = x_1 POL(adx(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(hd(x_1)) = 1 + x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(s(x_1)) = x_1 POL(tl(x_1)) = x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(hd(cons(X, Y))) -> mark(X) ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(nats) -> mark(adx(zeros)) active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) active(tl(cons(X, Y))) -> mark(Y) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. ---------------------------------------- (3) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(active(x_1)) = x_1 POL(adx(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + x_2 POL(hd(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(s(x_1)) = x_1 POL(tl(x_1)) = 2 + 2*x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(tl(cons(X, Y))) -> mark(Y) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(nats) -> mark(adx(zeros)) active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(active(x_1)) = x_1 POL(adx(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(hd(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 2 POL(s(x_1)) = x_1 POL(tl(x_1)) = x_1 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: active(nats) -> mark(adx(zeros)) ---------------------------------------- (6) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. ---------------------------------------- (7) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(zeros) -> MARK(cons(0, zeros)) ACTIVE(zeros) -> CONS(0, zeros) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) ACTIVE(incr(cons(X, Y))) -> CONS(s(X), incr(Y)) ACTIVE(incr(cons(X, Y))) -> S(X) ACTIVE(incr(cons(X, Y))) -> INCR(Y) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) ACTIVE(adx(cons(X, Y))) -> INCR(cons(X, adx(Y))) ACTIVE(adx(cons(X, Y))) -> CONS(X, adx(Y)) ACTIVE(adx(cons(X, Y))) -> ADX(Y) MARK(nats) -> ACTIVE(nats) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(adx(X)) -> ADX(mark(X)) MARK(adx(X)) -> MARK(X) MARK(zeros) -> ACTIVE(zeros) MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) MARK(0) -> ACTIVE(0) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> INCR(mark(X)) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(hd(X)) -> HD(mark(X)) MARK(hd(X)) -> MARK(X) MARK(tl(X)) -> ACTIVE(tl(mark(X))) MARK(tl(X)) -> TL(mark(X)) MARK(tl(X)) -> MARK(X) ADX(mark(X)) -> ADX(X) ADX(active(X)) -> ADX(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) INCR(mark(X)) -> INCR(X) INCR(active(X)) -> INCR(X) S(mark(X)) -> S(X) S(active(X)) -> S(X) HD(mark(X)) -> HD(X) HD(active(X)) -> HD(X) TL(mark(X)) -> TL(X) TL(active(X)) -> TL(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 13 less nodes. ---------------------------------------- (10) Complex Obligation (AND) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: TL(active(X)) -> TL(X) TL(mark(X)) -> TL(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: TL(active(X)) -> TL(X) TL(mark(X)) -> TL(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) 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: *TL(active(X)) -> TL(X) The graph contains the following edges 1 > 1 *TL(mark(X)) -> TL(X) The graph contains the following edges 1 > 1 ---------------------------------------- (15) YES ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: HD(active(X)) -> HD(X) HD(mark(X)) -> HD(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: HD(active(X)) -> HD(X) HD(mark(X)) -> HD(X) R is empty. Q is empty. 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: *HD(active(X)) -> HD(X) The graph contains the following edges 1 > 1 *HD(mark(X)) -> HD(X) The graph contains the following edges 1 > 1 ---------------------------------------- (20) YES ---------------------------------------- (21) 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(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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. ---------------------------------------- (23) 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. ---------------------------------------- (24) 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 ---------------------------------------- (25) YES ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: INCR(active(X)) -> INCR(X) INCR(mark(X)) -> INCR(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(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: INCR(active(X)) -> INCR(X) INCR(mark(X)) -> INCR(X) 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: *INCR(active(X)) -> INCR(X) The graph contains the following edges 1 > 1 *INCR(mark(X)) -> INCR(X) The graph contains the following edges 1 > 1 ---------------------------------------- (30) YES ---------------------------------------- (31) 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(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) 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. ---------------------------------------- (33) 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. ---------------------------------------- (34) 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 ---------------------------------------- (35) YES ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: ADX(active(X)) -> ADX(X) ADX(mark(X)) -> ADX(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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. ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: ADX(active(X)) -> ADX(X) ADX(mark(X)) -> ADX(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) 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: *ADX(active(X)) -> ADX(X) The graph contains the following edges 1 > 1 *ADX(mark(X)) -> ADX(X) The graph contains the following edges 1 > 1 ---------------------------------------- (40) YES ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(adx(X)) -> MARK(X) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(hd(X)) -> MARK(X) MARK(tl(X)) -> ACTIVE(tl(mark(X))) MARK(tl(X)) -> MARK(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) 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(hd(X)) -> MARK(X) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = 2*x_1 POL(MARK(x_1)) = 2*x_1 POL(active(x_1)) = x_1 POL(adx(x_1)) = x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(hd(x_1)) = 2 + 2*x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(s(x_1)) = x_1 POL(tl(x_1)) = x_1 POL(zeros) = 0 ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(adx(X)) -> MARK(X) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(tl(X)) -> ACTIVE(tl(mark(X))) MARK(tl(X)) -> MARK(X) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) 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(tl(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(adx(x_1)) = x_1 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(hd(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(s(x_1)) = x_1 POL(tl(x_1)) = 1 + x_1 POL(zeros) = 0 ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(adx(X)) -> MARK(X) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(tl(X)) -> ACTIVE(tl(mark(X))) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) 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(adx(X)) -> MARK(X) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = 2*x_1 POL(MARK(x_1)) = 2*x_1 POL(active(x_1)) = x_1 POL(adx(x_1)) = 1 + 2*x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(hd(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(s(x_1)) = x_1 POL(tl(x_1)) = x_1 POL(zeros) = 0 ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(tl(X)) -> ACTIVE(tl(mark(X))) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) at position [0] we obtained the following new rules [LPAR04]: (MARK(cons(mark(x0), x1)) -> ACTIVE(cons(x0, x1)),MARK(cons(mark(x0), x1)) -> ACTIVE(cons(x0, x1))) (MARK(cons(x0, mark(x1))) -> ACTIVE(cons(x0, x1)),MARK(cons(x0, mark(x1))) -> ACTIVE(cons(x0, x1))) (MARK(cons(active(x0), x1)) -> ACTIVE(cons(x0, x1)),MARK(cons(active(x0), x1)) -> ACTIVE(cons(x0, x1))) (MARK(cons(x0, active(x1))) -> ACTIVE(cons(x0, x1)),MARK(cons(x0, active(x1))) -> ACTIVE(cons(x0, x1))) ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(tl(X)) -> ACTIVE(tl(mark(X))) MARK(cons(mark(x0), x1)) -> ACTIVE(cons(x0, x1)) MARK(cons(x0, mark(x1))) -> ACTIVE(cons(x0, x1)) MARK(cons(active(x0), x1)) -> ACTIVE(cons(x0, x1)) MARK(cons(x0, active(x1))) -> ACTIVE(cons(x0, x1)) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(tl(X)) -> ACTIVE(tl(mark(X))) MARK(cons(mark(x0), x1)) -> ACTIVE(cons(x0, x1)) MARK(cons(x0, mark(x1))) -> ACTIVE(cons(x0, x1)) MARK(cons(active(x0), x1)) -> ACTIVE(cons(x0, x1)) MARK(cons(x0, active(x1))) -> ACTIVE(cons(x0, x1)) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(s(X)) -> ACTIVE(s(X)) MARK(hd(X)) -> ACTIVE(hd(mark(X))) MARK(cons(mark(x0), x1)) -> ACTIVE(cons(x0, x1)) MARK(cons(x0, mark(x1))) -> ACTIVE(cons(x0, x1)) MARK(cons(active(x0), x1)) -> ACTIVE(cons(x0, x1)) MARK(cons(x0, active(x1))) -> ACTIVE(cons(x0, x1)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( ACTIVE_1(x_1) ) = max{0, 2x_1 - 2} POL( adx_1(x_1) ) = 2 POL( hd_1(x_1) ) = 0 POL( incr_1(x_1) ) = 2 POL( tl_1(x_1) ) = 2 POL( mark_1(x_1) ) = max{0, -2} POL( nats ) = 0 POL( active_1(x_1) ) = max{0, -2} POL( cons_2(x_1, x_2) ) = 0 POL( zeros ) = 0 POL( 0 ) = 0 POL( s_1(x_1) ) = 0 POL( MARK_1(x_1) ) = 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: adx(active(X)) -> adx(X) adx(mark(X)) -> adx(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) incr(active(X)) -> incr(X) incr(mark(X)) -> incr(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) hd(active(X)) -> hd(X) hd(mark(X)) -> hd(X) tl(active(X)) -> tl(X) tl(mark(X)) -> tl(X) ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) MARK(incr(X)) -> MARK(X) MARK(tl(X)) -> ACTIVE(tl(mark(X))) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(adx(cons(X, Y))) -> MARK(incr(cons(X, adx(Y)))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 adx(x1) = adx ACTIVE(x1) = x1 incr(x1) = x1 cons(x1, x2) = cons mark(x1) = x1 tl(x1) = tl nats = nats active(x1) = x1 zeros = zeros s(x1) = s hd(x1) = hd 0 = 0 Knuth-Bendix order [KBO] with precedence:trivial and weight map: nats=1 s=2 hd=2 tl=2 zeros=3 0=2 cons=2 adx=3 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(nats) -> active(nats) mark(cons(X1, X2)) -> active(cons(X1, X2)) active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) mark(adx(X)) -> active(adx(mark(X))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(zeros) -> active(zeros) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) mark(0) -> active(0) adx(active(X)) -> adx(X) adx(mark(X)) -> adx(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) incr(active(X)) -> incr(X) incr(mark(X)) -> incr(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) tl(active(X)) -> tl(X) tl(mark(X)) -> tl(X) hd(active(X)) -> hd(X) hd(mark(X)) -> hd(X) ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(tl(X)) -> ACTIVE(tl(mark(X))) The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(adx(X)) -> ACTIVE(adx(mark(X))) ACTIVE(incr(cons(X, Y))) -> MARK(cons(s(X), incr(Y))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(tl(X)) -> ACTIVE(tl(mark(X))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 adx(x1) = adx ACTIVE(x1) = ACTIVE cons(x1, x2) = cons incr(x1) = incr(x1) tl(x1) = tl Knuth-Bendix order [KBO] with precedence:tl > ACTIVE > cons and weight map: ACTIVE=1 cons=1 tl=1 incr_1=1 adx=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 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) ---------------------------------------- (57) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(incr(cons(X, Y))) -> mark(cons(s(X), incr(Y))) active(adx(cons(X, Y))) -> mark(incr(cons(X, adx(Y)))) mark(nats) -> active(nats) mark(adx(X)) -> active(adx(mark(X))) mark(zeros) -> active(zeros) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(0) -> active(0) mark(incr(X)) -> active(incr(mark(X))) mark(s(X)) -> active(s(X)) mark(hd(X)) -> active(hd(mark(X))) mark(tl(X)) -> active(tl(mark(X))) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(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) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(X) s(mark(X)) -> s(X) s(active(X)) -> s(X) hd(mark(X)) -> hd(X) hd(active(X)) -> hd(X) tl(mark(X)) -> tl(X) tl(active(X)) -> tl(X) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (59) YES