/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 16 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) QDPSizeChangeProof [EQUIVALENT, 0 ms] (9) YES (10) QDP (11) UsableRulesProof [EQUIVALENT, 0 ms] (12) QDP (13) QDPSizeChangeProof [EQUIVALENT, 0 ms] (14) YES (15) QDP (16) UsableRulesProof [EQUIVALENT, 0 ms] (17) QDP (18) QDPSizeChangeProof [EQUIVALENT, 0 ms] (19) YES (20) QDP (21) UsableRulesProof [EQUIVALENT, 0 ms] (22) QDP (23) QDPSizeChangeProof [EQUIVALENT, 0 ms] (24) YES (25) QDP (26) UsableRulesProof [EQUIVALENT, 0 ms] (27) QDP (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] (29) YES (30) QDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) QDP (33) QDPSizeChangeProof [EQUIVALENT, 0 ms] (34) YES (35) QDP (36) UsableRulesProof [EQUIVALENT, 0 ms] (37) QDP (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] (39) YES (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) QDPSizeChangeProof [EQUIVALENT, 0 ms] (44) YES (45) QDP (46) UsableRulesProof [EQUIVALENT, 0 ms] (47) QDP (48) QDPSizeChangeProof [EQUIVALENT, 0 ms] (49) YES (50) QDP (51) QDPOrderProof [EQUIVALENT, 49 ms] (52) QDP (53) QDPOrderProof [EQUIVALENT, 54 ms] (54) QDP (55) QDPOrderProof [EQUIVALENT, 0 ms] (56) QDP (57) QDPOrderProof [EQUIVALENT, 43 ms] (58) QDP (59) QDPOrderProof [EQUIVALENT, 43 ms] (60) QDP (61) QDPOrderProof [EQUIVALENT, 193 ms] (62) QDP (63) QDPOrderProof [EQUIVALENT, 146 ms] (64) QDP (65) QDPOrderProof [EQUIVALENT, 253 ms] (66) QDP (67) QDPOrderProof [EQUIVALENT, 129 ms] (68) QDP (69) DependencyGraphProof [EQUIVALENT, 0 ms] (70) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) ACTIVE(U11(tt, V2)) -> U12^1(isNat(V2)) ACTIVE(U11(tt, V2)) -> ISNAT(V2) ACTIVE(U12(tt)) -> MARK(tt) ACTIVE(U21(tt)) -> MARK(tt) ACTIVE(U31(tt, N)) -> MARK(N) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U41(tt, M, N)) -> U42^1(isNat(N), M, N) ACTIVE(U41(tt, M, N)) -> ISNAT(N) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) ACTIVE(U42(tt, M, N)) -> S(plus(N, M)) ACTIVE(U42(tt, M, N)) -> PLUS(N, M) ACTIVE(isNat(0)) -> MARK(tt) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) ACTIVE(isNat(plus(V1, V2))) -> U11^1(isNat(V1), V2) ACTIVE(isNat(plus(V1, V2))) -> ISNAT(V1) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) ACTIVE(isNat(s(V1))) -> U21^1(isNat(V1)) ACTIVE(isNat(s(V1))) -> ISNAT(V1) ACTIVE(plus(N, 0)) -> MARK(U31(isNat(N), N)) ACTIVE(plus(N, 0)) -> U31^1(isNat(N), N) ACTIVE(plus(N, 0)) -> ISNAT(N) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) ACTIVE(plus(N, s(M))) -> U41^1(isNat(M), M, N) ACTIVE(plus(N, s(M))) -> ISNAT(M) MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) MARK(U11(X1, X2)) -> U11^1(mark(X1), X2) MARK(U11(X1, X2)) -> MARK(X1) MARK(tt) -> ACTIVE(tt) MARK(U12(X)) -> ACTIVE(U12(mark(X))) MARK(U12(X)) -> U12^1(mark(X)) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) MARK(U21(X)) -> ACTIVE(U21(mark(X))) MARK(U21(X)) -> U21^1(mark(X)) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> ACTIVE(U31(mark(X1), X2)) MARK(U31(X1, X2)) -> U31^1(mark(X1), X2) MARK(U31(X1, X2)) -> MARK(X1) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) MARK(U41(X1, X2, X3)) -> U41^1(mark(X1), X2, X3) MARK(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) MARK(U42(X1, X2, X3)) -> U42^1(mark(X1), X2, X3) MARK(U42(X1, X2, X3)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) MARK(s(X)) -> S(mark(X)) MARK(s(X)) -> MARK(X) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(0) -> ACTIVE(0) U11^1(mark(X1), X2) -> U11^1(X1, X2) U11^1(X1, mark(X2)) -> U11^1(X1, X2) U11^1(active(X1), X2) -> U11^1(X1, X2) U11^1(X1, active(X2)) -> U11^1(X1, X2) U12^1(mark(X)) -> U12^1(X) U12^1(active(X)) -> U12^1(X) ISNAT(mark(X)) -> ISNAT(X) ISNAT(active(X)) -> ISNAT(X) U21^1(mark(X)) -> U21^1(X) U21^1(active(X)) -> U21^1(X) U31^1(mark(X1), X2) -> U31^1(X1, X2) U31^1(X1, mark(X2)) -> U31^1(X1, X2) U31^1(active(X1), X2) -> U31^1(X1, X2) U31^1(X1, active(X2)) -> U31^1(X1, X2) U41^1(mark(X1), X2, X3) -> U41^1(X1, X2, X3) U41^1(X1, mark(X2), X3) -> U41^1(X1, X2, X3) U41^1(X1, X2, mark(X3)) -> U41^1(X1, X2, X3) U41^1(active(X1), X2, X3) -> U41^1(X1, X2, X3) U41^1(X1, active(X2), X3) -> U41^1(X1, X2, X3) U41^1(X1, X2, active(X3)) -> U41^1(X1, X2, X3) U42^1(mark(X1), X2, X3) -> U42^1(X1, X2, X3) U42^1(X1, mark(X2), X3) -> U42^1(X1, X2, X3) U42^1(X1, X2, mark(X3)) -> U42^1(X1, X2, X3) U42^1(active(X1), X2, X3) -> U42^1(X1, X2, X3) U42^1(X1, active(X2), X3) -> U42^1(X1, X2, X3) U42^1(X1, X2, active(X3)) -> U42^1(X1, X2, X3) S(mark(X)) -> S(X) S(active(X)) -> S(X) PLUS(mark(X1), X2) -> PLUS(X1, X2) PLUS(X1, mark(X2)) -> PLUS(X1, X2) PLUS(active(X1), X2) -> PLUS(X1, X2) PLUS(X1, active(X2)) -> PLUS(X1, X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 10 SCCs with 27 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(X1, mark(X2)) -> PLUS(X1, X2) PLUS(mark(X1), X2) -> PLUS(X1, X2) PLUS(active(X1), X2) -> PLUS(X1, X2) PLUS(X1, active(X2)) -> PLUS(X1, X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(X1, mark(X2)) -> PLUS(X1, X2) PLUS(mark(X1), X2) -> PLUS(X1, X2) PLUS(active(X1), X2) -> PLUS(X1, X2) PLUS(X1, active(X2)) -> PLUS(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *PLUS(X1, mark(X2)) -> PLUS(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *PLUS(mark(X1), X2) -> PLUS(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *PLUS(active(X1), X2) -> PLUS(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *PLUS(X1, active(X2)) -> PLUS(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (9) YES ---------------------------------------- (10) 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(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: S(active(X)) -> S(X) S(mark(X)) -> S(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *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 ---------------------------------------- (14) YES ---------------------------------------- (15) Obligation: Q DP problem: The TRS P consists of the following rules: U42^1(X1, mark(X2), X3) -> U42^1(X1, X2, X3) U42^1(mark(X1), X2, X3) -> U42^1(X1, X2, X3) U42^1(X1, X2, mark(X3)) -> U42^1(X1, X2, X3) U42^1(active(X1), X2, X3) -> U42^1(X1, X2, X3) U42^1(X1, active(X2), X3) -> U42^1(X1, X2, X3) U42^1(X1, X2, active(X3)) -> U42^1(X1, X2, X3) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (16) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: U42^1(X1, mark(X2), X3) -> U42^1(X1, X2, X3) U42^1(mark(X1), X2, X3) -> U42^1(X1, X2, X3) U42^1(X1, X2, mark(X3)) -> U42^1(X1, X2, X3) U42^1(active(X1), X2, X3) -> U42^1(X1, X2, X3) U42^1(X1, active(X2), X3) -> U42^1(X1, X2, X3) U42^1(X1, X2, active(X3)) -> U42^1(X1, X2, X3) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *U42^1(X1, mark(X2), X3) -> U42^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *U42^1(mark(X1), X2, X3) -> U42^1(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *U42^1(X1, X2, mark(X3)) -> U42^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 *U42^1(active(X1), X2, X3) -> U42^1(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *U42^1(X1, active(X2), X3) -> U42^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *U42^1(X1, X2, active(X3)) -> U42^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (19) YES ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: U41^1(X1, mark(X2), X3) -> U41^1(X1, X2, X3) U41^1(mark(X1), X2, X3) -> U41^1(X1, X2, X3) U41^1(X1, X2, mark(X3)) -> U41^1(X1, X2, X3) U41^1(active(X1), X2, X3) -> U41^1(X1, X2, X3) U41^1(X1, active(X2), X3) -> U41^1(X1, X2, X3) U41^1(X1, X2, active(X3)) -> U41^1(X1, X2, X3) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: U41^1(X1, mark(X2), X3) -> U41^1(X1, X2, X3) U41^1(mark(X1), X2, X3) -> U41^1(X1, X2, X3) U41^1(X1, X2, mark(X3)) -> U41^1(X1, X2, X3) U41^1(active(X1), X2, X3) -> U41^1(X1, X2, X3) U41^1(X1, active(X2), X3) -> U41^1(X1, X2, X3) U41^1(X1, X2, active(X3)) -> U41^1(X1, X2, X3) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *U41^1(X1, mark(X2), X3) -> U41^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *U41^1(mark(X1), X2, X3) -> U41^1(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *U41^1(X1, X2, mark(X3)) -> U41^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 *U41^1(active(X1), X2, X3) -> U41^1(X1, X2, X3) The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3 *U41^1(X1, active(X2), X3) -> U41^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *U41^1(X1, X2, active(X3)) -> U41^1(X1, X2, X3) The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3 ---------------------------------------- (24) YES ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U31^1(X1, mark(X2)) -> U31^1(X1, X2) U31^1(mark(X1), X2) -> U31^1(X1, X2) U31^1(active(X1), X2) -> U31^1(X1, X2) U31^1(X1, active(X2)) -> U31^1(X1, X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U31^1(X1, mark(X2)) -> U31^1(X1, X2) U31^1(mark(X1), X2) -> U31^1(X1, X2) U31^1(active(X1), X2) -> U31^1(X1, X2) U31^1(X1, active(X2)) -> U31^1(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) 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: *U31^1(X1, mark(X2)) -> U31^1(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *U31^1(mark(X1), X2) -> U31^1(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *U31^1(active(X1), X2) -> U31^1(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *U31^1(X1, active(X2)) -> U31^1(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: U21^1(active(X)) -> U21^1(X) U21^1(mark(X)) -> U21^1(X) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U21^1(active(X)) -> U21^1(X) U21^1(mark(X)) -> U21^1(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *U21^1(active(X)) -> U21^1(X) The graph contains the following edges 1 > 1 *U21^1(mark(X)) -> U21^1(X) The graph contains the following edges 1 > 1 ---------------------------------------- (34) YES ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: ISNAT(active(X)) -> ISNAT(X) ISNAT(mark(X)) -> ISNAT(X) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: ISNAT(active(X)) -> ISNAT(X) ISNAT(mark(X)) -> ISNAT(X) R is empty. Q is empty. 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: *ISNAT(active(X)) -> ISNAT(X) The graph contains the following edges 1 > 1 *ISNAT(mark(X)) -> ISNAT(X) The graph contains the following edges 1 > 1 ---------------------------------------- (39) YES ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(active(X)) -> U12^1(X) U12^1(mark(X)) -> U12^1(X) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: U12^1(active(X)) -> U12^1(X) U12^1(mark(X)) -> U12^1(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) 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: *U12^1(active(X)) -> U12^1(X) The graph contains the following edges 1 > 1 *U12^1(mark(X)) -> U12^1(X) The graph contains the following edges 1 > 1 ---------------------------------------- (44) YES ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(X1, mark(X2)) -> U11^1(X1, X2) U11^1(mark(X1), X2) -> U11^1(X1, X2) U11^1(active(X1), X2) -> U11^1(X1, X2) U11^1(X1, active(X2)) -> U11^1(X1, X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(X1, mark(X2)) -> U11^1(X1, X2) U11^1(mark(X1), X2) -> U11^1(X1, X2) U11^1(active(X1), X2) -> U11^1(X1, X2) U11^1(X1, active(X2)) -> U11^1(X1, X2) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) 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: *U11^1(X1, mark(X2)) -> U11^1(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 *U11^1(mark(X1), X2) -> U11^1(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *U11^1(active(X1), X2) -> U11^1(X1, X2) The graph contains the following edges 1 > 1, 2 >= 2 *U11^1(X1, active(X2)) -> U11^1(X1, X2) The graph contains the following edges 1 >= 1, 2 > 2 ---------------------------------------- (49) YES ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> ACTIVE(U12(mark(X))) ACTIVE(U31(tt, N)) -> MARK(N) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) MARK(U21(X)) -> ACTIVE(U21(mark(X))) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> ACTIVE(U31(mark(X1), X2)) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U31(X1, X2)) -> MARK(X1) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) ACTIVE(plus(N, 0)) -> MARK(U31(isNat(N), N)) MARK(U42(X1, X2, X3)) -> MARK(X1) MARK(s(X)) -> ACTIVE(s(mark(X))) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) MARK(s(X)) -> MARK(X) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U12(X)) -> ACTIVE(U12(mark(X))) MARK(U21(X)) -> ACTIVE(U21(mark(X))) MARK(s(X)) -> ACTIVE(s(mark(X))) 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(U11(x_1, x_2)) = 1 POL(U12(x_1)) = 0 POL(U21(x_1)) = 0 POL(U31(x_1, x_2)) = 1 POL(U41(x_1, x_2, x_3)) = 1 POL(U42(x_1, x_2, x_3)) = 1 POL(active(x_1)) = 0 POL(isNat(x_1)) = 1 POL(mark(x_1)) = 0 POL(plus(x_1, x_2)) = 1 POL(s(x_1)) = 0 POL(tt) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) plus(X1, mark(X2)) -> plus(X1, X2) plus(mark(X1), X2) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) U31(X1, mark(X2)) -> U31(X1, X2) U31(mark(X1), X2) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) ACTIVE(U31(tt, N)) -> MARK(N) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> ACTIVE(U31(mark(X1), X2)) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U31(X1, X2)) -> MARK(X1) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) ACTIVE(plus(N, 0)) -> MARK(U31(isNat(N), N)) MARK(U42(X1, X2, X3)) -> MARK(X1) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) MARK(s(X)) -> MARK(X) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(plus(N, 0)) -> MARK(U31(isNat(N), N)) 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)) = x_1 POL(U11(x_1, x_2)) = x_1 POL(U12(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(active(x_1)) = x_1 POL(isNat(x_1)) = 0 POL(mark(x_1)) = x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(tt) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) active(U11(tt, V2)) -> mark(U12(isNat(V2))) mark(U12(X)) -> active(U12(mark(X))) active(U31(tt, N)) -> mark(N) mark(isNat(X)) -> active(isNat(X)) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) mark(U21(X)) -> active(U21(mark(X))) active(U42(tt, M, N)) -> mark(s(plus(N, M))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) active(plus(N, 0)) -> mark(U31(isNat(N), N)) mark(s(X)) -> active(s(mark(X))) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(tt) -> active(tt) mark(0) -> active(0) U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) plus(X1, mark(X2)) -> plus(X1, X2) plus(mark(X1), X2) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) U31(X1, mark(X2)) -> U31(X1, X2) U31(mark(X1), X2) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(isNat(0)) -> mark(tt) ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) ACTIVE(U31(tt, N)) -> MARK(N) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> ACTIVE(U31(mark(X1), X2)) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U31(X1, X2)) -> MARK(X1) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) MARK(U42(X1, X2, X3)) -> MARK(X1) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) MARK(s(X)) -> MARK(X) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(U31(tt, N)) -> MARK(N) MARK(U31(X1, X2)) -> MARK(X1) 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)) = x_1 POL(U11(x_1, x_2)) = x_1 POL(U12(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(active(x_1)) = x_1 POL(isNat(x_1)) = 0 POL(mark(x_1)) = x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(tt) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) active(U11(tt, V2)) -> mark(U12(isNat(V2))) mark(U12(X)) -> active(U12(mark(X))) active(U31(tt, N)) -> mark(N) mark(isNat(X)) -> active(isNat(X)) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) mark(U21(X)) -> active(U21(mark(X))) active(U42(tt, M, N)) -> mark(s(plus(N, M))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) active(plus(N, 0)) -> mark(U31(isNat(N), N)) mark(s(X)) -> active(s(mark(X))) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(tt) -> active(tt) mark(0) -> active(0) U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) plus(X1, mark(X2)) -> plus(X1, X2) plus(mark(X1), X2) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) U31(X1, mark(X2)) -> U31(X1, X2) U31(mark(X1), X2) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(isNat(0)) -> mark(tt) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> ACTIVE(U31(mark(X1), X2)) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) MARK(U42(X1, X2, X3)) -> MARK(X1) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) MARK(s(X)) -> MARK(X) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. 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(U31(X1, X2)) -> ACTIVE(U31(mark(X1), 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(U11(x_1, x_2)) = 1 POL(U12(x_1)) = 0 POL(U21(x_1)) = 0 POL(U31(x_1, x_2)) = 0 POL(U41(x_1, x_2, x_3)) = 1 POL(U42(x_1, x_2, x_3)) = 1 POL(active(x_1)) = 0 POL(isNat(x_1)) = 1 POL(mark(x_1)) = 0 POL(plus(x_1, x_2)) = 1 POL(s(x_1)) = 0 POL(tt) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) plus(X1, mark(X2)) -> plus(X1, X2) plus(mark(X1), X2) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(mark(X1), X2) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) MARK(U42(X1, X2, X3)) -> MARK(X1) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) MARK(s(X)) -> MARK(X) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. 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(U41(X1, X2, X3)) -> MARK(X1) MARK(U42(X1, X2, X3)) -> MARK(X1) MARK(s(X)) -> MARK(X) 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)) = x_1 POL(U11(x_1, x_2)) = x_1 POL(U12(x_1)) = x_1 POL(U21(x_1)) = x_1 POL(U31(x_1, x_2)) = x_2 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(active(x_1)) = x_1 POL(isNat(x_1)) = 0 POL(mark(x_1)) = x_1 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 1 + x_1 POL(tt) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) active(U11(tt, V2)) -> mark(U12(isNat(V2))) mark(U12(X)) -> active(U12(mark(X))) active(U31(tt, N)) -> mark(N) mark(isNat(X)) -> active(isNat(X)) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) mark(U21(X)) -> active(U21(mark(X))) active(U42(tt, M, N)) -> mark(s(plus(N, M))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) active(plus(N, 0)) -> mark(U31(isNat(N), N)) mark(s(X)) -> active(s(mark(X))) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(tt) -> active(tt) mark(0) -> active(0) U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) plus(X1, mark(X2)) -> plus(X1, X2) plus(mark(X1), X2) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(isNat(0)) -> mark(tt) U31(X1, mark(X2)) -> U31(X1, X2) U31(mark(X1), X2) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(plus(X1, X2)) -> ACTIVE(plus(mark(X1), mark(X2))) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( ACTIVE_1(x_1) ) = max{0, -2} POL( U11_2(x_1, x_2) ) = x_1 + 1 POL( U41_3(x_1, ..., x_3) ) = 0 POL( U42_3(x_1, ..., x_3) ) = max{0, -2} POL( plus_2(x_1, x_2) ) = 2x_1 + x_2 + 2 POL( mark_1(x_1) ) = 2x_1 + 2 POL( active_1(x_1) ) = x_1 + 2 POL( tt ) = 0 POL( U12_1(x_1) ) = 2x_1 + 1 POL( isNat_1(x_1) ) = 0 POL( U31_2(x_1, x_2) ) = max{0, 2x_1 + 2x_2 - 2} POL( U21_1(x_1) ) = x_1 + 1 POL( s_1(x_1) ) = max{0, -2} POL( 0 ) = 1 POL( MARK_1(x_1) ) = max{0, 2x_1 - 2} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(active(X)) -> s(X) s(mark(X)) -> s(X) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(plus(N, s(M))) -> MARK(U41(isNat(M), M, N)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( ACTIVE_1(x_1) ) = max{0, 2x_1 - 2} POL( U11_2(x_1, x_2) ) = 2 POL( U41_3(x_1, ..., x_3) ) = 2 POL( U42_3(x_1, ..., x_3) ) = 2 POL( mark_1(x_1) ) = max{0, -2} POL( active_1(x_1) ) = max{0, -2} POL( tt ) = 0 POL( U12_1(x_1) ) = 2 POL( isNat_1(x_1) ) = 2 POL( U31_2(x_1, x_2) ) = max{0, 2x_1 - 2} POL( U21_1(x_1) ) = max{0, -2} POL( s_1(x_1) ) = 1 POL( plus_2(x_1, x_2) ) = x_2 + 2 POL( 0 ) = 0 POL( MARK_1(x_1) ) = 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) MARK(U21(X)) -> MARK(X) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(U21(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( ACTIVE_1(x_1) ) = max{0, 2x_1 - 1} POL( U11_2(x_1, x_2) ) = x_1 + x_2 + 1 POL( U41_3(x_1, ..., x_3) ) = x_2 + x_3 + 2 POL( U42_3(x_1, ..., x_3) ) = x_2 + x_3 + 2 POL( mark_1(x_1) ) = x_1 POL( active_1(x_1) ) = x_1 POL( tt ) = 2 POL( U12_1(x_1) ) = x_1 + 2 POL( isNat_1(x_1) ) = x_1 + 1 POL( U31_2(x_1, x_2) ) = x_2 + 1 POL( U21_1(x_1) ) = x_1 + 1 POL( s_1(x_1) ) = x_1 + 1 POL( plus_2(x_1, x_2) ) = x_1 + x_2 + 1 POL( 0 ) = 2 POL( MARK_1(x_1) ) = max{0, 2x_1 - 1} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) active(U11(tt, V2)) -> mark(U12(isNat(V2))) mark(U12(X)) -> active(U12(mark(X))) active(U31(tt, N)) -> mark(N) mark(isNat(X)) -> active(isNat(X)) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) mark(U21(X)) -> active(U21(mark(X))) active(U42(tt, M, N)) -> mark(s(plus(N, M))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) active(plus(N, 0)) -> mark(U31(isNat(N), N)) mark(s(X)) -> active(s(mark(X))) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(tt) -> active(tt) mark(0) -> active(0) U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) plus(X1, mark(X2)) -> plus(X1, X2) plus(mark(X1), X2) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) s(active(X)) -> s(X) s(mark(X)) -> s(X) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(isNat(0)) -> mark(tt) U31(X1, mark(X2)) -> U31(X1, X2) U31(mark(X1), X2) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) MARK(isNat(X)) -> ACTIVE(isNat(X)) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ACTIVE(U11(tt, V2)) -> MARK(U12(isNat(V2))) ACTIVE(U41(tt, M, N)) -> MARK(U42(isNat(N), M, N)) ACTIVE(U42(tt, M, N)) -> MARK(s(plus(N, M))) ACTIVE(isNat(plus(V1, V2))) -> MARK(U11(isNat(V1), V2)) ACTIVE(isNat(s(V1))) -> MARK(U21(isNat(V1))) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = x1 U11(x1, x2) = U11 ACTIVE(x1) = x1 U12(x1) = U12 isNat(x1) = isNat U41(x1, x2, x3) = U41 U42(x1, x2, x3) = U42 s(x1) = s U21(x1) = U21 Knuth-Bendix order [KBO] with precedence:isNat > U21 isNat > U11 > U12 and weight map: isNat=1 U42=3 s=2 U41=4 U12=1 U21=1 U11=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: U11(X1, mark(X2)) -> U11(X1, X2) U11(mark(X1), X2) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) isNat(active(X)) -> isNat(X) isNat(mark(X)) -> isNat(X) U12(active(X)) -> U12(X) U12(mark(X)) -> U12(X) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(active(X)) -> s(X) s(mark(X)) -> s(X) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U21(active(X)) -> U21(X) U21(mark(X)) -> U21(X) ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> ACTIVE(U11(mark(X1), X2)) MARK(isNat(X)) -> ACTIVE(isNat(X)) MARK(U41(X1, X2, X3)) -> ACTIVE(U41(mark(X1), X2, X3)) MARK(U42(X1, X2, X3)) -> ACTIVE(U42(mark(X1), X2, X3)) The TRS R consists of the following rules: active(U11(tt, V2)) -> mark(U12(isNat(V2))) active(U12(tt)) -> mark(tt) active(U21(tt)) -> mark(tt) active(U31(tt, N)) -> mark(N) active(U41(tt, M, N)) -> mark(U42(isNat(N), M, N)) active(U42(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNat(V1), V2)) active(isNat(s(V1))) -> mark(U21(isNat(V1))) active(plus(N, 0)) -> mark(U31(isNat(N), N)) active(plus(N, s(M))) -> mark(U41(isNat(M), M, N)) mark(U11(X1, X2)) -> active(U11(mark(X1), X2)) mark(tt) -> active(tt) mark(U12(X)) -> active(U12(mark(X))) mark(isNat(X)) -> active(isNat(X)) mark(U21(X)) -> active(U21(mark(X))) mark(U31(X1, X2)) -> active(U31(mark(X1), X2)) mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3)) mark(U42(X1, X2, X3)) -> active(U42(mark(X1), X2, X3)) mark(s(X)) -> active(s(mark(X))) mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2))) mark(0) -> active(0) U11(mark(X1), X2) -> U11(X1, X2) U11(X1, mark(X2)) -> U11(X1, X2) U11(active(X1), X2) -> U11(X1, X2) U11(X1, active(X2)) -> U11(X1, X2) U12(mark(X)) -> U12(X) U12(active(X)) -> U12(X) isNat(mark(X)) -> isNat(X) isNat(active(X)) -> isNat(X) U21(mark(X)) -> U21(X) U21(active(X)) -> U21(X) U31(mark(X1), X2) -> U31(X1, X2) U31(X1, mark(X2)) -> U31(X1, X2) U31(active(X1), X2) -> U31(X1, X2) U31(X1, active(X2)) -> U31(X1, X2) U41(mark(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, mark(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, mark(X3)) -> U41(X1, X2, X3) U41(active(X1), X2, X3) -> U41(X1, X2, X3) U41(X1, active(X2), X3) -> U41(X1, X2, X3) U41(X1, X2, active(X3)) -> U41(X1, X2, X3) U42(mark(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, mark(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, mark(X3)) -> U42(X1, X2, X3) U42(active(X1), X2, X3) -> U42(X1, X2, X3) U42(X1, active(X2), X3) -> U42(X1, X2, X3) U42(X1, X2, active(X3)) -> U42(X1, X2, X3) s(mark(X)) -> s(X) s(active(X)) -> s(X) plus(mark(X1), X2) -> plus(X1, X2) plus(X1, mark(X2)) -> plus(X1, X2) plus(active(X1), X2) -> plus(X1, X2) plus(X1, active(X2)) -> plus(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes. ---------------------------------------- (70) TRUE