/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) AAECC Innermost [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 30 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QReductionProof [EQUIVALENT, 0 ms] (25) QDP (26) TransformationProof [EQUIVALENT, 0 ms] (27) QDP (28) TransformationProof [EQUIVALENT, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) TransformationProof [EQUIVALENT, 0 ms] (33) QDP (34) DependencyGraphProof [EQUIVALENT, 0 ms] (35) QDP (36) TransformationProof [EQUIVALENT, 0 ms] (37) QDP (38) TransformationProof [EQUIVALENT, 0 ms] (39) QDP (40) TransformationProof [EQUIVALENT, 0 ms] (41) QDP (42) TransformationProof [EQUIVALENT, 0 ms] (43) QDP (44) DependencyGraphProof [EQUIVALENT, 0 ms] (45) QDP (46) TransformationProof [EQUIVALENT, 0 ms] (47) QDP (48) DependencyGraphProof [EQUIVALENT, 0 ms] (49) QDP (50) TransformationProof [EQUIVALENT, 0 ms] (51) QDP (52) DependencyGraphProof [EQUIVALENT, 0 ms] (53) AND (54) QDP (55) UsableRulesProof [EQUIVALENT, 0 ms] (56) QDP (57) QReductionProof [EQUIVALENT, 0 ms] (58) QDP (59) TransformationProof [EQUIVALENT, 0 ms] (60) QDP (61) UsableRulesProof [EQUIVALENT, 0 ms] (62) QDP (63) TransformationProof [EQUIVALENT, 0 ms] (64) QDP (65) UsableRulesProof [EQUIVALENT, 0 ms] (66) QDP (67) QReductionProof [EQUIVALENT, 0 ms] (68) QDP (69) TransformationProof [EQUIVALENT, 0 ms] (70) QDP (71) TransformationProof [EQUIVALENT, 0 ms] (72) QDP (73) TransformationProof [EQUIVALENT, 0 ms] (74) QDP (75) QDPSizeChangeProof [EQUIVALENT, 0 ms] (76) YES (77) QDP (78) UsableRulesProof [EQUIVALENT, 0 ms] (79) QDP (80) QReductionProof [EQUIVALENT, 0 ms] (81) QDP (82) QDPSizeChangeProof [EQUIVALENT, 0 ms] (83) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x Q is empty. ---------------------------------------- (1) AAECC Innermost (EQUIVALENT) We have applied [NOC,AAECCNOC] to switch to innermost. The TRS R 1 is gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x The TRS R 2 is cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) The signature Sigma is {cond1_4, cond2_4, cond3_4} ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND1(true, x, y, z) -> GR(x, 0) COND2(true, x, y, z) -> COND1(gr(add(x, y), z), p(x), y, z) COND2(true, x, y, z) -> GR(add(x, y), z) COND2(true, x, y, z) -> ADD(x, y) COND2(true, x, y, z) -> P(x) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND2(false, x, y, z) -> GR(y, 0) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(true, x, y, z) -> GR(add(x, y), z) COND3(true, x, y, z) -> ADD(x, y) COND3(true, x, y, z) -> P(y) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND3(false, x, y, z) -> GR(add(x, y), z) COND3(false, x, y, z) -> ADD(x, y) GR(s(x), s(y)) -> GR(x, y) ADD(s(x), y) -> ADD(x, y) The TRS R consists of the following rules: cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 10 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: ADD(s(x), y) -> ADD(x, y) The TRS R consists of the following rules: cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) 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. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: ADD(s(x), y) -> ADD(x, y) R is empty. The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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]. cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: ADD(s(x), y) -> ADD(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) 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: *ADD(s(x), y) -> ADD(x, y) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: GR(s(x), s(y)) -> GR(x, y) The TRS R consists of the following rules: cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) 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. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: GR(s(x), s(y)) -> GR(x, y) R is empty. The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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]. cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: GR(s(x), s(y)) -> GR(x, y) 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: *GR(s(x), s(y)) -> GR(x, y) 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: COND2(true, x, y, z) -> COND1(gr(add(x, y), z), p(x), y, z) COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) The TRS R consists of the following rules: cond1(true, x, y, z) -> cond2(gr(x, 0), x, y, z) cond2(true, x, y, z) -> cond1(gr(add(x, y), z), p(x), y, z) cond2(false, x, y, z) -> cond3(gr(y, 0), x, y, z) cond3(true, x, y, z) -> cond1(gr(add(x, y), z), x, p(y), z) cond3(false, x, y, z) -> cond1(gr(add(x, y), z), x, y, z) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) add(0, x) -> x add(s(x), y) -> s(add(x, y)) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, x, y, z) -> COND1(gr(add(x, y), z), p(x), y, z) COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) 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]. cond1(true, x0, x1, x2) cond2(true, x0, x1, x2) cond2(false, x0, x1, x2) cond3(true, x0, x1, x2) cond3(false, x0, x1, x2) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, x, y, z) -> COND1(gr(add(x, y), z), p(x), y, z) COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND2(true, x, y, z) -> COND1(gr(add(x, y), z), p(x), y, z) at position [0] we obtained the following new rules [LPAR04]: (COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), p(0), x0, y2),COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), p(0), x0, y2)) (COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), p(s(x0)), x1, y2),COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), p(s(x0)), x1, y2)) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), p(0), x0, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), p(s(x0)), x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), p(0), x0, y2) at position [1] we obtained the following new rules [LPAR04]: (COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2),COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2)) ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), p(s(x0)), x1, y2) COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), p(s(x0)), x1, y2) at position [1] we obtained the following new rules [LPAR04]: (COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2),COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2)) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND1(true, x, y, z) -> COND2(gr(x, 0), x, y, z) at position [0] we obtained the following new rules [LPAR04]: (COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2),COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2)) (COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2),COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2)) ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND2(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(true, x, y, z) -> COND1(gr(add(x, y), z), x, p(y), z) at position [0] we obtained the following new rules [LPAR04]: (COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2),COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2)) (COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2),COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2)) ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND2(false, x, y, z) -> COND3(gr(y, 0), x, y, z) at position [0] we obtained the following new rules [LPAR04]: (COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2),COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2)) (COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2),COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2)) ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2) COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(false, x, y, z) -> COND1(gr(add(x, y), z), x, y, z) at position [0] we obtained the following new rules [LPAR04]: (COND3(false, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2),COND3(false, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2)) (COND3(false, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), x1, y2),COND3(false, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), x1, y2)) ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2) COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) COND3(false, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2) COND3(false, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(false, 0, x0, y2) -> COND1(gr(x0, y2), 0, x0, y2) at position [0] we obtained the following new rules [LPAR04]: (COND3(false, 0, 0, x0) -> COND1(false, 0, 0, x0),COND3(false, 0, 0, x0) -> COND1(false, 0, 0, x0)) (COND3(false, 0, s(x0), 0) -> COND1(true, 0, s(x0), 0),COND3(false, 0, s(x0), 0) -> COND1(true, 0, s(x0), 0)) (COND3(false, 0, s(x0), s(x1)) -> COND1(gr(x0, x1), 0, s(x0), s(x1)),COND3(false, 0, s(x0), s(x1)) -> COND1(gr(x0, x1), 0, s(x0), s(x1))) ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2) COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) COND3(false, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), x1, y2) COND3(false, 0, 0, x0) -> COND1(false, 0, 0, x0) COND3(false, 0, s(x0), 0) -> COND1(true, 0, s(x0), 0) COND3(false, 0, s(x0), s(x1)) -> COND1(gr(x0, x1), 0, s(x0), s(x1)) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2) COND3(false, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), x1, y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND2(false, y0, 0, y2) -> COND3(false, y0, 0, y2) we obtained the following new rules [LPAR04]: (COND2(false, 0, 0, z1) -> COND3(false, 0, 0, z1),COND2(false, 0, 0, z1) -> COND3(false, 0, 0, z1)) ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(false, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), x1, y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) COND2(false, 0, 0, z1) -> COND3(false, 0, 0, z1) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND2(false, y0, s(x0), y2) -> COND3(true, y0, s(x0), y2) we obtained the following new rules [LPAR04]: (COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1),COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1)) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND3(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), s(x0), p(x1), y2) COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (52) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (53) Complex Obligation (AND) ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) 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. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) 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]. add(0, x0) add(s(x0), x1) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND3(true, 0, x0, y2) -> COND1(gr(x0, y2), 0, p(x0), y2) we obtained the following new rules [LPAR04]: (COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, p(s(z0)), z1),COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, p(s(z0)), z1)) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, p(s(z0)), z1) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) 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. ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, p(s(z0)), z1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(s(x)) -> x gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, p(s(z0)), z1) at position [2] we obtained the following new rules [LPAR04]: (COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1),COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1)) ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(s(x)) -> x gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) 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. ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) 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]. p(0) p(s(x0)) ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND1(true, 0, y1, y2) -> COND2(false, 0, y1, y2) we obtained the following new rules [LPAR04]: (COND1(true, 0, s(y_0), x1) -> COND2(false, 0, s(y_0), x1),COND1(true, 0, s(y_0), x1) -> COND2(false, 0, s(y_0), x1)) ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1) COND1(true, 0, s(y_0), x1) -> COND2(false, 0, s(y_0), x1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND3(true, 0, s(z0), z1) -> COND1(gr(s(z0), z1), 0, z0, z1) we obtained the following new rules [LPAR04]: (COND3(true, 0, s(s(y_1)), x1) -> COND1(gr(s(s(y_1)), x1), 0, s(y_1), x1),COND3(true, 0, s(s(y_1)), x1) -> COND1(gr(s(s(y_1)), x1), 0, s(y_1), x1)) ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) COND1(true, 0, s(y_0), x1) -> COND2(false, 0, s(y_0), x1) COND3(true, 0, s(s(y_1)), x1) -> COND1(gr(s(s(y_1)), x1), 0, s(y_1), x1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND2(false, 0, s(x1), z1) -> COND3(true, 0, s(x1), z1) we obtained the following new rules [LPAR04]: (COND2(false, 0, s(s(y_0)), x1) -> COND3(true, 0, s(s(y_0)), x1),COND2(false, 0, s(s(y_0)), x1) -> COND3(true, 0, s(s(y_0)), x1)) ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, s(y_0), x1) -> COND2(false, 0, s(y_0), x1) COND3(true, 0, s(s(y_1)), x1) -> COND1(gr(s(s(y_1)), x1), 0, s(y_1), x1) COND2(false, 0, s(s(y_0)), x1) -> COND3(true, 0, s(s(y_0)), x1) The TRS R consists of the following rules: gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) 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: *COND2(false, 0, s(s(y_0)), x1) -> COND3(true, 0, s(s(y_0)), x1) The graph contains the following edges 2 >= 2, 3 >= 3, 4 >= 4 *COND3(true, 0, s(s(y_1)), x1) -> COND1(gr(s(s(y_1)), x1), 0, s(y_1), x1) The graph contains the following edges 2 >= 2, 3 > 3, 4 >= 4 *COND1(true, 0, s(y_0), x1) -> COND2(false, 0, s(y_0), x1) The graph contains the following edges 2 >= 2, 3 >= 3, 4 >= 4 ---------------------------------------- (76) YES ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) 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. ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) 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]. p(0) p(s(x0)) ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) The TRS R consists of the following rules: add(0, x) -> x add(s(x), y) -> s(add(x, y)) gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) gr(0, x) -> false The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) 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: *COND2(true, s(x0), x1, y2) -> COND1(gr(s(add(x0, x1)), y2), x0, x1, y2) The graph contains the following edges 2 > 2, 3 >= 3, 4 >= 4 *COND1(true, s(x0), y1, y2) -> COND2(true, s(x0), y1, y2) The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3, 4 >= 4 ---------------------------------------- (83) YES