/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) DependencyPairsProof [EQUIVALENT, 21 ms] (2) QDP (3) DependencyGraphProof [EQUIVALENT, 0 ms] (4) AND (5) QDP (6) UsableRulesProof [EQUIVALENT, 0 ms] (7) QDP (8) ATransformationProof [EQUIVALENT, 0 ms] (9) QDP (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] (11) YES (12) QDP (13) UsableRulesProof [EQUIVALENT, 0 ms] (14) QDP (15) ATransformationProof [EQUIVALENT, 0 ms] (16) QDP (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] (18) YES (19) QDP (20) UsableRulesProof [EQUIVALENT, 0 ms] (21) QDP (22) MNOCProof [EQUIVALENT, 0 ms] (23) QDP (24) ATransformationProof [EQUIVALENT, 0 ms] (25) QDP (26) UsableRulesReductionPairsProof [EQUIVALENT, 4 ms] (27) QDP (28) PisEmptyProof [EQUIVALENT, 0 ms] (29) YES (30) QDP (31) UsableRulesProof [EQUIVALENT, 0 ms] (32) QDP (33) UsableRulesReductionPairsProof [EQUIVALENT, 16 ms] (34) QDP (35) MRRProof [EQUIVALENT, 0 ms] (36) QDP (37) MRRProof [EQUIVALENT, 13 ms] (38) QDP (39) DependencyGraphProof [EQUIVALENT, 0 ms] (40) TRUE (41) QDP (42) UsableRulesProof [EQUIVALENT, 0 ms] (43) QDP (44) MNOCProof [EQUIVALENT, 0 ms] (45) QDP (46) ATransformationProof [EQUIVALENT, 0 ms] (47) QDP (48) QDPSizeChangeProof [EQUIVALENT, 0 ms] (49) YES (50) QDP (51) QDPOrderProof [EQUIVALENT, 12 ms] (52) QDP (53) PisEmptyProof [EQUIVALENT, 0 ms] (54) YES (55) QDP (56) QDPSizeChangeProof [EQUIVALENT, 0 ms] (57) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. ---------------------------------------- (1) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (2) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y) APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(minus, x) APP'(app'(minus, app'(app'(minus, x), y)), z) -> APP'(app'(minus, x), app'(app'(plus, y), z)) APP'(app'(minus, app'(app'(minus, x), y)), z) -> APP'(app'(plus, y), z) APP'(app'(minus, app'(app'(minus, x), y)), z) -> APP'(plus, y) APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y)) APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(quot, app'(app'(minus, x), y)) APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y) APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(minus, x) APP'(app'(plus, app'(s, x)), y) -> APP'(s, app'(app'(plus, x), y)) APP'(app'(plus, app'(s, x)), y) -> APP'(app'(plus, x), y) APP'(app'(plus, app'(s, x)), y) -> APP'(plus, x) APP'(app'(app, app'(app'(cons, x), l)), k) -> APP'(app'(cons, x), app'(app'(app, l), k)) APP'(app'(app, app'(app'(cons, x), l)), k) -> APP'(app'(app, l), k) APP'(app'(app, app'(app'(cons, x), l)), k) -> APP'(app, l) APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(app'(cons, app'(app'(plus, x), y)), l) APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(cons, app'(app'(plus, x), y)) APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(app'(plus, x), y) APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(plus, x) APP'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> APP'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) APP'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> APP'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k)))) APP'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> APP'(sum, app'(app'(cons, x), app'(app'(cons, y), k))) APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(cons, app'(f, x)) APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(f, x) APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(app'(map, f), xs) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(app'(app'(filter2, app'(f, x)), f), x) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(app'(filter2, app'(f, x)), f) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(filter2, app'(f, x)) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(f, x) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(cons, x), app'(app'(filter, f), xs)) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(cons, x) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(filter, f), xs) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(filter, f) APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(app'(filter, f), xs) APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(filter, f) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (3) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 26 less nodes. ---------------------------------------- (4) Complex Obligation (AND) ---------------------------------------- (5) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(app, app'(app'(cons, x), l)), k) -> APP'(app'(app, l), k) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (6) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(app, app'(app'(cons, x), l)), k) -> APP'(app'(app, l), k) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: app(cons(x, l), k) -> app(l, k) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) 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: *app(cons(x, l), k) -> app(l, k) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (11) YES ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(plus, app'(s, x)), y) -> APP'(app'(plus, x), y) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) 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. ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(plus, app'(s, x)), y) -> APP'(app'(plus, x), y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: plus(s(x), y) -> plus(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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: *plus(s(x), y) -> plus(x, y) The graph contains the following edges 1 > 1, 2 >= 2 ---------------------------------------- (18) YES ---------------------------------------- (19) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (20) 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. ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) The TRS R consists of the following rules: app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> APP'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) The TRS R consists of the following rules: app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) The set Q consists of the following terms: app'(app'(plus, 0), x0) app'(app'(plus, app'(s, x0)), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (25) Obligation: Q DP problem: 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: plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) The set Q consists of the following terms: plus(0, x0) plus(s(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) UsableRulesReductionPairsProof (EQUIVALENT) By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 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: plus(0, y) -> y Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(sum(x_1)) = 2*x_1 ---------------------------------------- (27) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: plus(s(x), y) -> s(plus(x, y)) The set Q consists of the following terms: plus(0, x0) plus(s(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (29) YES ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> APP'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) 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. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> APP'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) The TRS R consists of the following rules: app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) UsableRulesReductionPairsProof (EQUIVALENT) First, we A-transformed [FROCOS05] the QDP-Problem. Then we obtain the following A-transformed DP problem. The pairs P are: sum1(app(l, cons(x, cons(y, k)))) -> sum1(app(l, sum(cons(x, cons(y, k))))) and the Q and R are: Q restricted rewrite system: The TRS R consists of the following rules: sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) app(nil, k) -> k app(l, nil) -> l app(cons(x, l), k) -> cons(x, app(l, k)) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) sum(cons(x, nil)) -> cons(x, nil) Q is empty. By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. No dependency pairs are removed. The following rules are removed from R: app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) Used ordering: POLO with Polynomial interpretation [POLO]: POL(0) = 0 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)) = x_1 POL(sum(x_1)) = x_1 POL(sum1(x_1)) = x_1 ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: sum1(app(l, cons(x, cons(y, k)))) -> sum1(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) app(nil, k) -> k app(l, nil) -> l 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) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) 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(nil, k) -> k app(l, nil) -> l Used ordering: Polynomial interpretation [POLO]: 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) = 2 POL(plus(x_1, x_2)) = x_1 + x_2 POL(s(x_1)) = x_1 POL(sum(x_1)) = x_1 POL(sum1(x_1)) = 2*x_1 ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: sum1(app(l, cons(x, cons(y, k)))) -> sum1(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) 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) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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: sum(cons(x, cons(y, l))) -> sum(cons(plus(x, y), l)) app(cons(x, l), k) -> cons(x, app(l, k)) Used ordering: Polynomial interpretation [POLO]: POL(app(x_1, x_2)) = 2*x_1 + 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 POL(sum1(x_1)) = 2*x_1 ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: sum1(app(l, cons(x, cons(y, k)))) -> sum1(app(l, sum(cons(x, cons(y, k))))) The TRS R consists of the following rules: plus(s(x), y) -> s(plus(x, y)) sum(cons(x, nil)) -> cons(x, nil) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (40) TRUE ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(minus, app'(app'(minus, x), y)), z) -> APP'(app'(minus, x), app'(app'(plus, y), z)) APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) 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. ---------------------------------------- (43) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(minus, app'(app'(minus, x), y)), z) -> APP'(app'(minus, x), app'(app'(plus, y), z)) APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y) The TRS R consists of the following rules: app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (44) MNOCProof (EQUIVALENT) We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. ---------------------------------------- (45) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(minus, app'(app'(minus, x), y)), z) -> APP'(app'(minus, x), app'(app'(plus, y), z)) APP'(app'(minus, app'(s, x)), app'(s, y)) -> APP'(app'(minus, x), y) The TRS R consists of the following rules: app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) The set Q consists of the following terms: app'(app'(plus, 0), x0) app'(app'(plus, app'(s, x0)), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (46) ATransformationProof (EQUIVALENT) We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: minus(minus1(x, y), z) -> minus(x, plus(y, z)) minus(s(x), s(y)) -> minus(x, y) The TRS R consists of the following rules: plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) The set Q consists of the following terms: plus(0, x0) plus(s(x0), x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *minus(minus1(x, y), z) -> minus(x, plus(y, z)) The graph contains the following edges 1 > 1 *minus(s(x), s(y)) -> minus(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (49) YES ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y)) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. Here, we combined the reduction pair processor with the A-transformation [FROCOS05] which results in the following intermediate Q-DP Problem. The a-transformed P is quot1(s(x), s(y)) -> quot1(minus(x, y), s(y)) The a-transformed usable rules are minus(x, 0) -> x minus(minus(x, y), z) -> minus(x, plus(y, z)) minus(s(x), s(y)) -> minus(x, y) plus(0, y) -> y plus(s(x), y) -> s(plus(x, y)) The following pairs can be oriented strictly and are deleted. APP'(app'(quot, app'(s, x)), app'(s, y)) -> APP'(app'(quot, app'(app'(minus, x), y)), app'(s, y)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. quot1(x1, x2) = quot1(x1) s(x1) = s(x1) minus(x1, x2) = minus(x1) 0 = 0 plus(x1, x2) = plus(x1, x2) Recursive path order with status [RPO]. Quasi-Precedence: 0 > [quot1_1, minus_1] plus_2 > s_1 > [quot1_1, minus_1] Status: quot1_1: multiset status s_1: multiset status minus_1: [1] 0: multiset status plus_2: multiset status The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) ---------------------------------------- (52) Obligation: Q DP problem: P is empty. The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (54) YES ---------------------------------------- (55) Obligation: Q DP problem: The TRS P consists of the following rules: APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(app'(map, f), xs) APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(f, x) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(filter, f), xs) APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(f, x) APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(app'(filter, f), xs) The TRS R consists of the following rules: app'(app'(minus, x), 0) -> x app'(app'(minus, app'(s, x)), app'(s, y)) -> app'(app'(minus, x), y) app'(app'(minus, app'(app'(minus, x), y)), z) -> app'(app'(minus, x), app'(app'(plus, y), z)) app'(app'(quot, 0), app'(s, y)) -> 0 app'(app'(quot, app'(s, x)), app'(s, y)) -> app'(s, app'(app'(quot, app'(app'(minus, x), y)), app'(s, y))) app'(app'(plus, 0), y) -> y app'(app'(plus, app'(s, x)), y) -> app'(s, app'(app'(plus, x), y)) app'(app'(app, nil), k) -> k app'(app'(app, l), nil) -> l app'(app'(app, app'(app'(cons, x), l)), k) -> app'(app'(cons, x), app'(app'(app, l), k)) app'(sum, app'(app'(cons, x), nil)) -> app'(app'(cons, x), nil) app'(sum, app'(app'(cons, x), app'(app'(cons, y), l))) -> app'(sum, app'(app'(cons, app'(app'(plus, x), y)), l)) app'(sum, app'(app'(app, l), app'(app'(cons, x), app'(app'(cons, y), k)))) -> app'(sum, app'(app'(app, l), app'(sum, app'(app'(cons, x), app'(app'(cons, y), k))))) app'(app'(map, f), nil) -> nil app'(app'(map, f), app'(app'(cons, x), xs)) -> app'(app'(cons, app'(f, x)), app'(app'(map, f), xs)) app'(app'(filter, f), nil) -> nil app'(app'(filter, f), app'(app'(cons, x), xs)) -> app'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) app'(app'(app'(app'(filter2, true), f), x), xs) -> app'(app'(cons, x), app'(app'(filter, f), xs)) app'(app'(app'(app'(filter2, false), f), x), xs) -> app'(app'(filter, f), xs) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (56) 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: *APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(f, x) The graph contains the following edges 1 > 1, 2 > 2 *APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(f, x) The graph contains the following edges 1 > 1, 2 > 2 *APP'(app'(map, f), app'(app'(cons, x), xs)) -> APP'(app'(map, f), xs) The graph contains the following edges 1 >= 1, 2 > 2 *APP'(app'(filter, f), app'(app'(cons, x), xs)) -> APP'(app'(app'(app'(filter2, app'(f, x)), f), x), xs) The graph contains the following edges 2 > 2 *APP'(app'(app'(app'(filter2, true), f), x), xs) -> APP'(app'(filter, f), xs) The graph contains the following edges 2 >= 2 *APP'(app'(app'(app'(filter2, false), f), x), xs) -> APP'(app'(filter, f), xs) The graph contains the following edges 2 >= 2 ---------------------------------------- (57) YES