/export/starexec/sandbox/solver/bin/starexec_run_default /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES We split firstr-order part and higher-order part, and do modular checking by a general modularity. ******** FO SN check ******** Check SN using AProVE (RWTH Aachen University) proof of tmp15483.trs # AProVE Commit ID: 240871ee8d33536d563834eff18151406a8bc3fe ffrohn 20170821 unpublished Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) MRRProof [EQUIVALENT, 15 ms] (9) QDP (10) MRRProof [EQUIVALENT, 24 ms] (11) QDP (12) MRRProof [EQUIVALENT, 0 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) TRUE (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) QDPOrderProof [EQUIVALENT, 0 ms] (23) QDP (24) PisEmptyProof [EQUIVALENT, 0 ms] (25) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> 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: MINUS(s(Y), s(U)) -> MINUS(Y, U) QUOT(s(W), s(P)) -> QUOT(minus(W, P), s(P)) QUOT(s(W), s(P)) -> MINUS(W, P) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> 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 3 SCCs with 1 less node. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> 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(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) minus(s(Y), s(U)) -> minus(Y, U) minus(X, 0) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: minus(X, 0) -> X Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = 1 + x_1 + x_2 POL(plus(x_1, x_2)) = 2*x_1 + 2*x_2 POL(s(x_1)) = x_1 ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) minus(s(Y), s(U)) -> minus(Y, U) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: plus(0, X1) -> X1 Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = x_1 + x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) minus(s(Y), s(U)) -> minus(Y, U) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: PLUS(s(Y1), U1) -> PLUS(Y1, U1) Strictly oriented rules of the TRS R: plus(s(Y1), U1) -> s(plus(Y1, U1)) minus(s(Y), s(U)) -> minus(Y, U) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = 2*x_1 + x_2 POL(plus(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(s(x_1)) = 1 + x_1 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (15) TRUE ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(Y), s(U)) -> MINUS(Y, U) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> X2 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(Y), s(U)) -> MINUS(Y, U) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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: *MINUS(s(Y), s(U)) -> MINUS(Y, U) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: QUOT(s(W), s(P)) -> QUOT(minus(W, P), s(P)) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> X2 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. QUOT(s(W), s(P)) -> QUOT(minus(W, P), s(P)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. QUOT(x1, x2) = x1 s(x1) = s(x1) minus(x1, x2) = x1 Knuth-Bendix order [KBO] with precedence:trivial and weight map: s_1=1 dummyConstant=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) ---------------------------------------- (23) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> X2 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (25) YES ... proof of tmp15483.trs # AProVE Commit ID: 240871ee8d33536d563834eff18151406a8bc3fe ffrohn 20170821 unpublished Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 0 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) MRRProof [EQUIVALENT, 15 ms] (9) QDP (10) MRRProof [EQUIVALENT, 24 ms] (11) QDP (12) MRRProof [EQUIVALENT, 0 ms] (13) QDP (14) DependencyGraphProof [EQUIVALENT, 0 ms] (15) TRUE (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) QDPOrderProof [EQUIVALENT, 0 ms] (23) QDP (24) PisEmptyProof [EQUIVALENT, 0 ms] (25) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> 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: MINUS(s(Y), s(U)) -> MINUS(Y, U) QUOT(s(W), s(P)) -> QUOT(minus(W, P), s(P)) QUOT(s(W), s(P)) -> MINUS(W, P) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> 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 3 SCCs with 1 less node. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> 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(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) minus(s(Y), s(U)) -> minus(Y, U) minus(X, 0) -> X Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: minus(X, 0) -> X Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = 1 + x_1 + x_2 POL(plus(x_1, x_2)) = 2*x_1 + 2*x_2 POL(s(x_1)) = x_1 ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) minus(s(Y), s(U)) -> minus(Y, U) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: plus(0, X1) -> X1 Used ordering: Polynomial interpretation [POLO]: POL(0) = 2 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = x_1 + x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(s(Y1), U1) -> PLUS(Y1, U1) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) minus(s(Y), s(U)) -> minus(Y, U) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented dependency pairs: PLUS(s(Y1), U1) -> PLUS(Y1, U1) Strictly oriented rules of the TRS R: plus(s(Y1), U1) -> s(plus(Y1, U1)) minus(s(Y), s(U)) -> minus(Y, U) Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = 2*x_1 + x_2 POL(plus(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(s(x_1)) = 1 + x_1 ---------------------------------------- (13) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(minus(V1, s(0)), minus(W1, s(s(P1)))) -> PLUS(minus(W1, s(s(P1))), minus(V1, s(0))) PLUS(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> PLUS(plus(Y2, s(s(U2))), plus(X2, s(0))) The TRS R consists of the following rules: plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (14) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (15) TRUE ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(Y), s(U)) -> MINUS(Y, U) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> X2 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(Y), s(U)) -> MINUS(Y, U) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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: *MINUS(s(Y), s(U)) -> MINUS(Y, U) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: QUOT(s(W), s(P)) -> QUOT(minus(W, P), s(P)) The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> X2 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. QUOT(s(W), s(P)) -> QUOT(minus(W, P), s(P)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. QUOT(x1, x2) = x1 s(x1) = s(x1) minus(x1, x2) = x1 Knuth-Bendix order [KBO] with precedence:trivial and weight map: s_1=1 dummyConstant=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) ---------------------------------------- (23) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: minus(X, 0) -> X minus(s(Y), s(U)) -> minus(Y, U) quot(0, s(V)) -> 0 quot(s(W), s(P)) -> s(quot(minus(W, P), s(P))) plus(0, X1) -> X1 plus(s(Y1), U1) -> s(plus(Y1, U1)) plus(minus(V1, s(0)), minus(W1, s(s(P1)))) -> plus(minus(W1, s(s(P1))), minus(V1, s(0))) plus(plus(X2, s(0)), plus(Y2, s(s(U2)))) -> plus(plus(Y2, s(s(U2))), plus(X2, s(0))) _(X1, X2) -> X1 _(X1, X2) -> X2 Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (25) YES >>YES ******** Signature ******** map : ((c -> c),d) -> d nil : d cons : (c,d) -> d filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d true : b false : b ******** Computation rules ******** (9) map(H2,nil) => nil (10) map(I2,cons(P2,X3)) => cons(I2[P2],map(I2,X3)) (11) filter(Z3,nil) => nil (12) filter(G3,cons(V3,W3)) => filter2(G3[V3],G3,V3,W3) (13) filter2(true,J3,X4,Y4) => cons(X4,filter(J3,Y4)) (14) filter2(false,G4,V4,W4) => filter(G4,W4) ******** General Schema criterion ******** Found constructors: 0, cons, false, nil, s, true Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (1) minus(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (2) minus(s(Y),s(U)) => minus(Y,U) (fun minus=minus) subterm comparison of args w. LR LR (meta Y)[is acc in s(Y),s(U)] [is positive in s(Y)] [is acc in Y] (meta U)[is acc in s(Y),s(U)] [is positive in s(Y)] [is positive in s(U)] [is acc in U] >>True Checking (3) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) subterm comparison of args w. LR LR >>False Try again using status RL Checking (1) minus(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (2) minus(s(Y),s(U)) => minus(Y,U) (fun minus=minus) subterm comparison of args w. RL RL (meta Y)[is acc in s(Y),s(U)] [is positive in s(Y)] [is acc in Y] (meta U)[is acc in s(Y),s(U)] [is positive in s(Y)] [is positive in s(U)] [is acc in U] >>True Checking (3) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) subterm comparison of args w. RL RL >>False Try again using status Mul Checking (1) minus(X,0) => X (meta X)[is acc in X,0] [is acc in X] >>True Checking (2) minus(s(Y),s(U)) => minus(Y,U) (fun minus=minus) subterm comparison of args w. Mul Mul (meta Y)[is acc in s(Y),s(U)] [is positive in s(Y)] [is acc in Y] (meta U)[is acc in s(Y),s(U)] [is positive in s(Y)] [is positive in s(U)] [is acc in U] >>True Checking (3) quot(0,s(V)) => 0 (fun quot>0) >>True Checking (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (fun quot>s) (fun quot=quot) subterm comparison of args w. Mul Mul >>False Found constructors: nil, cons, true, false Checking type order >>OK Checking positivity of constructors >>OK Checking function dependency >>Regared as equal: filter2, filter Checking (9) map(H2,nil) => nil (fun map>nil) >>True Checking (10) map(I2,cons(P2,X3)) => cons(I2[P2],map(I2,X3)) (fun map>cons) (meta I2)[is acc in I2,cons(P2,X3)] [is acc in I2] (meta P2)[is acc in I2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in P2] (fun map=map) subterm comparison of args w. LR LR (meta I2)[is acc in I2,cons(P2,X3)] [is acc in I2] (meta X3)[is acc in I2,cons(P2,X3)] [is positive in cons(P2,X3)] [is acc in X3] >>True Checking (11) filter(Z3,nil) => nil (fun filter>nil) >>True Checking (12) filter(G3,cons(V3,W3)) => filter2(G3[V3],G3,V3,W3) (fun filter=filter2) subterm comparison of args w. Arg [1,2] Arg [2,4,3,1] (meta G3)[is acc in G3,cons(V3,W3)] [is acc in G3] (meta V3)[is acc in G3,cons(V3,W3)] [is positive in cons(V3,W3)] [is acc in V3] (meta G3)[is acc in G3,cons(V3,W3)] [is acc in G3] (meta V3)[is acc in G3,cons(V3,W3)] [is positive in cons(V3,W3)] [is acc in V3] (meta W3)[is acc in G3,cons(V3,W3)] [is positive in cons(V3,W3)] [is acc in W3] >>True Checking (13) filter2(true,J3,X4,Y4) => cons(X4,filter(J3,Y4)) (fun filter2>cons) (meta X4)[is acc in true,J3,X4,Y4] [is positive in true] [is acc in X4] (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta J3)[is acc in true,J3,X4,Y4] [is positive in true] [is acc in J3] (meta Y4)[is acc in true,J3,X4,Y4] [is positive in true] [is acc in Y4] >>True Checking (14) filter2(false,G4,V4,W4) => filter(G4,W4) (fun filter2=filter) subterm comparison of args w. Arg [2,4,3,1] Arg [1,2] (meta G4)[is acc in false,G4,V4,W4] [is positive in false] [is acc in G4] (meta W4)[is acc in false,G4,V4,W4] [is positive in false] [is acc in W4] >>True #SN! ******** Signature ******** 0 : a cons : (c,d) -> d false : b filter : ((c -> b),d) -> d filter2 : (b,(c -> b),c,d) -> d map : ((c -> c),d) -> d minus : (a,a) -> a nil : d plus : (a,a) -> a quot : (a,a) -> a s : a -> a true : b ******** Computation Rules ******** (1) minus(X,0) => X (2) minus(s(Y),s(U)) => minus(Y,U) (3) quot(0,s(V)) => 0 (4) quot(s(W),s(P)) => s(quot(minus(W,P),s(P))) (5) 0 + X1 => X1 (6) s(Y1) + U1 => s(Y1 + U1) (7) minus(V1,s(0)) + minus(W1,s(s(P1))) => minus(W1,s(s(P1))) + minus(V1,s(0)) (8) (X2 + s(0)) + (Y2 + s(s(U2))) => (Y2 + s(s(U2))) + (X2 + s(0)) (9) map(H2,nil) => nil (10) map(I2,cons(P2,X3)) => cons(I2[P2],map(I2,X3)) (11) filter(Z3,nil) => nil (12) filter(G3,cons(V3,W3)) => filter2(G3[V3],G3,V3,W3) (13) filter2(true,J3,X4,Y4) => cons(X4,filter(J3,Y4)) (14) filter2(false,G4,V4,W4) => filter(G4,W4) YES