/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, 0 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) MNOCProof [EQUIVALENT, 0 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) AND (17) QDP (18) UsableRulesProof [EQUIVALENT, 0 ms] (19) QDP (20) QReductionProof [EQUIVALENT, 0 ms] (21) QDP (22) QDPOrderProof [EQUIVALENT, 22 ms] (23) QDP (24) PisEmptyProof [EQUIVALENT, 0 ms] (25) YES (26) QDP (27) QDPSizeChangeProof [EQUIVALENT, 0 ms] (28) YES (29) QDP (30) UsableRulesProof [EQUIVALENT, 0 ms] (31) QDP (32) MNOCProof [EQUIVALENT, 0 ms] (33) QDP (34) UsableRulesReductionPairsProof [EQUIVALENT, 16 ms] (35) QDP (36) TransformationProof [EQUIVALENT, 0 ms] (37) QDP (38) UsableRulesProof [EQUIVALENT, 0 ms] (39) QDP (40) QDPOrderProof [EQUIVALENT, 15 ms] (41) QDP (42) PisEmptyProof [EQUIVALENT, 0 ms] (43) YES (44) QDP (45) QDPOrderProof [EQUIVALENT, 0 ms] (46) QDP (47) QDPOrderProof [EQUIVALENT, 0 ms] (48) QDP (49) PisEmptyProof [EQUIVALENT, 0 ms] (50) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) 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(x), s(y)) -> MINUS(p(s(x)), p(s(y))) MINUS(s(x), s(y)) -> P(s(x)) MINUS(s(x), s(y)) -> P(s(y)) MINUS(x, plus(y, z)) -> MINUS(minus(x, y), z) MINUS(x, plus(y, z)) -> MINUS(x, y) P(s(s(x))) -> P(s(x)) DIV(s(x), s(y)) -> DIV(minus(x, y), s(y)) DIV(s(x), s(y)) -> MINUS(x, y) DIV(plus(x, y), z) -> PLUS(div(x, z), div(y, z)) DIV(plus(x, y), z) -> DIV(x, z) DIV(plus(x, y), z) -> DIV(y, z) PLUS(s(x), y) -> PLUS(y, minus(s(x), s(0))) PLUS(s(x), y) -> MINUS(s(x), s(0)) The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) 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 4 SCCs with 5 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: P(s(s(x))) -> P(s(x)) The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) 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: P(s(s(x))) -> P(s(x)) 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: *P(s(s(x))) -> P(s(x)) The graph contains the following edges 1 > 1 ---------------------------------------- (9) YES ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(x, plus(y, z)) -> MINUS(minus(x, y), z) MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) MINUS(x, plus(y, z)) -> MINUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) 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: MINUS(x, plus(y, z)) -> MINUS(minus(x, y), z) MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) MINUS(x, plus(y, z)) -> MINUS(x, y) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) minus(x, 0) -> x minus(0, y) -> 0 minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(x, plus(y, z)) -> MINUS(minus(x, y), z) MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) MINUS(x, plus(y, z)) -> MINUS(x, y) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) minus(x, 0) -> x minus(0, y) -> 0 minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) The set Q consists of the following terms: p(s(s(x0))) minus(x0, 0) minus(0, x0) minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (16) Complex Obligation (AND) ---------------------------------------- (17) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) minus(x, 0) -> x minus(0, y) -> 0 minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) The set Q consists of the following terms: p(s(s(x0))) minus(x0, 0) minus(0, x0) minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (18) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) The set Q consists of the following terms: p(s(s(x0))) minus(x0, 0) minus(0, x0) minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minus(x0, 0) minus(0, x0) minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) The set Q consists of the following terms: p(s(s(x0))) 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. MINUS(s(x), s(y)) -> MINUS(p(s(x)), p(s(y))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( MINUS_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( p_1(x_1) ) = max{0, x_1 - 2} POL( s_1(x_1) ) = 2x_1 + 1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: p(s(s(x))) -> s(p(s(x))) ---------------------------------------- (23) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) The set Q consists of the following terms: p(s(s(x0))) 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 ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(x, plus(y, z)) -> MINUS(x, y) MINUS(x, plus(y, z)) -> MINUS(minus(x, y), z) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) minus(x, 0) -> x minus(0, y) -> 0 minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) The set Q consists of the following terms: p(s(s(x0))) minus(x0, 0) minus(0, x0) minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) 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(x, plus(y, z)) -> MINUS(x, y) The graph contains the following edges 1 >= 1, 2 > 2 *MINUS(x, plus(y, z)) -> MINUS(minus(x, y), z) The graph contains the following edges 2 > 2 ---------------------------------------- (28) YES ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(s(x), y) -> PLUS(y, minus(s(x), s(0))) The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) 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. ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(s(x), y) -> PLUS(y, minus(s(x), s(0))) The TRS R consists of the following rules: minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, 0) -> x minus(0, y) -> 0 p(s(s(x))) -> s(p(s(x))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(s(x), y) -> PLUS(y, minus(s(x), s(0))) The TRS R consists of the following rules: minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, 0) -> x minus(0, y) -> 0 p(s(s(x))) -> s(p(s(x))) The set Q consists of the following terms: minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) minus(x0, 0) minus(0, x0) p(s(s(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: minus(x, plus(y, z)) -> minus(minus(x, y), z) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(minus(x_1, x_2)) = x_1 + x_2 POL(p(x_1)) = x_1 POL(plus(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(s(x_1)) = x_1 ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(s(x), y) -> PLUS(y, minus(s(x), s(0))) The TRS R consists of the following rules: minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) p(s(s(x))) -> s(p(s(x))) minus(x, 0) -> x minus(0, y) -> 0 The set Q consists of the following terms: minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) minus(x0, 0) minus(0, x0) p(s(s(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule PLUS(s(x), y) -> PLUS(y, minus(s(x), s(0))) at position [1] we obtained the following new rules [LPAR04]: (PLUS(s(x), y) -> PLUS(y, minus(p(s(x)), p(s(0)))),PLUS(s(x), y) -> PLUS(y, minus(p(s(x)), p(s(0))))) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(s(x), y) -> PLUS(y, minus(p(s(x)), p(s(0)))) The TRS R consists of the following rules: minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) p(s(s(x))) -> s(p(s(x))) minus(x, 0) -> x minus(0, y) -> 0 The set Q consists of the following terms: minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) minus(x0, 0) minus(0, x0) p(s(s(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: PLUS(s(x), y) -> PLUS(y, minus(p(s(x)), p(s(0)))) The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) minus(0, y) -> 0 The set Q consists of the following terms: minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) minus(x0, 0) minus(0, x0) p(s(s(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. PLUS(s(x), y) -> PLUS(y, minus(p(s(x)), p(s(0)))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( PLUS_2(x_1, x_2) ) = x_1 + x_2 + 2 POL( minus_2(x_1, x_2) ) = max{0, -2} POL( p_1(x_1) ) = max{0, -2} POL( s_1(x_1) ) = 2 POL( 0 ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus(0, y) -> 0 ---------------------------------------- (41) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: p(s(s(x))) -> s(p(s(x))) minus(0, y) -> 0 The set Q consists of the following terms: minus(x0, plus(x1, x2)) minus(s(x0), s(x1)) minus(x0, 0) minus(0, x0) p(s(s(x0))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (43) YES ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: DIV(plus(x, y), z) -> DIV(x, z) DIV(s(x), s(y)) -> DIV(minus(x, y), s(y)) DIV(plus(x, y), z) -> DIV(y, z) The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. DIV(plus(x, y), z) -> DIV(x, z) DIV(plus(x, y), z) -> DIV(y, z) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. DIV(x1, x2) = x1 plus(x1, x2) = plus(x1, x2) s(x1) = x1 minus(x1, x2) = x1 0 = 0 p(x1) = p Knuth-Bendix order [KBO] with precedence:trivial and weight map: 0=2 p=1 plus_2=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus(x, 0) -> x minus(0, y) -> 0 minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) p(s(s(x))) -> s(p(s(x))) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: DIV(s(x), s(y)) -> DIV(minus(x, y), s(y)) The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. DIV(s(x), s(y)) -> DIV(minus(x, y), s(y)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. DIV(x1, x2) = x1 s(x1) = s(x1) minus(x1, x2) = x1 0 = 0 p(x1) = x1 Knuth-Bendix order [KBO] with precedence:trivial and weight map: s_1=1 0=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus(x, 0) -> x minus(0, y) -> 0 minus(x, plus(y, z)) -> minus(minus(x, y), z) minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) p(s(s(x))) -> s(p(s(x))) ---------------------------------------- (48) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: minus(x, 0) -> x minus(0, y) -> 0 minus(s(x), s(y)) -> minus(p(s(x)), p(s(y))) minus(x, plus(y, z)) -> minus(minus(x, y), z) p(s(s(x))) -> s(p(s(x))) p(0) -> s(s(0)) div(s(x), s(y)) -> s(div(minus(x, y), s(y))) div(plus(x, y), z) -> plus(div(x, z), div(y, z)) plus(0, y) -> y plus(s(x), y) -> s(plus(y, minus(s(x), s(0)))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (50) YES