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, 110 ms] (2) QTRS (3) QTRSRRRProof [EQUIVALENT, 29 ms] (4) QTRS (5) QTRSRRRProof [EQUIVALENT, 23 ms] (6) QTRS (7) DependencyPairsProof [EQUIVALENT, 1 ms] (8) QDP (9) DependencyGraphProof [EQUIVALENT, 0 ms] (10) AND (11) QDP (12) UsableRulesProof [EQUIVALENT, 0 ms] (13) QDP (14) QReductionProof [EQUIVALENT, 0 ms] (15) QDP (16) QDPSizeChangeProof [EQUIVALENT, 0 ms] (17) YES (18) QDP (19) UsableRulesProof [EQUIVALENT, 0 ms] (20) QDP (21) QReductionProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 2 ms] (24) YES (25) QDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) QDP (28) QReductionProof [EQUIVALENT, 0 ms] (29) QDP (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] (31) YES (32) QDP (33) UsableRulesProof [EQUIVALENT, 0 ms] (34) QDP (35) QReductionProof [EQUIVALENT, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES (39) QDP (40) UsableRulesProof [EQUIVALENT, 0 ms] (41) QDP (42) QReductionProof [EQUIVALENT, 0 ms] (43) QDP (44) QDPSizeChangeProof [EQUIVALENT, 0 ms] (45) YES (46) QDP (47) UsableRulesProof [EQUIVALENT, 0 ms] (48) QDP (49) QReductionProof [EQUIVALENT, 0 ms] (50) QDP (51) QDPSizeChangeProof [EQUIVALENT, 0 ms] (52) YES (53) QDP (54) MRRProof [EQUIVALENT, 40 ms] (55) QDP (56) MRRProof [EQUIVALENT, 61 ms] (57) QDP (58) MRRProof [EQUIVALENT, 46 ms] (59) QDP (60) QDPOrderProof [EQUIVALENT, 58 ms] (61) QDP (62) DependencyGraphProof [EQUIVALENT, 0 ms] (63) QDP (64) QDPOrderProof [EQUIVALENT, 27 ms] (65) QDP (66) QDPOrderProof [EQUIVALENT, 32 ms] (67) QDP (68) DependencyGraphProof [EQUIVALENT, 0 ms] (69) QDP (70) UsableRulesProof [EQUIVALENT, 0 ms] (71) QDP (72) QReductionProof [EQUIVALENT, 0 ms] (73) QDP (74) QDPSizeChangeProof [EQUIVALENT, 0 ms] (75) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(nil)) -> mark(nil) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(nats) -> mark(adx(zeros)) active(zeros) -> mark(cons(0, zeros)) active(head(cons(X, L))) -> mark(X) active(tail(cons(X, L))) -> mark(L) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (1) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(active(x_1)) = x_1 POL(adx(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(head(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(nil) = 2 POL(s(x_1)) = x_1 POL(tail(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(adx(nil)) -> mark(nil) ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(nats) -> mark(adx(zeros)) active(zeros) -> mark(cons(0, zeros)) active(head(cons(X, L))) -> mark(X) active(tail(cons(X, L))) -> mark(L) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (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)) = 2*x_1 + 2*x_2 POL(head(x_1)) = 1 + x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tail(x_1)) = 1 + 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(head(cons(X, L))) -> mark(X) active(tail(cons(X, L))) -> mark(L) ---------------------------------------- (4) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(nats) -> mark(adx(zeros)) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (5) QTRSRRRProof (EQUIVALENT) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(active(x_1)) = x_1 POL(adx(x_1)) = 2*x_1 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(head(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 2 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tail(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(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (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(incr(nil)) -> MARK(nil) ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) ACTIVE(incr(cons(X, L))) -> CONS(s(X), incr(L)) ACTIVE(incr(cons(X, L))) -> S(X) ACTIVE(incr(cons(X, L))) -> INCR(L) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) ACTIVE(adx(cons(X, L))) -> INCR(cons(X, adx(L))) ACTIVE(adx(cons(X, L))) -> CONS(X, adx(L)) ACTIVE(adx(cons(X, L))) -> ADX(L) ACTIVE(zeros) -> MARK(cons(0, zeros)) ACTIVE(zeros) -> CONS(0, zeros) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> INCR(mark(X)) MARK(incr(X)) -> MARK(X) MARK(nil) -> ACTIVE(nil) 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(adx(X)) -> ACTIVE(adx(mark(X))) MARK(adx(X)) -> ADX(mark(X)) MARK(adx(X)) -> MARK(X) MARK(nats) -> ACTIVE(nats) MARK(zeros) -> ACTIVE(zeros) MARK(0) -> ACTIVE(0) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(head(X)) -> HEAD(mark(X)) MARK(head(X)) -> MARK(X) MARK(tail(X)) -> ACTIVE(tail(mark(X))) MARK(tail(X)) -> TAIL(mark(X)) MARK(tail(X)) -> MARK(X) INCR(mark(X)) -> INCR(X) INCR(active(X)) -> INCR(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) ADX(mark(X)) -> ADX(X) ADX(active(X)) -> ADX(X) HEAD(mark(X)) -> HEAD(X) HEAD(active(X)) -> HEAD(X) TAIL(mark(X)) -> TAIL(X) TAIL(active(X)) -> TAIL(X) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) 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 17 less nodes. ---------------------------------------- (10) Complex Obligation (AND) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: TAIL(active(X)) -> TAIL(X) TAIL(mark(X)) -> TAIL(X) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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. ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: TAIL(active(X)) -> TAIL(X) TAIL(mark(X)) -> TAIL(X) R is empty. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) 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]. incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: TAIL(active(X)) -> TAIL(X) TAIL(mark(X)) -> TAIL(X) R is empty. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) 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: *TAIL(active(X)) -> TAIL(X) The graph contains the following edges 1 > 1 *TAIL(mark(X)) -> TAIL(X) The graph contains the following edges 1 > 1 ---------------------------------------- (17) YES ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: HEAD(active(X)) -> HEAD(X) HEAD(mark(X)) -> HEAD(X) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: HEAD(active(X)) -> HEAD(X) HEAD(mark(X)) -> HEAD(X) R is empty. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) 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]. incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: HEAD(active(X)) -> HEAD(X) HEAD(mark(X)) -> HEAD(X) R is empty. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) 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: *HEAD(active(X)) -> HEAD(X) The graph contains the following edges 1 > 1 *HEAD(mark(X)) -> HEAD(X) The graph contains the following edges 1 > 1 ---------------------------------------- (24) YES ---------------------------------------- (25) 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(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) 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. ---------------------------------------- (27) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) 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]. incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (29) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) 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 ---------------------------------------- (31) YES ---------------------------------------- (32) 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(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) 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. ---------------------------------------- (34) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) 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]. incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (36) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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 ---------------------------------------- (38) YES ---------------------------------------- (39) 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(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) 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. ---------------------------------------- (41) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) 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]. incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (43) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) 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 ---------------------------------------- (45) YES ---------------------------------------- (46) 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(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) 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. ---------------------------------------- (48) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) 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]. incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (50) 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. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) 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 ---------------------------------------- (52) YES ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(adx(X)) -> MARK(X) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(head(X)) -> MARK(X) MARK(tail(X)) -> ACTIVE(tail(mark(X))) MARK(tail(X)) -> MARK(X) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (54) 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(head(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)) = 2*x_1 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(head(x_1)) = 2 + x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tail(x_1)) = 2*x_1 POL(zeros) = 0 ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(adx(X)) -> MARK(X) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) MARK(tail(X)) -> MARK(X) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) 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)) = 2 + x_1 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(head(x_1)) = 2*x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tail(x_1)) = 2*x_1 POL(zeros) = 0 ---------------------------------------- (57) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) MARK(tail(X)) -> MARK(X) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (58) 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(tail(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 + 2*x_2 POL(head(x_1)) = x_1 POL(incr(x_1)) = x_1 POL(mark(x_1)) = x_1 POL(nats) = 0 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tail(x_1)) = 2 + 2*x_1 POL(zeros) = 0 ---------------------------------------- (59) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(zeros) -> ACTIVE(zeros) ACTIVE(zeros) -> MARK(cons(0, zeros)) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (60) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(zeros) -> MARK(cons(0, zeros)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. ACTIVE(x1) = x1 incr(x1) = x1 cons(x1, x2) = x1 MARK(x1) = x1 s(x1) = x1 mark(x1) = x1 adx(x1) = x1 zeros = zeros 0 = 0 head(x1) = head tail(x1) = tail active(x1) = x1 nil = nil nats = nats Knuth-Bendix order [KBO] with precedence:trivial and weight map: nats=1 tail=2 0=2 head=2 zeros=3 nil=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) mark(incr(X)) -> active(incr(mark(X))) active(zeros) -> mark(cons(0, zeros)) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(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) incr(active(X)) -> incr(X) incr(mark(X)) -> incr(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) adx(active(X)) -> adx(X) adx(mark(X)) -> adx(X) head(active(X)) -> head(X) head(mark(X)) -> head(X) tail(active(X)) -> tail(X) tail(mark(X)) -> tail(X) active(incr(nil)) -> mark(nil) ---------------------------------------- (61) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(zeros) -> ACTIVE(zeros) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (62) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> MARK(X1) MARK(incr(X)) -> ACTIVE(incr(mark(X))) ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(adx(cons(X, L))) -> MARK(incr(cons(X, adx(L)))) 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 incr(x1) = x1 s(x1) = x1 adx(x1) = adx(x1) head(x1) = head tail(x1) = tail active(x1) = x1 zeros = zeros 0 = 0 nil = nil nats = nats Knuth-Bendix order [KBO] with precedence:trivial and weight map: nats=1 tail=2 zeros=3 0=2 head=2 adx_1=1 nil=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) mark(incr(X)) -> active(incr(mark(X))) active(zeros) -> mark(cons(0, zeros)) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(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) incr(active(X)) -> incr(X) incr(mark(X)) -> incr(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) adx(active(X)) -> adx(X) adx(mark(X)) -> adx(X) head(active(X)) -> head(X) head(mark(X)) -> head(X) tail(active(X)) -> tail(X) tail(mark(X)) -> tail(X) active(incr(nil)) -> mark(nil) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(cons(X1, X2)) -> MARK(X1) MARK(incr(X)) -> ACTIVE(incr(mark(X))) MARK(incr(X)) -> MARK(X) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(incr(cons(X, L))) -> MARK(cons(s(X), incr(L))) MARK(incr(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 cons(x1, x2) = x1 ACTIVE(x1) = x1 mark(x1) = x1 incr(x1) = incr(x1) s(x1) = x1 adx(x1) = adx(x1) head(x1) = head tail(x1) = tail active(x1) = x1 zeros = zeros 0 = 0 nil = nil nats = nats Knuth-Bendix order [KBO] with precedence:trivial and weight map: nats=1 tail=2 zeros=3 0=2 head=2 incr_1=1 adx_1=2 nil=2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) mark(incr(X)) -> active(incr(mark(X))) active(zeros) -> mark(cons(0, zeros)) mark(nil) -> active(nil) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(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) incr(active(X)) -> incr(X) incr(mark(X)) -> incr(X) s(active(X)) -> s(X) s(mark(X)) -> s(X) adx(active(X)) -> adx(X) adx(mark(X)) -> adx(X) head(active(X)) -> head(X) head(mark(X)) -> head(X) tail(active(X)) -> tail(X) tail(mark(X)) -> tail(X) active(incr(nil)) -> mark(nil) ---------------------------------------- (67) 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(incr(X)) -> ACTIVE(incr(mark(X))) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> MARK(X) MARK(adx(X)) -> ACTIVE(adx(mark(X))) MARK(head(X)) -> ACTIVE(head(mark(X))) MARK(tail(X)) -> ACTIVE(tail(mark(X))) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 6 less nodes. ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) The TRS R consists of the following rules: active(incr(nil)) -> mark(nil) active(incr(cons(X, L))) -> mark(cons(s(X), incr(L))) active(adx(cons(X, L))) -> mark(incr(cons(X, adx(L)))) active(zeros) -> mark(cons(0, zeros)) mark(incr(X)) -> active(incr(mark(X))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) mark(s(X)) -> active(s(mark(X))) mark(adx(X)) -> active(adx(mark(X))) mark(nats) -> active(nats) mark(zeros) -> active(zeros) mark(0) -> active(0) mark(head(X)) -> active(head(mark(X))) mark(tail(X)) -> active(tail(mark(X))) incr(mark(X)) -> incr(X) incr(active(X)) -> incr(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) adx(mark(X)) -> adx(X) adx(active(X)) -> adx(X) head(mark(X)) -> head(X) head(active(X)) -> head(X) tail(mark(X)) -> tail(X) tail(active(X)) -> tail(X) The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) 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. ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) R is empty. The set Q consists of the following terms: active(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (72) 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(incr(nil)) active(incr(cons(x0, x1))) active(adx(nil)) active(adx(cons(x0, x1))) active(nats) active(zeros) active(head(cons(x0, x1))) active(tail(cons(x0, x1))) mark(incr(x0)) mark(nil) mark(cons(x0, x1)) mark(s(x0)) mark(adx(x0)) mark(nats) mark(zeros) mark(0) mark(head(x0)) mark(tail(x0)) incr(mark(x0)) incr(active(x0)) adx(mark(x0)) adx(active(x0)) head(mark(x0)) head(active(x0)) tail(mark(x0)) tail(active(x0)) ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(s(X)) -> MARK(X) MARK(cons(X1, X2)) -> MARK(X1) R is empty. The set Q consists of the following terms: cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) s(mark(x0)) s(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (74) 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 ---------------------------------------- (75) YES