YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given ETRS could be proven: (0) ETRS (1) EquationalDependencyPairsProof [EQUIVALENT, 0 ms] (2) EDP (3) EDependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) EDP (6) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (7) EDP (8) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (9) EDP (10) PisEmptyProof [EQUIVALENT, 0 ms] (11) YES (12) EDP (13) EUsableRulesReductionPairsProof [EQUIVALENT, 9 ms] (14) EDP (15) ERuleRemovalProof [EQUIVALENT, 0 ms] (16) EDP (17) EDPPoloProof [EQUIVALENT, 8 ms] (18) EDP (19) PisEmptyProof [EQUIVALENT, 0 ms] (20) YES (21) EDP (22) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (23) EDP (24) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (25) EDP (26) PisEmptyProof [EQUIVALENT, 0 ms] (27) YES (28) EDP (29) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (30) EDP (31) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (32) EDP (33) ERuleRemovalProof [EQUIVALENT, 17 ms] (34) EDP (35) ERuleRemovalProof [EQUIVALENT, 0 ms] (36) EDP (37) EUsableRulesReductionPairsProof [EQUIVALENT, 10 ms] (38) EDP (39) EDPProblemToQDPProblemProof [EQUIVALENT, 0 ms] (40) QDP (41) UsableRulesProof [EQUIVALENT, 0 ms] (42) QDP (43) MRRProof [EQUIVALENT, 7 ms] (44) QDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) TRUE (47) EDP (48) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (49) EDP (50) EUsableRulesReductionPairsProof [EQUIVALENT, 0 ms] (51) EDP (52) PisEmptyProof [EQUIVALENT, 0 ms] (53) YES (54) EDP (55) ESharpUsableEquationsProof [EQUIVALENT, 0 ms] (56) EDP (57) EDPPoloProof [EQUIVALENT, 0 ms] (58) EDP (59) PisEmptyProof [EQUIVALENT, 0 ms] (60) YES ---------------------------------------- (0) Obligation: Equational rewrite system: The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) ---------------------------------------- (1) EquationalDependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,DA_STEIN] we result in the following initial EDP problem: The TRS P consists of the following rules: MINUS(s(x), s(y)) -> MINUS(x, y) MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) MINUS(minus(x, y), z) -> PLUS(y, z) QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) QUOT(s(x), s(y)) -> MINUS(x, y) PLUS(s(x), y) -> PLUS(x, y) APP(cons(x, l), k) -> APP(l, k) SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) SUM(cons(x, cons(y, l))) -> PLUS(x, y) SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) SUM(app(l, cons(x, cons(y, k)))) -> APP(l, sum(cons(x, cons(y, k)))) SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k))) PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) PLUS(plus(s(x), y), ext) -> PLUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (2) Obligation: The TRS P consists of the following rules: MINUS(s(x), s(y)) -> MINUS(x, y) MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) MINUS(minus(x, y), z) -> PLUS(y, z) QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) QUOT(s(x), s(y)) -> MINUS(x, y) PLUS(s(x), y) -> PLUS(x, y) APP(cons(x, l), k) -> APP(l, k) SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) SUM(cons(x, cons(y, l))) -> PLUS(x, y) SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) SUM(app(l, cons(x, cons(y, k)))) -> APP(l, sum(cons(x, cons(y, k)))) SUM(app(l, cons(x, cons(y, k)))) -> SUM(cons(x, cons(y, k))) PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) PLUS(plus(s(x), y), ext) -> PLUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (3) EDependencyGraphProof (EQUIVALENT) The approximation of the Equational Dependency Graph [DA_STEIN] contains 6 SCCs with 5 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: The TRS P consists of the following rules: APP(cons(x, l), k) -> APP(l, k) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (6) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) ---------------------------------------- (7) Obligation: The TRS P consists of the following rules: APP(cons(x, l), k) -> APP(l, k) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (8) EUsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: APP(cons(x, l), k) -> APP(l, k) The following rules are removed from R: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The following equations are removed from E: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(APP(x_1, x_2)) = 3*x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + 3*x_2 ---------------------------------------- (9) Obligation: P is empty. R is empty. E is empty. E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (10) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: The TRS P consists of the following rules: PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) PLUS(s(x), y) -> PLUS(x, y) PLUS(plus(s(x), y), ext) -> PLUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (13) EUsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) No equations are removed from E. Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 ---------------------------------------- (14) Obligation: The TRS P consists of the following rules: PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) PLUS(s(x), y) -> PLUS(x, y) PLUS(plus(s(x), y), ext) -> PLUS(x, y) The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (15) ERuleRemovalProof (EQUIVALENT) By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. Strictly oriented dependency pairs: PLUS(s(x), y) -> PLUS(x, y) PLUS(plus(s(x), y), ext) -> PLUS(x, y) Used ordering: POLO with Polynomial interpretation [POLO]: POL(PLUS(x_1, x_2)) = 2*x_1 + 2*x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 1 + x_1 ---------------------------------------- (16) Obligation: The TRS P consists of the following rules: PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (17) EDPPoloProof (EQUIVALENT) We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. PLUS(plus(s(x), y), ext) -> PLUS(s(plus(x, y)), ext) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) We had to orient the following equations of E# equivalently. PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) With the implicit AFS we had to orient the following usable equations of E equivalently. plus(plus(x, y), z) == plus(x, plus(y, z)) plus(x, y) == plus(y, x) Used ordering: POLO with Polynomial interpretation [POLO]: POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(plus(x_1, x_2)) = 1 + x_1 + x_2 POL(s(x_1)) = 0 ---------------------------------------- (18) Obligation: P is empty. The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (19) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: The TRS P consists of the following rules: SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (22) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) ---------------------------------------- (23) Obligation: The TRS P consists of the following rules: SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (24) EUsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: SUM(cons(x, cons(y, l))) -> SUM(cons(plus(x, y), l)) The following rules are removed from R: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) No equations are removed from E. Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(SUM(x_1)) = x_1 POL(cons(x_1, x_2)) = 2 + x_1 + x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 3 + x_1 ---------------------------------------- (25) Obligation: P is empty. The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (26) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (27) YES ---------------------------------------- (28) Obligation: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (29) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) ---------------------------------------- (30) Obligation: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (31) EUsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y No equations are removed from E. Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(SUM(x_1)) = x_1 POL(app(x_1, x_2)) = 2*x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(nil) = 0 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 1 + x_1 POL(sum(x_1)) = x_1 ---------------------------------------- (32) Obligation: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) app(cons(x, l), k) -> cons(x, app(l, k)) plus(s(x), y) -> s(plus(x, y)) sum(cons(x, nil)) -> cons(x, nil) app(nil, k) -> k app(l, nil) -> l sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (33) ERuleRemovalProof (EQUIVALENT) By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. Strictly oriented rules of the TRS R: app(nil, k) -> k app(l, nil) -> l Used ordering: POLO with Polynomial interpretation [POLO]: POL(SUM(x_1)) = 2*x_1 POL(app(x_1, x_2)) = 2*x_1 + 2*x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(nil) = 2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(sum(x_1)) = x_1 ---------------------------------------- (34) Obligation: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) app(cons(x, l), k) -> cons(x, app(l, k)) plus(s(x), y) -> s(plus(x, y)) sum(cons(x, nil)) -> cons(x, nil) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (35) ERuleRemovalProof (EQUIVALENT) By using the rule removal processor [DA_STEIN] with the following polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this EDP problem can be strictly oriented. Strictly oriented rules of the TRS R: sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(SUM(x_1)) = 2*x_1 POL(app(x_1, x_2)) = x_1 + 2*x_2 POL(cons(x_1, x_2)) = 2 + x_1 + x_2 POL(nil) = 0 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(sum(x_1)) = x_1 ---------------------------------------- (36) Obligation: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) app(cons(x, l), k) -> cons(x, app(l, k)) plus(s(x), y) -> s(plus(x, y)) sum(cons(x, nil)) -> cons(x, nil) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (37) EUsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) The following equations are removed from E: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) Used ordering: POLO with Polynomial interpretation [POLO]: POL(SUM(x_1)) = 2*x_1 POL(app(x_1, x_2)) = 2*x_1 + 2*x_2 POL(cons(x_1, x_2)) = 2*x_1 + x_2 POL(nil) = 0 POL(sum(x_1)) = x_1 ---------------------------------------- (38) Obligation: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) E is empty. E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (39) EDPProblemToQDPProblemProof (EQUIVALENT) The EDP problem does not contain equations anymore, so we can transform it with the EDP to QDP problem processor [DA_STEIN] into a QDP problem. ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: app(cons(x, l), k) -> cons(x, app(l, k)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) MRRProof (EQUIVALENT) By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. Strictly oriented rules of the TRS R: app(cons(x, l), k) -> cons(x, app(l, k)) Used ordering: Polynomial interpretation [POLO]: POL(SUM(x_1)) = 2*x_1 POL(app(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(cons(x_1, x_2)) = 1 + x_1 + x_2 POL(sum(x_1)) = x_1 ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: SUM(app(l, cons(x, cons(y, k)))) -> SUM(app(l, sum(cons(x, cons(y, k))))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (46) TRUE ---------------------------------------- (47) Obligation: The TRS P consists of the following rules: MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) MINUS(s(x), s(y)) -> MINUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (48) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) ---------------------------------------- (49) Obligation: The TRS P consists of the following rules: MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) MINUS(s(x), s(y)) -> MINUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (50) EUsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules and equations with reduction pair processor [DA_STEIN] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules can be oriented non-strictly, the usable equations and the esharp equations can be oriented equivalently. All non-usable rules and equations are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. The following dependency pairs can be deleted: MINUS(minus(x, y), z) -> MINUS(x, plus(y, z)) MINUS(s(x), s(y)) -> MINUS(x, y) The following rules are removed from R: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) No equations are removed from E. Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(MINUS(x_1, x_2)) = 3*x_1 + 2*x_2 POL(minus(x_1, x_2)) = 2 + 3*x_1 + 3*x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = 3 + x_1 ---------------------------------------- (51) Obligation: P is empty. The TRS R consists of the following rules: plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) plus(s(x), y) -> s(plus(x, y)) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (52) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (53) YES ---------------------------------------- (54) Obligation: The TRS P consists of the following rules: QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) The set E# consists of the following equations: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (55) ESharpUsableEquationsProof (EQUIVALENT) We can delete the following equations of E# with the esharp usable equations processor[DA_STEIN]: PLUS(x, y) == PLUS(y, x) PLUS(plus(x, y), z) == PLUS(x, plus(y, z)) ---------------------------------------- (56) Obligation: The TRS P consists of the following rules: QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (57) EDPPoloProof (EQUIVALENT) We use the reduction pair processor [DA_STEIN] with a polynomial ordering [POLO]. All Dependency Pairs of this DP problem can be strictly oriented. QUOT(s(x), s(y)) -> QUOT(minus(x, y), s(y)) With the implicit AFS we had to orient the following set of usable rules of R non-strictly. minus(minus(x, y), z) -> minus(x, plus(y, z)) minus(s(x), s(y)) -> minus(x, y) minus(x, 0) -> x There is no equation of E#. With the implicit AFS there is no usable equation of E. Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(QUOT(x_1, x_2)) = x_1 POL(minus(x_1, x_2)) = x_1 POL(plus(x_1, x_2)) = 0 POL(s(x_1)) = 1 + 2*x_1 ---------------------------------------- (58) Obligation: P is empty. The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) minus(minus(x, y), z) -> minus(x, plus(y, z)) quot(0, s(y)) -> 0 quot(s(x), s(y)) -> s(quot(minus(x, y), s(y))) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) sum(cons(x, nil)) -> cons(x, nil) sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) sum(app(l, cons(x, cons(y, k)))) -> sum(app(l, sum(cons(x, cons(y, k))))) plus(plus(s(x), y), ext) -> plus(s(plus(x, y)), ext) The set E consists of the following equations: plus(x, y) == plus(y, x) plus(plus(x, y), z) == plus(x, plus(y, z)) E# is empty. We have to consider all minimal (P,E#,R,E)-chains ---------------------------------------- (59) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,E#,R,E) chain. ---------------------------------------- (60) YES