7.54/3.07 YES 7.58/3.08 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 7.58/3.08 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.58/3.08 7.58/3.08 7.58/3.08 Termination w.r.t. Q of the given QTRS could be proven: 7.58/3.08 7.58/3.08 (0) QTRS 7.58/3.08 (1) DependencyPairsProof [EQUIVALENT, 28 ms] 7.58/3.08 (2) QDP 7.58/3.08 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 7.58/3.08 (4) AND 7.58/3.08 (5) QDP 7.58/3.08 (6) UsableRulesProof [EQUIVALENT, 0 ms] 7.58/3.08 (7) QDP 7.58/3.08 (8) ATransformationProof [EQUIVALENT, 0 ms] 7.58/3.08 (9) QDP 7.58/3.08 (10) QReductionProof [EQUIVALENT, 0 ms] 7.58/3.08 (11) QDP 7.58/3.08 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.58/3.08 (13) YES 7.58/3.08 (14) QDP 7.58/3.08 (15) UsableRulesProof [EQUIVALENT, 0 ms] 7.58/3.08 (16) QDP 7.58/3.08 (17) ATransformationProof [EQUIVALENT, 0 ms] 7.58/3.08 (18) QDP 7.58/3.08 (19) QReductionProof [EQUIVALENT, 0 ms] 7.58/3.08 (20) QDP 7.58/3.08 (21) TransformationProof [EQUIVALENT, 0 ms] 7.58/3.08 (22) QDP 7.58/3.08 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 7.58/3.08 (24) TRUE 7.58/3.08 (25) QDP 7.58/3.08 (26) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.58/3.08 (27) YES 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (0) 7.58/3.08 Obligation: 7.58/3.08 Q restricted rewrite system: 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 app(app(plus, x), 0) -> x 7.58/3.08 app(app(plus, x), app(s, y)) -> app(s, app(app(plus, x), y)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x) -> app(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 app(app(g, x), y) -> x 7.58/3.08 app(app(g, x), y) -> y 7.58/3.08 app(app(map, fun), nil) -> nil 7.58/3.08 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 7.58/3.08 app(app(filter, fun), nil) -> nil 7.58/3.08 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 7.58/3.08 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (1) DependencyPairsProof (EQUIVALENT) 7.58/3.08 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (2) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 APP(app(plus, x), app(s, y)) -> APP(s, app(app(plus, x), y)) 7.58/3.08 APP(app(plus, x), app(s, y)) -> APP(app(plus, x), y) 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(app(f, x), app(app(plus, x), x)) 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(f, x) 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(app(plus, x), x) 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(plus, x) 7.58/3.08 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(cons, app(fun, x)), app(app(map, fun), xs)) 7.58/3.08 APP(app(map, fun), app(app(cons, x), xs)) -> APP(cons, app(fun, x)) 7.58/3.08 APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 7.58/3.08 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(filter2, app(fun, x)), fun), x) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(filter2, app(fun, x)), fun) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(filter2, app(fun, x)) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 7.58/3.08 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(cons, x), app(app(filter, fun), xs)) 7.58/3.08 APP(app(app(app(filter2, true), fun), x), xs) -> APP(cons, x) 7.58/3.08 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 7.58/3.08 APP(app(app(app(filter2, true), fun), x), xs) -> APP(filter, fun) 7.58/3.08 APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 7.58/3.08 APP(app(app(app(filter2, false), fun), x), xs) -> APP(filter, fun) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 app(app(plus, x), 0) -> x 7.58/3.08 app(app(plus, x), app(s, y)) -> app(s, app(app(plus, x), y)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x) -> app(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 app(app(g, x), y) -> x 7.58/3.08 app(app(g, x), y) -> y 7.58/3.08 app(app(map, fun), nil) -> nil 7.58/3.08 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 7.58/3.08 app(app(filter, fun), nil) -> nil 7.58/3.08 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 7.58/3.08 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (3) DependencyGraphProof (EQUIVALENT) 7.58/3.08 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 14 less nodes. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (4) 7.58/3.08 Complex Obligation (AND) 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (5) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 APP(app(plus, x), app(s, y)) -> APP(app(plus, x), y) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 app(app(plus, x), 0) -> x 7.58/3.08 app(app(plus, x), app(s, y)) -> app(s, app(app(plus, x), y)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x) -> app(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 app(app(g, x), y) -> x 7.58/3.08 app(app(g, x), y) -> y 7.58/3.08 app(app(map, fun), nil) -> nil 7.58/3.08 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 7.58/3.08 app(app(filter, fun), nil) -> nil 7.58/3.08 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 7.58/3.08 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (6) UsableRulesProof (EQUIVALENT) 7.58/3.08 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. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (7) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 APP(app(plus, x), app(s, y)) -> APP(app(plus, x), y) 7.58/3.08 7.58/3.08 R is empty. 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (8) ATransformationProof (EQUIVALENT) 7.58/3.08 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (9) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 plus1(x, s(y)) -> plus1(x, y) 7.58/3.08 7.58/3.08 R is empty. 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 plus(x0, 0) 7.58/3.08 plus(x0, s(x1)) 7.58/3.08 f(0, s(0), x0) 7.58/3.08 g(x0, x1) 7.58/3.08 map(x0, nil) 7.58/3.08 map(x0, cons(x1, x2)) 7.58/3.08 filter(x0, nil) 7.58/3.08 filter(x0, cons(x1, x2)) 7.58/3.08 filter2(true, x0, x1, x2) 7.58/3.08 filter2(false, x0, x1, x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (10) QReductionProof (EQUIVALENT) 7.58/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.58/3.08 7.58/3.08 plus(x0, 0) 7.58/3.08 plus(x0, s(x1)) 7.58/3.08 f(0, s(0), x0) 7.58/3.08 g(x0, x1) 7.58/3.08 map(x0, nil) 7.58/3.08 map(x0, cons(x1, x2)) 7.58/3.08 filter(x0, nil) 7.58/3.08 filter(x0, cons(x1, x2)) 7.58/3.08 filter2(true, x0, x1, x2) 7.58/3.08 filter2(false, x0, x1, x2) 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (11) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 plus1(x, s(y)) -> plus1(x, y) 7.58/3.08 7.58/3.08 R is empty. 7.58/3.08 Q is empty. 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (12) QDPSizeChangeProof (EQUIVALENT) 7.58/3.08 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. 7.58/3.08 7.58/3.08 From the DPs we obtained the following set of size-change graphs: 7.58/3.08 *plus1(x, s(y)) -> plus1(x, y) 7.58/3.08 The graph contains the following edges 1 >= 1, 2 > 2 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (13) 7.58/3.08 YES 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (14) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 app(app(plus, x), 0) -> x 7.58/3.08 app(app(plus, x), app(s, y)) -> app(s, app(app(plus, x), y)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x) -> app(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 app(app(g, x), y) -> x 7.58/3.08 app(app(g, x), y) -> y 7.58/3.08 app(app(map, fun), nil) -> nil 7.58/3.08 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 7.58/3.08 app(app(filter, fun), nil) -> nil 7.58/3.08 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 7.58/3.08 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (15) UsableRulesProof (EQUIVALENT) 7.58/3.08 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. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (16) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 APP(app(app(f, 0), app(s, 0)), x) -> APP(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 app(app(plus, x), 0) -> x 7.58/3.08 app(app(plus, x), app(s, y)) -> app(s, app(app(plus, x), y)) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (17) ATransformationProof (EQUIVALENT) 7.58/3.08 We have applied the A-Transformation [FROCOS05] to get from an applicative problem to a standard problem. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (18) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 f1(0, s(0), x) -> f1(x, plus(x, x), x) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 plus(x, 0) -> x 7.58/3.08 plus(x, s(y)) -> s(plus(x, y)) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 plus(x0, 0) 7.58/3.08 plus(x0, s(x1)) 7.58/3.08 f(0, s(0), x0) 7.58/3.08 g(x0, x1) 7.58/3.08 map(x0, nil) 7.58/3.08 map(x0, cons(x1, x2)) 7.58/3.08 filter(x0, nil) 7.58/3.08 filter(x0, cons(x1, x2)) 7.58/3.08 filter2(true, x0, x1, x2) 7.58/3.08 filter2(false, x0, x1, x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (19) QReductionProof (EQUIVALENT) 7.58/3.08 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.58/3.08 7.58/3.08 f(0, s(0), x0) 7.58/3.08 g(x0, x1) 7.58/3.08 map(x0, nil) 7.58/3.08 map(x0, cons(x1, x2)) 7.58/3.08 filter(x0, nil) 7.58/3.08 filter(x0, cons(x1, x2)) 7.58/3.08 filter2(true, x0, x1, x2) 7.58/3.08 filter2(false, x0, x1, x2) 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (20) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 f1(0, s(0), x) -> f1(x, plus(x, x), x) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 plus(x, 0) -> x 7.58/3.08 plus(x, s(y)) -> s(plus(x, y)) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 plus(x0, 0) 7.58/3.08 plus(x0, s(x1)) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (21) TransformationProof (EQUIVALENT) 7.58/3.08 By narrowing [LPAR04] the rule f1(0, s(0), x) -> f1(x, plus(x, x), x) at position [1] we obtained the following new rules [LPAR04]: 7.58/3.08 7.58/3.08 (f1(0, s(0), 0) -> f1(0, 0, 0),f1(0, s(0), 0) -> f1(0, 0, 0)) 7.58/3.08 (f1(0, s(0), s(x1)) -> f1(s(x1), s(plus(s(x1), x1)), s(x1)),f1(0, s(0), s(x1)) -> f1(s(x1), s(plus(s(x1), x1)), s(x1))) 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (22) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 f1(0, s(0), 0) -> f1(0, 0, 0) 7.58/3.08 f1(0, s(0), s(x1)) -> f1(s(x1), s(plus(s(x1), x1)), s(x1)) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 plus(x, 0) -> x 7.58/3.08 plus(x, s(y)) -> s(plus(x, y)) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 plus(x0, 0) 7.58/3.08 plus(x0, s(x1)) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (23) DependencyGraphProof (EQUIVALENT) 7.58/3.08 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (24) 7.58/3.08 TRUE 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (25) 7.58/3.08 Obligation: 7.58/3.08 Q DP problem: 7.58/3.08 The TRS P consists of the following rules: 7.58/3.08 7.58/3.08 APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 7.58/3.08 APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 7.58/3.08 APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 7.58/3.08 APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 7.58/3.08 7.58/3.08 The TRS R consists of the following rules: 7.58/3.08 7.58/3.08 app(app(plus, x), 0) -> x 7.58/3.08 app(app(plus, x), app(s, y)) -> app(s, app(app(plus, x), y)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x) -> app(app(app(f, x), app(app(plus, x), x)), x) 7.58/3.08 app(app(g, x), y) -> x 7.58/3.08 app(app(g, x), y) -> y 7.58/3.08 app(app(map, fun), nil) -> nil 7.58/3.08 app(app(map, fun), app(app(cons, x), xs)) -> app(app(cons, app(fun, x)), app(app(map, fun), xs)) 7.58/3.08 app(app(filter, fun), nil) -> nil 7.58/3.08 app(app(filter, fun), app(app(cons, x), xs)) -> app(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 app(app(app(app(filter2, true), fun), x), xs) -> app(app(cons, x), app(app(filter, fun), xs)) 7.58/3.08 app(app(app(app(filter2, false), fun), x), xs) -> app(app(filter, fun), xs) 7.58/3.08 7.58/3.08 The set Q consists of the following terms: 7.58/3.08 7.58/3.08 app(app(plus, x0), 0) 7.58/3.08 app(app(plus, x0), app(s, x1)) 7.58/3.08 app(app(app(f, 0), app(s, 0)), x0) 7.58/3.08 app(app(g, x0), x1) 7.58/3.08 app(app(map, x0), nil) 7.58/3.08 app(app(map, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(filter, x0), nil) 7.58/3.08 app(app(filter, x0), app(app(cons, x1), x2)) 7.58/3.08 app(app(app(app(filter2, true), x0), x1), x2) 7.58/3.08 app(app(app(app(filter2, false), x0), x1), x2) 7.58/3.08 7.58/3.08 We have to consider all minimal (P,Q,R)-chains. 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (26) QDPSizeChangeProof (EQUIVALENT) 7.58/3.08 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. 7.58/3.08 7.58/3.08 From the DPs we obtained the following set of size-change graphs: 7.58/3.08 *APP(app(filter, fun), app(app(cons, x), xs)) -> APP(fun, x) 7.58/3.08 The graph contains the following edges 1 > 1, 2 > 2 7.58/3.08 7.58/3.08 7.58/3.08 *APP(app(map, fun), app(app(cons, x), xs)) -> APP(fun, x) 7.58/3.08 The graph contains the following edges 1 > 1, 2 > 2 7.58/3.08 7.58/3.08 7.58/3.08 *APP(app(map, fun), app(app(cons, x), xs)) -> APP(app(map, fun), xs) 7.58/3.08 The graph contains the following edges 1 >= 1, 2 > 2 7.58/3.08 7.58/3.08 7.58/3.08 *APP(app(filter, fun), app(app(cons, x), xs)) -> APP(app(app(app(filter2, app(fun, x)), fun), x), xs) 7.58/3.08 The graph contains the following edges 2 > 2 7.58/3.08 7.58/3.08 7.58/3.08 *APP(app(app(app(filter2, true), fun), x), xs) -> APP(app(filter, fun), xs) 7.58/3.08 The graph contains the following edges 2 >= 2 7.58/3.08 7.58/3.08 7.58/3.08 *APP(app(app(app(filter2, false), fun), x), xs) -> APP(app(filter, fun), xs) 7.58/3.08 The graph contains the following edges 2 >= 2 7.58/3.08 7.58/3.08 7.58/3.08 ---------------------------------------- 7.58/3.08 7.58/3.08 (27) 7.58/3.08 YES 7.67/3.18 EOF