YES proof of /export/starexec/sandbox/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) DependencyPairsProof [EQUIVALENT, 46 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QReductionProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) QReductionProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES (19) QDP (20) UsableRulesProof [EQUIVALENT, 0 ms] (21) QDP (22) QReductionProof [EQUIVALENT, 0 ms] (23) QDP (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] (25) YES (26) QDP (27) UsableRulesProof [EQUIVALENT, 0 ms] (28) QDP (29) QReductionProof [EQUIVALENT, 0 ms] (30) QDP (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] (32) YES (33) QDP (34) UsableRulesProof [EQUIVALENT, 0 ms] (35) QDP (36) QReductionProof [EQUIVALENT, 0 ms] (37) QDP (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] (39) YES (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) QReductionProof [EQUIVALENT, 0 ms] (44) QDP (45) QDPSizeChangeProof [EQUIVALENT, 0 ms] (46) YES (47) QDP (48) UsableRulesProof [EQUIVALENT, 0 ms] (49) QDP (50) QReductionProof [EQUIVALENT, 0 ms] (51) QDP (52) QDPSizeChangeProof [EQUIVALENT, 0 ms] (53) YES (54) QDP (55) UsableRulesProof [EQUIVALENT, 0 ms] (56) QDP (57) QDPOrderProof [EQUIVALENT, 27 ms] (58) QDP (59) QDPOrderProof [EQUIVALENT, 0 ms] (60) QDP (61) DependencyGraphProof [EQUIVALENT, 0 ms] (62) QDP (63) UsableRulesProof [EQUIVALENT, 0 ms] (64) QDP (65) QReductionProof [EQUIVALENT, 0 ms] (66) QDP (67) QDPSizeChangeProof [EQUIVALENT, 0 ms] (68) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(and(true, X)) -> MARK(X) ACTIVE(and(false, Y)) -> MARK(false) ACTIVE(if(true, X, Y)) -> MARK(X) ACTIVE(if(false, X, Y)) -> MARK(Y) ACTIVE(add(0, X)) -> MARK(X) ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) ACTIVE(add(s(X), Y)) -> S(add(X, Y)) ACTIVE(add(s(X), Y)) -> ADD(X, Y) ACTIVE(first(0, X)) -> MARK(nil) ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z)) ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z) ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) ACTIVE(from(X)) -> CONS(X, from(s(X))) ACTIVE(from(X)) -> FROM(s(X)) ACTIVE(from(X)) -> S(X) MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) MARK(and(X1, X2)) -> AND(mark(X1), X2) MARK(and(X1, X2)) -> MARK(X1) MARK(true) -> ACTIVE(true) MARK(false) -> ACTIVE(false) MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) MARK(if(X1, X2, X3)) -> IF(mark(X1), X2, X3) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) MARK(add(X1, X2)) -> ADD(mark(X1), X2) MARK(add(X1, X2)) -> MARK(X1) MARK(0) -> ACTIVE(0) MARK(s(X)) -> ACTIVE(s(X)) MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2)) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) MARK(nil) -> ACTIVE(nil) MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) MARK(from(X)) -> ACTIVE(from(X)) AND(mark(X1), X2) -> AND(X1, X2) AND(X1, mark(X2)) -> AND(X1, X2) AND(active(X1), X2) -> AND(X1, X2) AND(X1, active(X2)) -> AND(X1, X2) IF(mark(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, mark(X2), X3) -> IF(X1, X2, X3) IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) IF(active(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, active(X2), X3) -> IF(X1, X2, X3) IF(X1, X2, active(X3)) -> IF(X1, X2, X3) ADD(mark(X1), X2) -> ADD(X1, X2) ADD(X1, mark(X2)) -> ADD(X1, X2) ADD(active(X1), X2) -> ADD(X1, X2) ADD(X1, active(X2)) -> ADD(X1, X2) S(mark(X)) -> S(X) S(active(X)) -> S(X) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) FROM(mark(X)) -> FROM(X) FROM(active(X)) -> FROM(X) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 8 SCCs with 23 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: FROM(active(X)) -> FROM(X) FROM(mark(X)) -> FROM(X) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) 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. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: FROM(active(X)) -> FROM(X) FROM(mark(X)) -> FROM(X) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: FROM(active(X)) -> FROM(X) FROM(mark(X)) -> FROM(X) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *FROM(active(X)) -> FROM(X) The graph contains the following edges 1 > 1 *FROM(mark(X)) -> FROM(X) The graph contains the following edges 1 > 1 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: CONS(X1, mark(X2)) -> CONS(X1, X2) CONS(mark(X1), X2) -> CONS(X1, X2) CONS(active(X1), X2) -> CONS(X1, X2) CONS(X1, active(X2)) -> CONS(X1, X2) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) 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. ---------------------------------------- (14) 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(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (16) 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(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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 ---------------------------------------- (18) YES ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) 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. ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: FIRST(X1, mark(X2)) -> FIRST(X1, X2) FIRST(mark(X1), X2) -> FIRST(X1, X2) FIRST(active(X1), X2) -> FIRST(X1, X2) FIRST(X1, active(X2)) -> FIRST(X1, X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) 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: *FIRST(X1, mark(X2)) -> FIRST(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *FIRST(mark(X1), X2) -> FIRST(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *FIRST(active(X1), X2) -> FIRST(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *FIRST(X1, active(X2)) -> FIRST(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (25) YES ---------------------------------------- (26) 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(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) 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. ---------------------------------------- (28) 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(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (30) 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(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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 ---------------------------------------- (32) YES ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: ADD(X1, mark(X2)) -> ADD(X1, X2) ADD(mark(X1), X2) -> ADD(X1, X2) ADD(active(X1), X2) -> ADD(X1, X2) ADD(X1, active(X2)) -> ADD(X1, X2) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) 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. ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: ADD(X1, mark(X2)) -> ADD(X1, X2) ADD(mark(X1), X2) -> ADD(X1, X2) ADD(active(X1), X2) -> ADD(X1, X2) ADD(X1, active(X2)) -> ADD(X1, X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: ADD(X1, mark(X2)) -> ADD(X1, X2) ADD(mark(X1), X2) -> ADD(X1, X2) ADD(active(X1), X2) -> ADD(X1, X2) ADD(X1, active(X2)) -> ADD(X1, X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) 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: *ADD(X1, mark(X2)) -> ADD(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *ADD(mark(X1), X2) -> ADD(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *ADD(active(X1), X2) -> ADD(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *ADD(X1, active(X2)) -> ADD(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (39) YES ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: IF(X1, mark(X2), X3) -> IF(X1, X2, X3) IF(mark(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) IF(active(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, active(X2), X3) -> IF(X1, X2, X3) IF(X1, X2, active(X3)) -> IF(X1, X2, X3) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) 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. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: IF(X1, mark(X2), X3) -> IF(X1, X2, X3) IF(mark(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) IF(active(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, active(X2), X3) -> IF(X1, X2, X3) IF(X1, X2, active(X3)) -> IF(X1, X2, X3) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: IF(X1, mark(X2), X3) -> IF(X1, X2, X3) IF(mark(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) IF(active(X1), X2, X3) -> IF(X1, X2, X3) IF(X1, active(X2), X3) -> IF(X1, X2, X3) IF(X1, X2, active(X3)) -> IF(X1, X2, X3) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) 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: *IF(X1, mark(X2), X3) -> IF(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *IF(mark(X1), X2, X3) -> IF(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *IF(X1, X2, mark(X3)) -> IF(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 *IF(active(X1), X2, X3) -> IF(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *IF(X1, active(X2), X3) -> IF(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *IF(X1, X2, active(X3)) -> IF(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (46) YES ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: AND(X1, mark(X2)) -> AND(X1, X2) AND(mark(X1), X2) -> AND(X1, X2) AND(active(X1), X2) -> AND(X1, X2) AND(X1, active(X2)) -> AND(X1, X2) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) 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. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: AND(X1, mark(X2)) -> AND(X1, X2) AND(mark(X1), X2) -> AND(X1, X2) AND(active(X1), X2) -> AND(X1, X2) AND(X1, active(X2)) -> AND(X1, X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) 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]. and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: AND(X1, mark(X2)) -> AND(X1, X2) AND(mark(X1), X2) -> AND(X1, X2) AND(active(X1), X2) -> AND(X1, X2) AND(X1, active(X2)) -> AND(X1, X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) 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: *AND(X1, mark(X2)) -> AND(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *AND(mark(X1), X2) -> AND(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *AND(active(X1), X2) -> AND(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *AND(X1, active(X2)) -> AND(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (53) YES ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) ACTIVE(and(true, X)) -> MARK(X) MARK(and(X1, X2)) -> MARK(X1) MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) ACTIVE(if(true, X, Y)) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) ACTIVE(if(false, X, Y)) -> MARK(Y) MARK(add(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) ACTIVE(add(0, X)) -> MARK(X) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(and(true, X)) -> mark(X) active(and(false, Y)) -> mark(false) active(if(true, X, Y)) -> mark(X) active(if(false, X, Y)) -> mark(Y) active(add(0, X)) -> mark(X) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) mark(and(X1, X2)) -> active(and(mark(X1), X2)) mark(true) -> active(true) mark(false) -> active(false) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) mark(add(X1, X2)) -> active(add(mark(X1), X2)) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(mark(X1), X2) -> and(X1, X2) and(X1, mark(X2)) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(mark(X1), X2) -> add(X1, X2) add(X1, mark(X2)) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) s(mark(X)) -> s(X) s(active(X)) -> s(X) first(mark(X1), X2) -> first(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) cons(mark(X1), X2) -> cons(X1, X2) cons(X1, mark(X2)) -> cons(X1, X2) cons(active(X1), X2) -> cons(X1, X2) cons(X1, active(X2)) -> cons(X1, X2) from(mark(X)) -> from(X) from(active(X)) -> from(X) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) 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. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) ACTIVE(and(true, X)) -> MARK(X) MARK(and(X1, X2)) -> MARK(X1) MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) ACTIVE(if(true, X, Y)) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) ACTIVE(if(false, X, Y)) -> MARK(Y) MARK(add(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) ACTIVE(add(0, X)) -> MARK(X) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: mark(and(X1, X2)) -> active(and(mark(X1), X2)) active(and(true, X)) -> mark(X) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) active(if(true, X, Y)) -> mark(X) mark(add(X1, X2)) -> active(add(mark(X1), X2)) active(if(false, X, Y)) -> mark(Y) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(add(0, X)) -> mark(X) mark(true) -> active(true) mark(false) -> active(false) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) active(from(X)) -> mark(cons(X, from(s(X)))) active(and(false, Y)) -> mark(false) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) and(X1, mark(X2)) -> and(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(X1, mark(X2)) -> add(X1, X2) add(mark(X1), X2) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(ACTIVE(x_1)) = x_1 POL(MARK(x_1)) = 1 POL(active(x_1)) = 0 POL(add(x_1, x_2)) = 1 POL(and(x_1, x_2)) = 1 POL(cons(x_1, x_2)) = x_1 POL(false) = 0 POL(first(x_1, x_2)) = 0 POL(from(x_1)) = x_1 POL(if(x_1, x_2, x_3)) = 1 POL(mark(x_1)) = 0 POL(nil) = 0 POL(s(x_1)) = 0 POL(true) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: and(X1, mark(X2)) -> and(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(X1, mark(X2)) -> add(X1, X2) add(mark(X1), X2) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) ACTIVE(and(true, X)) -> MARK(X) MARK(and(X1, X2)) -> MARK(X1) MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) ACTIVE(if(true, X, Y)) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) ACTIVE(if(false, X, Y)) -> MARK(Y) MARK(add(X1, X2)) -> MARK(X1) ACTIVE(add(0, X)) -> MARK(X) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: mark(and(X1, X2)) -> active(and(mark(X1), X2)) active(and(true, X)) -> mark(X) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) active(if(true, X, Y)) -> mark(X) mark(add(X1, X2)) -> active(add(mark(X1), X2)) active(if(false, X, Y)) -> mark(Y) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(add(0, X)) -> mark(X) mark(true) -> active(true) mark(false) -> active(false) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) active(from(X)) -> mark(cons(X, from(s(X)))) active(and(false, Y)) -> mark(false) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) and(X1, mark(X2)) -> and(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(X1, mark(X2)) -> add(X1, X2) add(mark(X1), X2) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(and(X1, X2)) -> ACTIVE(and(mark(X1), X2)) MARK(if(X1, X2, X3)) -> ACTIVE(if(mark(X1), X2, X3)) ACTIVE(if(true, X, Y)) -> MARK(X) MARK(if(X1, X2, X3)) -> MARK(X1) MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), X2)) ACTIVE(if(false, X, Y)) -> MARK(Y) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial interpretation [POLO]: POL(0) = 1 POL(ACTIVE(x_1)) = x_1 POL(MARK(x_1)) = 1 + x_1 POL(active(x_1)) = x_1 POL(add(x_1, x_2)) = x_1 + x_2 POL(and(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 POL(false) = 1 POL(first(x_1, x_2)) = x_1 + x_2 POL(from(x_1)) = x_1 POL(if(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(mark(x_1)) = x_1 POL(nil) = 0 POL(s(x_1)) = 0 POL(true) = 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(and(X1, X2)) -> active(and(mark(X1), X2)) active(and(true, X)) -> mark(X) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) active(if(true, X, Y)) -> mark(X) mark(add(X1, X2)) -> active(add(mark(X1), X2)) active(if(false, X, Y)) -> mark(Y) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(add(0, X)) -> mark(X) mark(true) -> active(true) mark(false) -> active(false) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) and(X1, mark(X2)) -> and(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(X1, mark(X2)) -> add(X1, X2) add(mark(X1), X2) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) active(and(false, Y)) -> mark(false) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) active(from(X)) -> mark(cons(X, from(s(X)))) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(and(true, X)) -> MARK(X) MARK(and(X1, X2)) -> MARK(X1) MARK(add(X1, X2)) -> MARK(X1) ACTIVE(add(0, X)) -> MARK(X) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: mark(and(X1, X2)) -> active(and(mark(X1), X2)) active(and(true, X)) -> mark(X) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) active(if(true, X, Y)) -> mark(X) mark(add(X1, X2)) -> active(add(mark(X1), X2)) active(if(false, X, Y)) -> mark(Y) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(add(0, X)) -> mark(X) mark(true) -> active(true) mark(false) -> active(false) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) active(from(X)) -> mark(cons(X, from(s(X)))) active(and(false, Y)) -> mark(false) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) and(X1, mark(X2)) -> and(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(X1, mark(X2)) -> add(X1, X2) add(mark(X1), X2) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(add(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: mark(and(X1, X2)) -> active(and(mark(X1), X2)) active(and(true, X)) -> mark(X) mark(if(X1, X2, X3)) -> active(if(mark(X1), X2, X3)) active(if(true, X, Y)) -> mark(X) mark(add(X1, X2)) -> active(add(mark(X1), X2)) active(if(false, X, Y)) -> mark(Y) mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) active(add(0, X)) -> mark(X) mark(true) -> active(true) mark(false) -> active(false) mark(0) -> active(0) mark(s(X)) -> active(s(X)) mark(nil) -> active(nil) mark(cons(X1, X2)) -> active(cons(X1, X2)) mark(from(X)) -> active(from(X)) first(X1, mark(X2)) -> first(X1, X2) first(mark(X1), X2) -> first(X1, X2) first(active(X1), X2) -> first(X1, X2) first(X1, active(X2)) -> first(X1, X2) active(from(X)) -> mark(cons(X, from(s(X)))) active(and(false, Y)) -> mark(false) active(add(s(X), Y)) -> mark(s(add(X, Y))) active(first(0, X)) -> mark(nil) active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) and(X1, mark(X2)) -> and(X1, X2) and(mark(X1), X2) -> and(X1, X2) and(active(X1), X2) -> and(X1, X2) and(X1, active(X2)) -> and(X1, X2) if(X1, mark(X2), X3) -> if(X1, X2, X3) if(mark(X1), X2, X3) -> if(X1, X2, X3) if(X1, X2, mark(X3)) -> if(X1, X2, X3) if(active(X1), X2, X3) -> if(X1, X2, X3) if(X1, active(X2), X3) -> if(X1, X2, X3) if(X1, X2, active(X3)) -> if(X1, X2, X3) add(X1, mark(X2)) -> add(X1, X2) add(mark(X1), X2) -> add(X1, X2) add(active(X1), X2) -> add(X1, X2) add(X1, active(X2)) -> add(X1, X2) The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) 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. ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(add(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) R is empty. The set Q consists of the following terms: active(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) s(mark(x0)) s(active(x0)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) 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(and(true, x0)) active(and(false, x0)) active(if(true, x0, x1)) active(if(false, x0, x1)) active(add(0, x0)) active(add(s(x0), x1)) active(first(0, x0)) active(first(s(x0), cons(x1, x2))) active(from(x0)) mark(and(x0, x1)) mark(true) mark(false) mark(if(x0, x1, x2)) mark(add(x0, x1)) mark(0) mark(s(x0)) mark(first(x0, x1)) mark(nil) mark(cons(x0, x1)) mark(from(x0)) if(mark(x0), x1, x2) if(x0, mark(x1), x2) if(x0, x1, mark(x2)) if(active(x0), x1, x2) if(x0, active(x1), x2) if(x0, x1, active(x2)) s(mark(x0)) s(active(x0)) cons(mark(x0), x1) cons(x0, mark(x1)) cons(active(x0), x1) cons(x0, active(x1)) from(mark(x0)) from(active(x0)) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(add(X1, X2)) -> MARK(X1) MARK(and(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X1) MARK(first(X1, X2)) -> MARK(X2) R is empty. The set Q consists of the following terms: and(mark(x0), x1) and(x0, mark(x1)) and(active(x0), x1) and(x0, active(x1)) add(mark(x0), x1) add(x0, mark(x1)) add(active(x0), x1) add(x0, active(x1)) first(mark(x0), x1) first(x0, mark(x1)) first(active(x0), x1) first(x0, active(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) 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(add(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(and(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(first(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(first(X1, X2)) -> MARK(X2) The graph contains the following edges 1 > 1 ---------------------------------------- (68) YES