/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/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, 54 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) QDPOrderProof [EQUIVALENT, 1294 ms] (12) QDP (13) DependencyGraphProof [EQUIVALENT, 0 ms] (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U12(tt) -> tt a__U21(tt) -> tt a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U32(tt) -> tt a__U41(tt, N) -> mark(N) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U61(tt) -> 0 a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__plus(N, 0) -> a__U41(a__isNat(N), N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNat(X) -> isNat(X) a__U21(X) -> U21(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U61(X) -> U61(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__x(X1, X2) -> x(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: A__U11(tt, V2) -> A__U12(a__isNat(V2)) A__U11(tt, V2) -> A__ISNAT(V2) A__U31(tt, V2) -> A__U32(a__isNat(V2)) A__U31(tt, V2) -> A__ISNAT(V2) A__U41(tt, N) -> MARK(N) A__U51(tt, M, N) -> A__U52(a__isNat(N), M, N) A__U51(tt, M, N) -> A__ISNAT(N) A__U52(tt, M, N) -> A__PLUS(mark(N), mark(M)) A__U52(tt, M, N) -> MARK(N) A__U52(tt, M, N) -> MARK(M) A__U71(tt, M, N) -> A__U72(a__isNat(N), M, N) A__U71(tt, M, N) -> A__ISNAT(N) A__U72(tt, M, N) -> A__PLUS(a__x(mark(N), mark(M)), mark(N)) A__U72(tt, M, N) -> A__X(mark(N), mark(M)) A__U72(tt, M, N) -> MARK(N) A__U72(tt, M, N) -> MARK(M) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNat(V1), V2) A__ISNAT(plus(V1, V2)) -> A__ISNAT(V1) A__ISNAT(s(V1)) -> A__U21(a__isNat(V1)) A__ISNAT(s(V1)) -> A__ISNAT(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNat(V1), V2) A__ISNAT(x(V1, V2)) -> A__ISNAT(V1) A__PLUS(N, 0) -> A__U41(a__isNat(N), N) A__PLUS(N, 0) -> A__ISNAT(N) A__PLUS(N, s(M)) -> A__U51(a__isNat(M), M, N) A__PLUS(N, s(M)) -> A__ISNAT(M) A__X(N, 0) -> A__U61(a__isNat(N)) A__X(N, 0) -> A__ISNAT(N) A__X(N, s(M)) -> A__U71(a__isNat(M), M, N) A__X(N, s(M)) -> A__ISNAT(M) MARK(U11(X1, X2)) -> A__U11(mark(X1), X2) MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> A__U12(mark(X)) MARK(U12(X)) -> MARK(X) MARK(isNat(X)) -> A__ISNAT(X) MARK(U21(X)) -> A__U21(mark(X)) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) MARK(U31(X1, X2)) -> MARK(X1) MARK(U32(X)) -> A__U32(mark(X)) MARK(U32(X)) -> MARK(X) MARK(U41(X1, X2)) -> A__U41(mark(X1), X2) MARK(U41(X1, X2)) -> MARK(X1) MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) MARK(U51(X1, X2, X3)) -> MARK(X1) MARK(U52(X1, X2, X3)) -> A__U52(mark(X1), X2, X3) MARK(U52(X1, X2, X3)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(U61(X)) -> A__U61(mark(X)) MARK(U61(X)) -> MARK(X) MARK(U71(X1, X2, X3)) -> A__U71(mark(X1), X2, X3) MARK(U71(X1, X2, X3)) -> MARK(X1) MARK(U72(X1, X2, X3)) -> A__U72(mark(X1), X2, X3) MARK(U72(X1, X2, X3)) -> MARK(X1) MARK(x(X1, X2)) -> A__X(mark(X1), mark(X2)) MARK(x(X1, X2)) -> MARK(X1) MARK(x(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U12(tt) -> tt a__U21(tt) -> tt a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U32(tt) -> tt a__U41(tt, N) -> mark(N) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U61(tt) -> 0 a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__plus(N, 0) -> a__U41(a__isNat(N), N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNat(X) -> isNat(X) a__U21(X) -> U21(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U61(X) -> U61(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__x(X1, X2) -> x(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 2 SCCs with 17 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: A__U11(tt, V2) -> A__ISNAT(V2) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNat(V1), V2) A__ISNAT(plus(V1, V2)) -> A__ISNAT(V1) A__ISNAT(s(V1)) -> A__ISNAT(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNat(V1), V2) A__U31(tt, V2) -> A__ISNAT(V2) A__ISNAT(x(V1, V2)) -> A__ISNAT(V1) The TRS R consists of the following rules: a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U12(tt) -> tt a__U21(tt) -> tt a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U32(tt) -> tt a__U41(tt, N) -> mark(N) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U61(tt) -> 0 a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__plus(N, 0) -> a__U41(a__isNat(N), N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNat(X) -> isNat(X) a__U21(X) -> U21(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U61(X) -> U61(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__x(X1, X2) -> x(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: A__U11(tt, V2) -> A__ISNAT(V2) A__ISNAT(plus(V1, V2)) -> A__U11(a__isNat(V1), V2) A__ISNAT(plus(V1, V2)) -> A__ISNAT(V1) A__ISNAT(s(V1)) -> A__ISNAT(V1) A__ISNAT(x(V1, V2)) -> A__U31(a__isNat(V1), V2) A__U31(tt, V2) -> A__ISNAT(V2) A__ISNAT(x(V1, V2)) -> A__ISNAT(V1) The TRS R consists of the following rules: a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__isNat(X) -> isNat(X) a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U31(X1, X2) -> U31(X1, X2) a__U32(tt) -> tt a__U32(X) -> U32(X) a__U21(tt) -> tt a__U21(X) -> U21(X) a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U11(X1, X2) -> U11(X1, X2) a__U12(tt) -> tt a__U12(X) -> U12(X) 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: *A__ISNAT(plus(V1, V2)) -> A__U11(a__isNat(V1), V2) The graph contains the following edges 1 > 2 *A__ISNAT(x(V1, V2)) -> A__U31(a__isNat(V1), V2) The graph contains the following edges 1 > 2 *A__U11(tt, V2) -> A__ISNAT(V2) The graph contains the following edges 2 >= 1 *A__U31(tt, V2) -> A__ISNAT(V2) The graph contains the following edges 2 >= 1 *A__ISNAT(plus(V1, V2)) -> A__ISNAT(V1) The graph contains the following edges 1 > 1 *A__ISNAT(s(V1)) -> A__ISNAT(V1) The graph contains the following edges 1 > 1 *A__ISNAT(x(V1, V2)) -> A__ISNAT(V1) The graph contains the following edges 1 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> MARK(X1) MARK(U32(X)) -> MARK(X) MARK(U41(X1, X2)) -> A__U41(mark(X1), X2) A__U41(tt, N) -> MARK(N) MARK(U41(X1, X2)) -> MARK(X1) MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) A__U51(tt, M, N) -> A__U52(a__isNat(N), M, N) A__U52(tt, M, N) -> A__PLUS(mark(N), mark(M)) A__PLUS(N, 0) -> A__U41(a__isNat(N), N) A__PLUS(N, s(M)) -> A__U51(a__isNat(M), M, N) A__U52(tt, M, N) -> MARK(N) MARK(U51(X1, X2, X3)) -> MARK(X1) MARK(U52(X1, X2, X3)) -> A__U52(mark(X1), X2, X3) A__U52(tt, M, N) -> MARK(M) MARK(U52(X1, X2, X3)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(U61(X)) -> MARK(X) MARK(U71(X1, X2, X3)) -> A__U71(mark(X1), X2, X3) A__U71(tt, M, N) -> A__U72(a__isNat(N), M, N) A__U72(tt, M, N) -> A__PLUS(a__x(mark(N), mark(M)), mark(N)) A__U72(tt, M, N) -> A__X(mark(N), mark(M)) A__X(N, s(M)) -> A__U71(a__isNat(M), M, N) A__U72(tt, M, N) -> MARK(N) MARK(U71(X1, X2, X3)) -> MARK(X1) MARK(U72(X1, X2, X3)) -> A__U72(mark(X1), X2, X3) A__U72(tt, M, N) -> MARK(M) MARK(U72(X1, X2, X3)) -> MARK(X1) MARK(x(X1, X2)) -> A__X(mark(X1), mark(X2)) MARK(x(X1, X2)) -> MARK(X1) MARK(x(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) The TRS R consists of the following rules: a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U12(tt) -> tt a__U21(tt) -> tt a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U32(tt) -> tt a__U41(tt, N) -> mark(N) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U61(tt) -> 0 a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__plus(N, 0) -> a__U41(a__isNat(N), N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNat(X) -> isNat(X) a__U21(X) -> U21(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U61(X) -> U61(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__x(X1, X2) -> x(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U41(X1, X2)) -> A__U41(mark(X1), X2) MARK(U41(X1, X2)) -> MARK(X1) MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) A__U52(tt, M, N) -> A__PLUS(mark(N), mark(M)) A__PLUS(N, 0) -> A__U41(a__isNat(N), N) A__PLUS(N, s(M)) -> A__U51(a__isNat(M), M, N) A__U52(tt, M, N) -> MARK(N) MARK(U51(X1, X2, X3)) -> MARK(X1) MARK(U52(X1, X2, X3)) -> A__U52(mark(X1), X2, X3) A__U52(tt, M, N) -> MARK(M) MARK(U52(X1, X2, X3)) -> MARK(X1) MARK(plus(X1, X2)) -> A__PLUS(mark(X1), mark(X2)) MARK(plus(X1, X2)) -> MARK(X1) MARK(plus(X1, X2)) -> MARK(X2) MARK(U71(X1, X2, X3)) -> A__U71(mark(X1), X2, X3) A__U72(tt, M, N) -> A__PLUS(a__x(mark(N), mark(M)), mark(N)) A__U72(tt, M, N) -> A__X(mark(N), mark(M)) A__X(N, s(M)) -> A__U71(a__isNat(M), M, N) A__U72(tt, M, N) -> MARK(N) MARK(U71(X1, X2, X3)) -> MARK(X1) MARK(U72(X1, X2, X3)) -> A__U72(mark(X1), X2, X3) A__U72(tt, M, N) -> MARK(M) MARK(U72(X1, X2, X3)) -> MARK(X1) MARK(x(X1, X2)) -> A__X(mark(X1), mark(X2)) MARK(x(X1, X2)) -> MARK(X1) MARK(x(X1, X2)) -> MARK(X2) MARK(s(X)) -> MARK(X) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. MARK(x1) = MARK(x1) U11(x1, x2) = x1 U12(x1) = x1 U21(x1) = x1 U31(x1, x2) = x1 U32(x1) = x1 U41(x1, x2) = U41(x1, x2) A__U41(x1, x2) = A__U41(x2) mark(x1) = x1 tt = tt U51(x1, x2, x3) = U51(x1, x2, x3) A__U51(x1, x2, x3) = A__U51(x1, x2, x3) A__U52(x1, x2, x3) = A__U52(x1, x2, x3) a__isNat(x1) = a__isNat A__PLUS(x1, x2) = A__PLUS(x1, x2) 0 = 0 s(x1) = s(x1) U52(x1, x2, x3) = U52(x1, x2, x3) plus(x1, x2) = plus(x1, x2) U61(x1) = x1 U71(x1, x2, x3) = U71(x1, x2, x3) A__U71(x1, x2, x3) = A__U71(x1, x2, x3) A__U72(x1, x2, x3) = A__U72(x1, x2, x3) a__x(x1, x2) = a__x(x1, x2) A__X(x1, x2) = A__X(x1, x2) U72(x1, x2, x3) = U72(x1, x2, x3) x(x1, x2) = x(x1, x2) a__U11(x1, x2) = x1 a__U12(x1) = x1 isNat(x1) = isNat a__U21(x1) = x1 a__U31(x1, x2) = x1 a__U32(x1) = x1 a__U41(x1, x2) = a__U41(x1, x2) a__plus(x1, x2) = a__plus(x1, x2) a__U71(x1, x2, x3) = a__U71(x1, x2, x3) a__U72(x1, x2, x3) = a__U72(x1, x2, x3) a__U51(x1, x2, x3) = a__U51(x1, x2, x3) a__U52(x1, x2, x3) = a__U52(x1, x2, x3) a__U61(x1) = x1 Recursive path order with status [RPO]. Quasi-Precedence: [U71_3, A__U71_3, A__U72_3, a__x_2, A__X_2, U72_3, x_2, a__U71_3, a__U72_3] > [U51_3, U52_3, plus_2, a__plus_2, a__U51_3, a__U52_3] > [tt, a__isNat, s_1, isNat] > [MARK_1, A__U41_1, A__U51_3, A__U52_3, A__PLUS_2, 0] > [U41_2, a__U41_2] Status: MARK_1: multiset status U41_2: multiset status A__U41_1: multiset status tt: multiset status U51_3: multiset status A__U51_3: multiset status A__U52_3: multiset status a__isNat: multiset status A__PLUS_2: multiset status 0: multiset status s_1: multiset status U52_3: multiset status plus_2: multiset status U71_3: [2,3,1] A__U71_3: [2,3,1] A__U72_3: [2,3,1] a__x_2: [2,1] A__X_2: [2,1] U72_3: [2,3,1] x_2: [2,1] isNat: multiset status a__U41_2: multiset status a__plus_2: multiset status a__U71_3: [2,3,1] a__U72_3: [2,3,1] a__U51_3: multiset status a__U52_3: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) a__U41(tt, N) -> mark(N) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) a__plus(N, 0) -> a__U41(a__isNat(N), N) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(U61(X)) -> a__U61(mark(X)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__isNat(X) -> isNat(X) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(X1, X2) -> x(X1, X2) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__plus(X1, X2) -> plus(X1, X2) a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U11(X1, X2) -> U11(X1, X2) a__U12(tt) -> tt a__U12(X) -> U12(X) a__U21(tt) -> tt a__U21(X) -> U21(X) a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U31(X1, X2) -> U31(X1, X2) a__U32(tt) -> tt a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__U61(tt) -> 0 a__U61(X) -> U61(X) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U11(X1, X2)) -> MARK(X1) MARK(U12(X)) -> MARK(X) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> MARK(X1) MARK(U32(X)) -> MARK(X) A__U41(tt, N) -> MARK(N) A__U51(tt, M, N) -> A__U52(a__isNat(N), M, N) MARK(U61(X)) -> MARK(X) A__U71(tt, M, N) -> A__U72(a__isNat(N), M, N) The TRS R consists of the following rules: a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U12(tt) -> tt a__U21(tt) -> tt a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U32(tt) -> tt a__U41(tt, N) -> mark(N) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U61(tt) -> 0 a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__plus(N, 0) -> a__U41(a__isNat(N), N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNat(X) -> isNat(X) a__U21(X) -> U21(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U61(X) -> U61(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__x(X1, X2) -> x(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U12(X)) -> MARK(X) MARK(U11(X1, X2)) -> MARK(X1) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> MARK(X1) MARK(U32(X)) -> MARK(X) MARK(U61(X)) -> MARK(X) The TRS R consists of the following rules: a__U11(tt, V2) -> a__U12(a__isNat(V2)) a__U12(tt) -> tt a__U21(tt) -> tt a__U31(tt, V2) -> a__U32(a__isNat(V2)) a__U32(tt) -> tt a__U41(tt, N) -> mark(N) a__U51(tt, M, N) -> a__U52(a__isNat(N), M, N) a__U52(tt, M, N) -> s(a__plus(mark(N), mark(M))) a__U61(tt) -> 0 a__U71(tt, M, N) -> a__U72(a__isNat(N), M, N) a__U72(tt, M, N) -> a__plus(a__x(mark(N), mark(M)), mark(N)) a__isNat(0) -> tt a__isNat(plus(V1, V2)) -> a__U11(a__isNat(V1), V2) a__isNat(s(V1)) -> a__U21(a__isNat(V1)) a__isNat(x(V1, V2)) -> a__U31(a__isNat(V1), V2) a__plus(N, 0) -> a__U41(a__isNat(N), N) a__plus(N, s(M)) -> a__U51(a__isNat(M), M, N) a__x(N, 0) -> a__U61(a__isNat(N)) a__x(N, s(M)) -> a__U71(a__isNat(M), M, N) mark(U11(X1, X2)) -> a__U11(mark(X1), X2) mark(U12(X)) -> a__U12(mark(X)) mark(isNat(X)) -> a__isNat(X) mark(U21(X)) -> a__U21(mark(X)) mark(U31(X1, X2)) -> a__U31(mark(X1), X2) mark(U32(X)) -> a__U32(mark(X)) mark(U41(X1, X2)) -> a__U41(mark(X1), X2) mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) mark(U52(X1, X2, X3)) -> a__U52(mark(X1), X2, X3) mark(plus(X1, X2)) -> a__plus(mark(X1), mark(X2)) mark(U61(X)) -> a__U61(mark(X)) mark(U71(X1, X2, X3)) -> a__U71(mark(X1), X2, X3) mark(U72(X1, X2, X3)) -> a__U72(mark(X1), X2, X3) mark(x(X1, X2)) -> a__x(mark(X1), mark(X2)) mark(tt) -> tt mark(s(X)) -> s(mark(X)) mark(0) -> 0 a__U11(X1, X2) -> U11(X1, X2) a__U12(X) -> U12(X) a__isNat(X) -> isNat(X) a__U21(X) -> U21(X) a__U31(X1, X2) -> U31(X1, X2) a__U32(X) -> U32(X) a__U41(X1, X2) -> U41(X1, X2) a__U51(X1, X2, X3) -> U51(X1, X2, X3) a__U52(X1, X2, X3) -> U52(X1, X2, X3) a__plus(X1, X2) -> plus(X1, X2) a__U61(X) -> U61(X) a__U71(X1, X2, X3) -> U71(X1, X2, X3) a__U72(X1, X2, X3) -> U72(X1, X2, X3) a__x(X1, X2) -> x(X1, X2) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) 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. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U12(X)) -> MARK(X) MARK(U11(X1, X2)) -> MARK(X1) MARK(U21(X)) -> MARK(X) MARK(U31(X1, X2)) -> MARK(X1) MARK(U32(X)) -> MARK(X) MARK(U61(X)) -> MARK(X) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MARK(U12(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U11(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U21(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U31(X1, X2)) -> MARK(X1) The graph contains the following edges 1 > 1 *MARK(U32(X)) -> MARK(X) The graph contains the following edges 1 > 1 *MARK(U61(X)) -> MARK(X) The graph contains the following edges 1 > 1 ---------------------------------------- (18) YES