/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) AAECC Innermost [EQUIVALENT, 0 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 26 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) QDPSizeChangeProof [EQUIVALENT, 0 ms] (27) YES (28) QDP (29) UsableRulesProof [EQUIVALENT, 0 ms] (30) QDP (31) QReductionProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) QDP (45) TransformationProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 0 ms] (48) QDP (49) TransformationProof [EQUIVALENT, 0 ms] (50) QDP (51) TransformationProof [EQUIVALENT, 0 ms] (52) QDP (53) TransformationProof [EQUIVALENT, 0 ms] (54) QDP (55) DependencyGraphProof [EQUIVALENT, 0 ms] (56) QDP (57) TransformationProof [EQUIVALENT, 0 ms] (58) QDP (59) DependencyGraphProof [EQUIVALENT, 0 ms] (60) QDP (61) TransformationProof [EQUIVALENT, 0 ms] (62) QDP (63) DependencyGraphProof [EQUIVALENT, 0 ms] (64) AND (65) QDP (66) UsableRulesProof [EQUIVALENT, 0 ms] (67) QDP (68) QReductionProof [EQUIVALENT, 0 ms] (69) QDP (70) TransformationProof [EQUIVALENT, 0 ms] (71) QDP (72) DependencyGraphProof [EQUIVALENT, 0 ms] (73) QDP (74) UsableRulesProof [EQUIVALENT, 0 ms] (75) QDP (76) QReductionProof [EQUIVALENT, 0 ms] (77) QDP (78) TransformationProof [EQUIVALENT, 0 ms] (79) QDP (80) UsableRulesProof [EQUIVALENT, 0 ms] (81) QDP (82) QReductionProof [EQUIVALENT, 0 ms] (83) QDP (84) TransformationProof [EQUIVALENT, 0 ms] (85) QDP (86) TransformationProof [EQUIVALENT, 0 ms] (87) QDP (88) TransformationProof [EQUIVALENT, 0 ms] (89) QDP (90) QDPSizeChangeProof [EQUIVALENT, 0 ms] (91) YES (92) QDP (93) TransformationProof [EQUIVALENT, 0 ms] (94) QDP (95) UsableRulesProof [EQUIVALENT, 0 ms] (96) QDP (97) QReductionProof [EQUIVALENT, 0 ms] (98) QDP (99) TransformationProof [EQUIVALENT, 0 ms] (100) QDP (101) DependencyGraphProof [EQUIVALENT, 0 ms] (102) QDP (103) UsableRulesProof [EQUIVALENT, 0 ms] (104) QDP (105) QReductionProof [EQUIVALENT, 0 ms] (106) QDP (107) TransformationProof [EQUIVALENT, 0 ms] (108) QDP (109) DependencyGraphProof [EQUIVALENT, 0 ms] (110) AND (111) QDP (112) UsableRulesProof [EQUIVALENT, 0 ms] (113) QDP (114) QReductionProof [EQUIVALENT, 0 ms] (115) QDP (116) TransformationProof [EQUIVALENT, 0 ms] (117) QDP (118) TransformationProof [EQUIVALENT, 0 ms] (119) QDP (120) QDPSizeChangeProof [EQUIVALENT, 0 ms] (121) YES (122) QDP (123) TransformationProof [EQUIVALENT, 0 ms] (124) QDP (125) TransformationProof [EQUIVALENT, 0 ms] (126) QDP (127) TransformationProof [EQUIVALENT, 0 ms] (128) QDP (129) TransformationProof [EQUIVALENT, 0 ms] (130) QDP (131) TransformationProof [EQUIVALENT, 0 ms] (132) QDP (133) TransformationProof [EQUIVALENT, 0 ms] (134) QDP (135) QDPSizeChangeProof [EQUIVALENT, 0 ms] (136) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The TRS R 2 is cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) The signature Sigma is {cond1_3, cond2_3, cond3_3} ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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) -> COND2(gr(x, y), x, y) COND1(true, x, y) -> GR(x, y) COND2(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND2(true, x, y) -> GR(add(x, y), 0) COND2(true, x, y) -> ADD(x, y) COND2(true, x, y) -> P(x) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND2(false, x, y) -> EQ(x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(true, x, y) -> GR(add(x, y), 0) COND3(true, x, y) -> ADD(x, y) COND3(true, x, y) -> P(x) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND3(false, x, y) -> GR(add(x, y), 0) COND3(false, x, y) -> ADD(x, y) COND3(false, x, y) -> P(y) GR(s(x), s(y)) -> GR(x, y) ADD(s(x), y) -> ADD(x, y) EQ(s(x), s(y)) -> EQ(x, y) The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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 4 SCCs with 11 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x), s(y)) -> EQ(x, y) The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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: EQ(s(x), s(y)) -> EQ(x, y) R is empty. The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: EQ(s(x), s(y)) -> EQ(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: *EQ(s(x), s(y)) -> EQ(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: ADD(s(x), y) -> ADD(x, y) The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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: ADD(s(x), y) -> ADD(x, y) R is empty. The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) ---------------------------------------- (18) 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. ---------------------------------------- (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: *ADD(s(x), y) -> ADD(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: GR(s(x), s(y)) -> GR(x, y) The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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: GR(s(x), s(y)) -> GR(x, y) R is empty. The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(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) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) ---------------------------------------- (25) 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. ---------------------------------------- (26) 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 ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) The TRS R consists of the following rules: cond1(true, x, y) -> cond2(gr(x, y), x, y) cond2(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond2(false, x, y) -> cond3(eq(x, y), x, y) cond3(true, x, y) -> cond1(gr(add(x, y), 0), p(x), y) cond3(false, x, y) -> cond1(gr(add(x, y), 0), x, p(y)) 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)) eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) p(0) -> 0 p(s(x)) -> x The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) 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. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: cond1(true, x0, x1) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) add(0, x0) add(s(x0), x1) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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) cond2(true, x0, x1) cond2(false, x0, x1) cond3(true, x0, x1) cond3(false, x0, x1) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND2(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) at position [0] we obtained the following new rules [LPAR04]: (COND2(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0),COND2(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0)) (COND2(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1),COND2(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1)) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND2(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0) COND2(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND2(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0) at position [1] we obtained the following new rules [LPAR04]: (COND2(true, 0, x0) -> COND1(gr(x0, 0), 0, x0),COND2(true, 0, x0) -> COND1(gr(x0, 0), 0, x0)) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND2(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1) COND2(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND2(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1) at position [0] we obtained the following new rules [LPAR04]: (COND2(true, s(x0), x1) -> COND1(true, p(s(x0)), x1),COND2(true, s(x0), x1) -> COND1(true, p(s(x0)), x1)) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND2(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND2(true, s(x0), x1) -> COND1(true, p(s(x0)), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND2(true, s(x0), x1) -> COND1(true, p(s(x0)), x1) at position [1] we obtained the following new rules [LPAR04]: (COND2(true, s(x0), x1) -> COND1(true, x0, x1),COND2(true, s(x0), x1) -> COND1(true, x0, x1)) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, x, y) -> COND2(gr(x, y), x, y) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND2(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND2(true, s(x0), x1) -> COND1(true, x0, 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND1(true, x, y) -> COND2(gr(x, y), x, y) at position [0] we obtained the following new rules [LPAR04]: (COND1(true, 0, x0) -> COND2(false, 0, x0),COND1(true, 0, x0) -> COND2(false, 0, x0)) (COND1(true, s(x0), 0) -> COND2(true, s(x0), 0),COND1(true, s(x0), 0) -> COND2(true, s(x0), 0)) (COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)),COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND2(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, 0, x0) -> COND2(false, 0, x0) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(true, x, y) -> COND1(gr(add(x, y), 0), p(x), y) at position [0] we obtained the following new rules [LPAR04]: (COND3(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0),COND3(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0)) (COND3(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1),COND3(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1)) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND3(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0) COND3(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND3(true, 0, x0) -> COND1(gr(x0, 0), p(0), x0) at position [1] we obtained the following new rules [LPAR04]: (COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0),COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0)) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1) COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND3(true, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), p(s(x0)), x1) at position [0] we obtained the following new rules [LPAR04]: (COND3(true, s(x0), x1) -> COND1(true, p(s(x0)), x1),COND3(true, s(x0), x1) -> COND1(true, p(s(x0)), x1)) ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND3(true, s(x0), x1) -> COND1(true, p(s(x0)), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND3(true, s(x0), x1) -> COND1(true, p(s(x0)), x1) at position [1] we obtained the following new rules [LPAR04]: (COND3(true, s(x0), x1) -> COND1(true, x0, x1),COND3(true, s(x0), x1) -> COND1(true, x0, x1)) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, x, y) -> COND3(eq(x, y), x, y) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND3(true, s(x0), x1) -> COND1(true, x0, 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND2(false, x, y) -> COND3(eq(x, y), x, y) at position [0] we obtained the following new rules [LPAR04]: (COND2(false, 0, 0) -> COND3(true, 0, 0),COND2(false, 0, 0) -> COND3(true, 0, 0)) (COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)),COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0))) (COND2(false, s(x0), 0) -> COND3(false, s(x0), 0),COND2(false, s(x0), 0) -> COND3(false, s(x0), 0)) (COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)),COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1))) ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, x0) -> COND2(false, 0, x0) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND2(false, 0, 0) -> COND3(true, 0, 0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND2(false, s(x0), 0) -> COND3(false, s(x0), 0) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, 0) -> COND3(true, 0, 0) COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(true, 0, x0) -> COND1(gr(x0, 0), 0, x0) at position [0] we obtained the following new rules [LPAR04]: (COND3(true, 0, 0) -> COND1(false, 0, 0),COND3(true, 0, 0) -> COND1(false, 0, 0)) (COND3(true, 0, s(x0)) -> COND1(true, 0, s(x0)),COND3(true, 0, s(x0)) -> COND1(true, 0, s(x0))) ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, 0) -> COND3(true, 0, 0) COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(true, 0, 0) -> COND1(false, 0, 0) COND3(true, 0, s(x0)) -> COND1(true, 0, s(x0)) 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(false, x, y) -> COND1(gr(add(x, y), 0), x, p(y)) at position [0] we obtained the following new rules [LPAR04]: (COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0)),COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0))) (COND3(false, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), s(x0), p(x1)),COND3(false, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), s(x0), p(x1))) ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0)) COND3(false, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), s(x0), p(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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (64) Complex Obligation (AND) ---------------------------------------- (65) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) 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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (66) 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. ---------------------------------------- (67) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (68) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true 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. ---------------------------------------- (70) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(false, 0, x0) -> COND1(gr(x0, 0), 0, p(x0)) at position [0] we obtained the following new rules [LPAR04]: (COND3(false, 0, 0) -> COND1(false, 0, p(0)),COND3(false, 0, 0) -> COND1(false, 0, p(0))) (COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0))),COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0)))) ---------------------------------------- (71) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, x0) -> COND2(false, 0, x0) COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, 0, 0) -> COND1(false, 0, p(0)) COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0))) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true 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. ---------------------------------------- (72) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (73) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0))) COND1(true, 0, x0) -> COND2(false, 0, x0) The TRS R consists of the following rules: gr(0, x) -> false gr(s(x), 0) -> true 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. ---------------------------------------- (74) 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. ---------------------------------------- (75) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0))) COND1(true, 0, x0) -> COND2(false, 0, x0) The TRS R consists of the following rules: 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. ---------------------------------------- (76) 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]. gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) ---------------------------------------- (77) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0))) COND1(true, 0, x0) -> COND2(false, 0, x0) The TRS R consists of the following rules: p(s(x)) -> x The set Q consists of the following terms: p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (78) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND3(false, 0, s(x0)) -> COND1(true, 0, p(s(x0))) at position [2] we obtained the following new rules [LPAR04]: (COND3(false, 0, s(x0)) -> COND1(true, 0, x0),COND3(false, 0, s(x0)) -> COND1(true, 0, x0)) ---------------------------------------- (79) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND3(false, 0, s(x0)) -> COND1(true, 0, x0) The TRS R consists of the following rules: p(s(x)) -> x The set Q consists of the following terms: p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (80) 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. ---------------------------------------- (81) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND3(false, 0, s(x0)) -> COND1(true, 0, x0) R is empty. The set Q consists of the following terms: p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (82) 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)) ---------------------------------------- (83) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND1(true, 0, x0) -> COND2(false, 0, x0) COND3(false, 0, s(x0)) -> COND1(true, 0, x0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (84) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND1(true, 0, x0) -> COND2(false, 0, x0) we obtained the following new rules [LPAR04]: (COND1(true, 0, s(y_0)) -> COND2(false, 0, s(y_0)),COND1(true, 0, s(y_0)) -> COND2(false, 0, s(y_0))) ---------------------------------------- (85) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND3(false, 0, s(x0)) -> COND1(true, 0, x0) COND1(true, 0, s(y_0)) -> COND2(false, 0, s(y_0)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (86) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND3(false, 0, s(x0)) -> COND1(true, 0, x0) we obtained the following new rules [LPAR04]: (COND3(false, 0, s(s(y_0))) -> COND1(true, 0, s(y_0)),COND3(false, 0, s(s(y_0))) -> COND1(true, 0, s(y_0))) ---------------------------------------- (87) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) COND1(true, 0, s(y_0)) -> COND2(false, 0, s(y_0)) COND3(false, 0, s(s(y_0))) -> COND1(true, 0, s(y_0)) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (88) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND2(false, 0, s(x0)) -> COND3(false, 0, s(x0)) we obtained the following new rules [LPAR04]: (COND2(false, 0, s(s(y_0))) -> COND3(false, 0, s(s(y_0))),COND2(false, 0, s(s(y_0))) -> COND3(false, 0, s(s(y_0)))) ---------------------------------------- (89) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, 0, s(y_0)) -> COND2(false, 0, s(y_0)) COND3(false, 0, s(s(y_0))) -> COND1(true, 0, s(y_0)) COND2(false, 0, s(s(y_0))) -> COND3(false, 0, s(s(y_0))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (90) 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))) -> COND3(false, 0, s(s(y_0))) The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3 *COND3(false, 0, s(s(y_0))) -> COND1(true, 0, s(y_0)) The graph contains the following edges 2 >= 2, 3 > 3 *COND1(true, 0, s(y_0)) -> COND2(false, 0, s(y_0)) The graph contains the following edges 2 >= 2, 3 >= 3 ---------------------------------------- (91) YES ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), s(x0), p(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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND3(false, s(x0), x1) -> COND1(gr(s(add(x0, x1)), 0), s(x0), p(x1)) at position [0] we obtained the following new rules [LPAR04]: (COND3(false, s(x0), x1) -> COND1(true, s(x0), p(x1)),COND3(false, s(x0), x1) -> COND1(true, s(x0), p(x1))) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(x0), x1) -> COND1(true, s(x0), p(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 p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) 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. ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(x0), x1) -> COND1(true, s(x0), p(x1)) The TRS R consists of the following rules: p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) 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) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) 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) ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(x0), x1) -> COND1(true, s(x0), p(x1)) The TRS R consists of the following rules: p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (99) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND3(false, s(x0), x1) -> COND1(true, s(x0), p(x1)) at position [2] we obtained the following new rules [LPAR04]: (COND3(false, s(y0), 0) -> COND1(true, s(y0), 0),COND3(false, s(y0), 0) -> COND1(true, s(y0), 0)) (COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0),COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0)) ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(y0), 0) -> COND1(true, s(y0), 0) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) The TRS R consists of the following rules: p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (101) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) The TRS R consists of the following rules: p(0) -> 0 p(s(x)) -> x eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (103) 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. ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) p(0) p(s(x0)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (105) 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)) ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(x0), x1) -> COND1(true, x0, x1) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (107) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND2(true, s(x0), x1) -> COND1(true, x0, x1) we obtained the following new rules [LPAR04]: (COND2(true, s(z0), 0) -> COND1(true, z0, 0),COND2(true, s(z0), 0) -> COND1(true, z0, 0)) (COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)),COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1))) ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) COND2(true, s(z0), 0) -> COND1(true, z0, 0) COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (110) Complex Obligation (AND) ---------------------------------------- (111) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(z0), 0) -> COND1(true, z0, 0) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (112) 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. ---------------------------------------- (113) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(z0), 0) -> COND1(true, z0, 0) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) R is empty. The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (114) 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]. gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) ---------------------------------------- (115) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(z0), 0) -> COND1(true, z0, 0) COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (116) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND2(true, s(z0), 0) -> COND1(true, z0, 0) we obtained the following new rules [LPAR04]: (COND2(true, s(s(y_0)), 0) -> COND1(true, s(y_0), 0),COND2(true, s(s(y_0)), 0) -> COND1(true, s(y_0), 0)) ---------------------------------------- (117) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) COND2(true, s(s(y_0)), 0) -> COND1(true, s(y_0), 0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (118) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND1(true, s(x0), 0) -> COND2(true, s(x0), 0) we obtained the following new rules [LPAR04]: (COND1(true, s(s(y_0)), 0) -> COND2(true, s(s(y_0)), 0),COND1(true, s(s(y_0)), 0) -> COND2(true, s(s(y_0)), 0)) ---------------------------------------- (119) Obligation: Q DP problem: The TRS P consists of the following rules: COND2(true, s(s(y_0)), 0) -> COND1(true, s(y_0), 0) COND1(true, s(s(y_0)), 0) -> COND2(true, s(s(y_0)), 0) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (120) 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: *COND1(true, s(s(y_0)), 0) -> COND2(true, s(s(y_0)), 0) The graph contains the following edges 1 >= 1, 2 >= 2, 3 >= 3 *COND2(true, s(s(y_0)), 0) -> COND1(true, s(y_0), 0) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 ---------------------------------------- (121) YES ---------------------------------------- (122) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(x0), x1) -> COND1(true, x0, x1) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (123) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND3(true, s(x0), x1) -> COND1(true, x0, x1) we obtained the following new rules [LPAR04]: (COND3(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)),COND3(true, s(z0), s(z1)) -> COND1(true, z0, s(z1))) ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) COND3(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (125) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND3(false, s(y0), s(x0)) -> COND1(true, s(y0), x0) we obtained the following new rules [LPAR04]: (COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)),COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1))) ---------------------------------------- (126) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) COND3(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (127) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND2(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) we obtained the following new rules [LPAR04]: (COND2(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)),COND2(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1))) ---------------------------------------- (128) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)) COND2(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (129) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND3(true, s(z0), s(z1)) -> COND1(true, z0, s(z1)) we obtained the following new rules [LPAR04]: (COND3(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)),COND3(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1))) ---------------------------------------- (130) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)) COND2(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) COND3(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (131) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND2(false, s(x0), s(x1)) -> COND3(eq(x0, x1), s(x0), s(x1)) we obtained the following new rules [LPAR04]: (COND2(false, s(x0), s(s(y_2))) -> COND3(eq(x0, s(y_2)), s(x0), s(s(y_2))),COND2(false, s(x0), s(s(y_2))) -> COND3(eq(x0, s(y_2)), s(x0), s(s(y_2)))) (COND2(false, s(s(y_1)), s(x1)) -> COND3(eq(s(y_1), x1), s(s(y_1)), s(x1)),COND2(false, s(s(y_1)), s(x1)) -> COND3(eq(s(y_1), x1), s(s(y_1)), s(x1))) ---------------------------------------- (132) Obligation: Q DP problem: The TRS P consists of the following rules: COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)) COND2(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) COND3(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) COND2(false, s(x0), s(s(y_2))) -> COND3(eq(x0, s(y_2)), s(x0), s(s(y_2))) COND2(false, s(s(y_1)), s(x1)) -> COND3(eq(s(y_1), x1), s(s(y_1)), s(x1)) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (133) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND1(true, s(x0), s(x1)) -> COND2(gr(x0, x1), s(x0), s(x1)) we obtained the following new rules [LPAR04]: (COND1(true, s(s(y_1)), s(x1)) -> COND2(gr(s(y_1), x1), s(s(y_1)), s(x1)),COND1(true, s(s(y_1)), s(x1)) -> COND2(gr(s(y_1), x1), s(s(y_1)), s(x1))) (COND1(true, s(x0), s(s(y_2))) -> COND2(gr(x0, s(y_2)), s(x0), s(s(y_2))),COND1(true, s(x0), s(s(y_2))) -> COND2(gr(x0, s(y_2)), s(x0), s(s(y_2)))) ---------------------------------------- (134) Obligation: Q DP problem: The TRS P consists of the following rules: COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)) COND2(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) COND3(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) COND2(false, s(x0), s(s(y_2))) -> COND3(eq(x0, s(y_2)), s(x0), s(s(y_2))) COND2(false, s(s(y_1)), s(x1)) -> COND3(eq(s(y_1), x1), s(s(y_1)), s(x1)) COND1(true, s(s(y_1)), s(x1)) -> COND2(gr(s(y_1), x1), s(s(y_1)), s(x1)) COND1(true, s(x0), s(s(y_2))) -> COND2(gr(x0, s(y_2)), s(x0), s(s(y_2))) The TRS R consists of the following rules: eq(0, 0) -> true eq(0, s(x)) -> false eq(s(x), 0) -> false eq(s(x), s(y)) -> eq(x, y) gr(0, x) -> false gr(s(x), 0) -> true gr(s(x), s(y)) -> gr(x, y) The set Q consists of the following terms: gr(0, x0) gr(s(x0), 0) gr(s(x0), s(x1)) eq(0, 0) eq(0, s(x0)) eq(s(x0), 0) eq(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (135) 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(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 *COND1(true, s(s(y_1)), s(x1)) -> COND2(gr(s(y_1), x1), s(s(y_1)), s(x1)) The graph contains the following edges 2 >= 2, 3 >= 3 *COND1(true, s(x0), s(s(y_2))) -> COND2(gr(x0, s(y_2)), s(x0), s(s(y_2))) The graph contains the following edges 2 >= 2, 3 >= 3 *COND2(false, s(x0), s(s(y_2))) -> COND3(eq(x0, s(y_2)), s(x0), s(s(y_2))) The graph contains the following edges 2 >= 2, 3 >= 3 *COND2(false, s(s(y_1)), s(x1)) -> COND3(eq(s(y_1), x1), s(s(y_1)), s(x1)) The graph contains the following edges 2 >= 2, 3 >= 3 *COND3(false, s(x0), s(s(y_1))) -> COND1(true, s(x0), s(y_1)) The graph contains the following edges 2 >= 2, 3 > 3 *COND3(true, s(s(y_0)), s(x1)) -> COND1(true, s(y_0), s(x1)) The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3 ---------------------------------------- (136) YES