4.05/1.81 YES 4.05/1.82 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.05/1.82 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.05/1.82 4.05/1.82 4.05/1.82 Termination w.r.t. Q of the given QTRS could be proven: 4.05/1.82 4.05/1.82 (0) QTRS 4.05/1.82 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 4.05/1.82 (2) QDP 4.05/1.82 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 4.05/1.82 (4) QDP 4.05/1.82 (5) UsableRulesProof [EQUIVALENT, 0 ms] 4.05/1.82 (6) QDP 4.05/1.82 (7) QReductionProof [EQUIVALENT, 0 ms] 4.05/1.82 (8) QDP 4.05/1.82 (9) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.05/1.82 (10) YES 4.05/1.82 4.05/1.82 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (0) 4.05/1.82 Obligation: 4.05/1.82 Q restricted rewrite system: 4.05/1.82 The TRS R consists of the following rules: 4.05/1.82 4.05/1.82 app(f, 0) -> app(f, 0) 4.05/1.82 0 -> 1 4.05/1.82 app(app(map, fun), nil) -> nil 4.05/1.82 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 4.05/1.82 app(app(filter, fun), nil) -> nil 4.05/1.82 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 4.05/1.82 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 4.05/1.82 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 4.05/1.82 4.05/1.82 The set Q consists of the following terms: 4.05/1.82 4.05/1.82 0 4.05/1.82 app(app(map, x0), nil) 4.05/1.82 app(app(map, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(filter, x0), nil) 4.05/1.82 app(app(filter, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(app(app(filter2, true), x0), x1), x2) 4.05/1.82 app(app(app(app(filter2, false), x0), x1), x2) 4.05/1.82 4.05/1.82 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (1) DependencyPairsProof (EQUIVALENT) 4.05/1.82 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (2) 4.05/1.82 Obligation: 4.05/1.82 Q DP problem: 4.05/1.82 The TRS P consists of the following rules: 4.05/1.82 4.05/1.82 APP(f, 0) -> APP(f, 0) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(cons, app(fun, x)), app(app(map, fun), xs)) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(cons, app(fun, x)) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(fun, x)), fun), x), xs) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(filter2, app(fun, x)), fun), x) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(filter2, app(fun, x)), fun) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(filter2, app(fun, x)) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(cons, x), app(app(filter, fun), xs)) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(cons, x) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(filter, fun) 4.05/1.82 APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 APP(app(app(app(filter2, false), fun), x), xs) -> APP(filter, fun) 4.05/1.82 4.05/1.82 The TRS R consists of the following rules: 4.05/1.82 4.05/1.82 app(f, 0) -> app(f, 0) 4.05/1.82 0 -> 1 4.05/1.82 app(app(map, fun), nil) -> nil 4.05/1.82 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 4.05/1.82 app(app(filter, fun), nil) -> nil 4.05/1.82 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 4.05/1.82 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 4.05/1.82 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 4.05/1.82 4.05/1.82 The set Q consists of the following terms: 4.05/1.82 4.05/1.82 0 4.05/1.82 app(app(map, x0), nil) 4.05/1.82 app(app(map, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(filter, x0), nil) 4.05/1.82 app(app(filter, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(app(app(filter2, true), x0), x1), x2) 4.05/1.82 app(app(app(app(filter2, false), x0), x1), x2) 4.05/1.82 4.05/1.82 We have to consider all minimal (P,Q,R)-chains. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (3) DependencyGraphProof (EQUIVALENT) 4.05/1.82 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 11 less nodes. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (4) 4.05/1.82 Obligation: 4.05/1.82 Q DP problem: 4.05/1.82 The TRS P consists of the following rules: 4.05/1.82 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 4.05/1.82 The TRS R consists of the following rules: 4.05/1.82 4.05/1.82 app(f, 0) -> app(f, 0) 4.05/1.82 0 -> 1 4.05/1.82 app(app(map, fun), nil) -> nil 4.05/1.82 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 4.05/1.82 app(app(filter, fun), nil) -> nil 4.05/1.82 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 4.05/1.82 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 4.05/1.82 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 4.05/1.82 4.05/1.82 The set Q consists of the following terms: 4.05/1.82 4.05/1.82 0 4.05/1.82 app(app(map, x0), nil) 4.05/1.82 app(app(map, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(filter, x0), nil) 4.05/1.82 app(app(filter, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(app(app(filter2, true), x0), x1), x2) 4.05/1.82 app(app(app(app(filter2, false), x0), x1), x2) 4.05/1.82 4.05/1.82 We have to consider all minimal (P,Q,R)-chains. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (5) UsableRulesProof (EQUIVALENT) 4.05/1.82 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. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (6) 4.05/1.82 Obligation: 4.05/1.82 Q DP problem: 4.05/1.82 The TRS P consists of the following rules: 4.05/1.82 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 4.05/1.82 R is empty. 4.05/1.82 The set Q consists of the following terms: 4.05/1.82 4.05/1.82 0 4.05/1.82 app(app(map, x0), nil) 4.05/1.82 app(app(map, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(filter, x0), nil) 4.05/1.82 app(app(filter, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(app(app(filter2, true), x0), x1), x2) 4.05/1.82 app(app(app(app(filter2, false), x0), x1), x2) 4.05/1.82 4.05/1.82 We have to consider all minimal (P,Q,R)-chains. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (7) QReductionProof (EQUIVALENT) 4.05/1.82 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.05/1.82 4.05/1.82 0 4.05/1.82 4.05/1.82 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (8) 4.05/1.82 Obligation: 4.05/1.82 Q DP problem: 4.05/1.82 The TRS P consists of the following rules: 4.05/1.82 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 4.05/1.82 APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 4.05/1.82 R is empty. 4.05/1.82 The set Q consists of the following terms: 4.05/1.82 4.05/1.82 app(app(map, x0), nil) 4.05/1.82 app(app(map, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(filter, x0), nil) 4.05/1.82 app(app(filter, x0), app(app(cons, x1), x2)) 4.05/1.82 app(app(app(app(filter2, true), x0), x1), x2) 4.05/1.82 app(app(app(app(filter2, false), x0), x1), x2) 4.05/1.82 4.05/1.82 We have to consider all minimal (P,Q,R)-chains. 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (9) QDPSizeChangeProof (EQUIVALENT) 4.05/1.82 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. 4.05/1.82 4.05/1.82 From the DPs we obtained the following set of size-change graphs: 4.05/1.82 *APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 The graph contains the following edges 1 > 1, 2 > 2 4.05/1.82 4.05/1.82 4.05/1.82 *APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 4.05/1.82 The graph contains the following edges 1 > 1, 2 > 2 4.05/1.82 4.05/1.82 4.05/1.82 *APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 4.05/1.82 The graph contains the following edges 1 >= 1, 2 > 2 4.05/1.82 4.05/1.82 4.05/1.82 *APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 The graph contains the following edges 2 >= 2 4.05/1.82 4.05/1.82 4.05/1.82 *APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 4.05/1.82 The graph contains the following edges 2 >= 2 4.05/1.82 4.05/1.82 4.05/1.82 ---------------------------------------- 4.05/1.82 4.05/1.82 (10) 4.05/1.82 YES 4.05/1.85 EOF