/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, 47 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) QDP (5) QDPOrderProof [EQUIVALENT, 721 ms] (6) QDP (7) DependencyGraphProof [EQUIVALENT, 0 ms] (8) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: U11(tt, V2) -> U12(isNat(activate(V2))) U12(tt) -> tt U21(tt) -> tt U31(tt, V2) -> U32(isNat(activate(V2))) U32(tt) -> tt U41(tt, N) -> activate(N) U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) U52(tt, M, N) -> s(plus(activate(N), activate(M))) U61(tt) -> 0 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) isNat(n__s(V1)) -> U21(isNat(activate(V1))) isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) plus(N, 0) -> U41(isNat(N), N) plus(N, s(M)) -> U51(isNat(M), M, N) x(N, 0) -> U61(isNat(N)) x(N, s(M)) -> U71(isNat(M), M, N) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X 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: U11^1(tt, V2) -> U12^1(isNat(activate(V2))) U11^1(tt, V2) -> ISNAT(activate(V2)) U11^1(tt, V2) -> ACTIVATE(V2) U31^1(tt, V2) -> U32^1(isNat(activate(V2))) U31^1(tt, V2) -> ISNAT(activate(V2)) U31^1(tt, V2) -> ACTIVATE(V2) U41^1(tt, N) -> ACTIVATE(N) U51^1(tt, M, N) -> U52^1(isNat(activate(N)), activate(M), activate(N)) U51^1(tt, M, N) -> ISNAT(activate(N)) U51^1(tt, M, N) -> ACTIVATE(N) U51^1(tt, M, N) -> ACTIVATE(M) U52^1(tt, M, N) -> S(plus(activate(N), activate(M))) U52^1(tt, M, N) -> PLUS(activate(N), activate(M)) U52^1(tt, M, N) -> ACTIVATE(N) U52^1(tt, M, N) -> ACTIVATE(M) U61^1(tt) -> 0^1 U71^1(tt, M, N) -> U72^1(isNat(activate(N)), activate(M), activate(N)) U71^1(tt, M, N) -> ISNAT(activate(N)) U71^1(tt, M, N) -> ACTIVATE(N) U71^1(tt, M, N) -> ACTIVATE(M) U72^1(tt, M, N) -> PLUS(x(activate(N), activate(M)), activate(N)) U72^1(tt, M, N) -> X(activate(N), activate(M)) U72^1(tt, M, N) -> ACTIVATE(N) U72^1(tt, M, N) -> ACTIVATE(M) ISNAT(n__plus(V1, V2)) -> U11^1(isNat(activate(V1)), activate(V2)) ISNAT(n__plus(V1, V2)) -> ISNAT(activate(V1)) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V1) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V2) ISNAT(n__s(V1)) -> U21^1(isNat(activate(V1))) ISNAT(n__s(V1)) -> ISNAT(activate(V1)) ISNAT(n__s(V1)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> U31^1(isNat(activate(V1)), activate(V2)) ISNAT(n__x(V1, V2)) -> ISNAT(activate(V1)) ISNAT(n__x(V1, V2)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> ACTIVATE(V2) PLUS(N, 0) -> U41^1(isNat(N), N) PLUS(N, 0) -> ISNAT(N) PLUS(N, s(M)) -> U51^1(isNat(M), M, N) PLUS(N, s(M)) -> ISNAT(M) X(N, 0) -> U61^1(isNat(N)) X(N, 0) -> ISNAT(N) X(N, s(M)) -> U71^1(isNat(M), M, N) X(N, s(M)) -> ISNAT(M) ACTIVATE(n__0) -> 0^1 ACTIVATE(n__plus(X1, X2)) -> PLUS(activate(X1), activate(X2)) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__s(X)) -> S(activate(X)) ACTIVATE(n__s(X)) -> ACTIVATE(X) ACTIVATE(n__x(X1, X2)) -> X(activate(X1), activate(X2)) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X2) The TRS R consists of the following rules: U11(tt, V2) -> U12(isNat(activate(V2))) U12(tt) -> tt U21(tt) -> tt U31(tt, V2) -> U32(isNat(activate(V2))) U32(tt) -> tt U41(tt, N) -> activate(N) U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) U52(tt, M, N) -> s(plus(activate(N), activate(M))) U61(tt) -> 0 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) isNat(n__s(V1)) -> U21(isNat(activate(V1))) isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) plus(N, 0) -> U41(isNat(N), N) plus(N, s(M)) -> U51(isNat(M), M, N) x(N, 0) -> U61(isNat(N)) x(N, s(M)) -> U71(isNat(M), M, N) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X 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 1 SCC with 8 less nodes. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: U11^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__plus(V1, V2)) -> U11^1(isNat(activate(V1)), activate(V2)) U11^1(tt, V2) -> ACTIVATE(V2) ACTIVATE(n__plus(X1, X2)) -> PLUS(activate(X1), activate(X2)) PLUS(N, 0) -> U41^1(isNat(N), N) U41^1(tt, N) -> ACTIVATE(N) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__s(X)) -> ACTIVATE(X) ACTIVATE(n__x(X1, X2)) -> X(activate(X1), activate(X2)) X(N, 0) -> ISNAT(N) ISNAT(n__plus(V1, V2)) -> ISNAT(activate(V1)) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X2) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V2) ISNAT(n__s(V1)) -> ISNAT(activate(V1)) ISNAT(n__s(V1)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> U31^1(isNat(activate(V1)), activate(V2)) U31^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__x(V1, V2)) -> ISNAT(activate(V1)) ISNAT(n__x(V1, V2)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> ACTIVATE(V2) U31^1(tt, V2) -> ACTIVATE(V2) X(N, s(M)) -> U71^1(isNat(M), M, N) U71^1(tt, M, N) -> U72^1(isNat(activate(N)), activate(M), activate(N)) U72^1(tt, M, N) -> PLUS(x(activate(N), activate(M)), activate(N)) PLUS(N, 0) -> ISNAT(N) PLUS(N, s(M)) -> U51^1(isNat(M), M, N) U51^1(tt, M, N) -> U52^1(isNat(activate(N)), activate(M), activate(N)) U52^1(tt, M, N) -> PLUS(activate(N), activate(M)) PLUS(N, s(M)) -> ISNAT(M) U52^1(tt, M, N) -> ACTIVATE(N) U52^1(tt, M, N) -> ACTIVATE(M) U51^1(tt, M, N) -> ISNAT(activate(N)) U51^1(tt, M, N) -> ACTIVATE(N) U51^1(tt, M, N) -> ACTIVATE(M) U72^1(tt, M, N) -> X(activate(N), activate(M)) X(N, s(M)) -> ISNAT(M) U72^1(tt, M, N) -> ACTIVATE(N) U72^1(tt, M, N) -> ACTIVATE(M) U71^1(tt, M, N) -> ISNAT(activate(N)) U71^1(tt, M, N) -> ACTIVATE(N) U71^1(tt, M, N) -> ACTIVATE(M) The TRS R consists of the following rules: U11(tt, V2) -> U12(isNat(activate(V2))) U12(tt) -> tt U21(tt) -> tt U31(tt, V2) -> U32(isNat(activate(V2))) U32(tt) -> tt U41(tt, N) -> activate(N) U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) U52(tt, M, N) -> s(plus(activate(N), activate(M))) U61(tt) -> 0 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) isNat(n__s(V1)) -> U21(isNat(activate(V1))) isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) plus(N, 0) -> U41(isNat(N), N) plus(N, s(M)) -> U51(isNat(M), M, N) x(N, 0) -> U61(isNat(N)) x(N, s(M)) -> U71(isNat(M), M, N) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U11^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__plus(V1, V2)) -> U11^1(isNat(activate(V1)), activate(V2)) U11^1(tt, V2) -> ACTIVATE(V2) ACTIVATE(n__plus(X1, X2)) -> PLUS(activate(X1), activate(X2)) PLUS(N, 0) -> U41^1(isNat(N), N) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__plus(X1, X2)) -> ACTIVATE(X2) ACTIVATE(n__s(X)) -> ACTIVATE(X) X(N, 0) -> ISNAT(N) ISNAT(n__plus(V1, V2)) -> ISNAT(activate(V1)) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X1) ACTIVATE(n__x(X1, X2)) -> ACTIVATE(X2) ISNAT(n__plus(V1, V2)) -> ACTIVATE(V2) ISNAT(n__s(V1)) -> ISNAT(activate(V1)) ISNAT(n__s(V1)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> U31^1(isNat(activate(V1)), activate(V2)) U31^1(tt, V2) -> ISNAT(activate(V2)) ISNAT(n__x(V1, V2)) -> ISNAT(activate(V1)) ISNAT(n__x(V1, V2)) -> ACTIVATE(V1) ISNAT(n__x(V1, V2)) -> ACTIVATE(V2) U31^1(tt, V2) -> ACTIVATE(V2) X(N, s(M)) -> U71^1(isNat(M), M, N) U72^1(tt, M, N) -> PLUS(x(activate(N), activate(M)), activate(N)) PLUS(N, 0) -> ISNAT(N) PLUS(N, s(M)) -> U51^1(isNat(M), M, N) U51^1(tt, M, N) -> U52^1(isNat(activate(N)), activate(M), activate(N)) PLUS(N, s(M)) -> ISNAT(M) U52^1(tt, M, N) -> ACTIVATE(N) U52^1(tt, M, N) -> ACTIVATE(M) U51^1(tt, M, N) -> ISNAT(activate(N)) U51^1(tt, M, N) -> ACTIVATE(N) U51^1(tt, M, N) -> ACTIVATE(M) U72^1(tt, M, N) -> X(activate(N), activate(M)) X(N, s(M)) -> ISNAT(M) U72^1(tt, M, N) -> ACTIVATE(N) U72^1(tt, M, N) -> ACTIVATE(M) U71^1(tt, M, N) -> ISNAT(activate(N)) U71^1(tt, M, N) -> ACTIVATE(N) U71^1(tt, M, N) -> ACTIVATE(M) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. U11^1(x1, x2) = U11^1(x2) tt = tt ISNAT(x1) = ISNAT(x1) activate(x1) = x1 n__plus(x1, x2) = n__plus(x1, x2) isNat(x1) = isNat ACTIVATE(x1) = x1 PLUS(x1, x2) = PLUS(x1, x2) 0 = 0 U41^1(x1, x2) = x2 n__s(x1) = n__s(x1) n__x(x1, x2) = n__x(x1, x2) X(x1, x2) = X(x1, x2) U31^1(x1, x2) = U31^1(x1, x2) s(x1) = s(x1) U71^1(x1, x2, x3) = U71^1(x1, x2, x3) U72^1(x1, x2, x3) = U72^1(x1, x2, x3) x(x1, x2) = x(x1, x2) U51^1(x1, x2, x3) = U51^1(x1, x2, x3) U52^1(x1, x2, x3) = U52^1(x2, x3) n__0 = n__0 plus(x1, x2) = plus(x1, x2) U41(x1, x2) = x2 U71(x1, x2, x3) = U71(x1, x2, x3) U72(x1, x2, x3) = U72(x1, x2, x3) U11(x1, x2) = x1 U21(x1) = x1 U31(x1, x2) = x1 U61(x1) = U61(x1) U51(x1, x2, x3) = U51(x1, x2, x3) U32(x1) = U32 U12(x1) = x1 U52(x1, x2, x3) = U52(x1, x2, x3) Recursive path order with status [RPO]. Quasi-Precedence: [n__x_2, X_2, U71^1_3, U72^1_3, x_2, U71_3, U72_3] > [n__plus_2, plus_2, U51_3, U52_3] > U11^1_1 > ISNAT_1 [n__x_2, X_2, U71^1_3, U72^1_3, x_2, U71_3, U72_3] > [n__plus_2, plus_2, U51_3, U52_3] > [n__s_1, s_1] > [tt, isNat, U32] > [PLUS_2, U51^1_3, U52^1_2] > ISNAT_1 [n__x_2, X_2, U71^1_3, U72^1_3, x_2, U71_3, U72_3] > U31^1_2 > ISNAT_1 [n__x_2, X_2, U71^1_3, U72^1_3, x_2, U71_3, U72_3] > U61_1 > [0, n__0] > [tt, isNat, U32] > [PLUS_2, U51^1_3, U52^1_2] > ISNAT_1 Status: U11^1_1: multiset status tt: multiset status ISNAT_1: multiset status n__plus_2: multiset status isNat: multiset status PLUS_2: multiset status 0: multiset status n__s_1: [1] n__x_2: multiset status X_2: multiset status U31^1_2: multiset status s_1: [1] U71^1_3: multiset status U72^1_3: multiset status x_2: multiset status U51^1_3: multiset status U52^1_2: multiset status n__0: multiset status plus_2: multiset status U71_3: multiset status U72_3: multiset status U61_1: multiset status U51_3: multiset status U32: multiset status U52_3: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) plus(N, 0) -> U41(isNat(N), N) U41(tt, N) -> activate(N) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) x(N, s(M)) -> U71(isNat(M), M, N) U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) activate(n__s(X)) -> s(activate(X)) activate(X) -> X isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) isNat(n__s(V1)) -> U21(isNat(activate(V1))) isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) x(N, 0) -> U61(isNat(N)) x(X1, X2) -> n__x(X1, X2) plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) plus(N, s(M)) -> U51(isNat(M), M, N) U21(tt) -> tt U31(tt, V2) -> U32(isNat(activate(V2))) U32(tt) -> tt U11(tt, V2) -> U12(isNat(activate(V2))) U12(tt) -> tt U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) U52(tt, M, N) -> s(plus(activate(N), activate(M))) U61(tt) -> 0 0 -> n__0 ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: U41^1(tt, N) -> ACTIVATE(N) ACTIVATE(n__x(X1, X2)) -> X(activate(X1), activate(X2)) U71^1(tt, M, N) -> U72^1(isNat(activate(N)), activate(M), activate(N)) U52^1(tt, M, N) -> PLUS(activate(N), activate(M)) The TRS R consists of the following rules: U11(tt, V2) -> U12(isNat(activate(V2))) U12(tt) -> tt U21(tt) -> tt U31(tt, V2) -> U32(isNat(activate(V2))) U32(tt) -> tt U41(tt, N) -> activate(N) U51(tt, M, N) -> U52(isNat(activate(N)), activate(M), activate(N)) U52(tt, M, N) -> s(plus(activate(N), activate(M))) U61(tt) -> 0 U71(tt, M, N) -> U72(isNat(activate(N)), activate(M), activate(N)) U72(tt, M, N) -> plus(x(activate(N), activate(M)), activate(N)) isNat(n__0) -> tt isNat(n__plus(V1, V2)) -> U11(isNat(activate(V1)), activate(V2)) isNat(n__s(V1)) -> U21(isNat(activate(V1))) isNat(n__x(V1, V2)) -> U31(isNat(activate(V1)), activate(V2)) plus(N, 0) -> U41(isNat(N), N) plus(N, s(M)) -> U51(isNat(M), M, N) x(N, 0) -> U61(isNat(N)) x(N, s(M)) -> U71(isNat(M), M, N) 0 -> n__0 plus(X1, X2) -> n__plus(X1, X2) s(X) -> n__s(X) x(X1, X2) -> n__x(X1, X2) activate(n__0) -> 0 activate(n__plus(X1, X2)) -> plus(activate(X1), activate(X2)) activate(n__s(X)) -> s(activate(X)) activate(n__x(X1, X2)) -> x(activate(X1), activate(X2)) activate(X) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 4 less nodes. ---------------------------------------- (8) TRUE