5.85/2.38 YES 5.85/2.39 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.85/2.39 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.85/2.39 5.85/2.39 5.85/2.39 Termination w.r.t. Q of the given QTRS could be proven: 5.85/2.39 5.85/2.39 (0) QTRS 5.85/2.39 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 5.85/2.39 (2) QDP 5.85/2.39 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 5.85/2.39 (4) AND 5.85/2.39 (5) QDP 5.85/2.39 (6) UsableRulesProof [EQUIVALENT, 0 ms] 5.85/2.39 (7) QDP 5.85/2.39 (8) QReductionProof [EQUIVALENT, 0 ms] 5.85/2.39 (9) QDP 5.85/2.39 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 5.85/2.39 (11) YES 5.85/2.39 (12) QDP 5.85/2.39 (13) QDPOrderProof [EQUIVALENT, 72 ms] 5.85/2.39 (14) QDP 5.85/2.39 (15) PisEmptyProof [EQUIVALENT, 0 ms] 5.85/2.39 (16) YES 5.85/2.39 5.85/2.39 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (0) 5.85/2.39 Obligation: 5.85/2.39 Q restricted rewrite system: 5.85/2.39 The TRS R consists of the following rules: 5.85/2.39 5.85/2.39 and(true, y) -> y 5.85/2.39 and(false, y) -> false 5.85/2.39 eq(nil, nil) -> true 5.85/2.39 eq(cons(t, l), nil) -> false 5.85/2.39 eq(nil, cons(t, l)) -> false 5.85/2.39 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.85/2.39 eq(var(l), var(l')) -> eq(l, l') 5.85/2.39 eq(var(l), apply(t, s)) -> false 5.85/2.39 eq(var(l), lambda(x, t)) -> false 5.85/2.39 eq(apply(t, s), var(l)) -> false 5.85/2.39 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.85/2.39 eq(apply(t, s), lambda(x, t)) -> false 5.85/2.39 eq(lambda(x, t), var(l)) -> false 5.85/2.39 eq(lambda(x, t), apply(t, s)) -> false 5.85/2.39 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.85/2.39 if(true, var(k), var(l')) -> var(k) 5.85/2.39 if(false, var(k), var(l')) -> var(l') 5.85/2.39 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.85/2.39 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.85/2.39 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.85/2.39 5.85/2.39 The set Q consists of the following terms: 5.85/2.39 5.85/2.39 and(true, x0) 5.85/2.39 and(false, x0) 5.85/2.39 eq(nil, nil) 5.85/2.39 eq(cons(x0, x1), nil) 5.85/2.39 eq(nil, cons(x0, x1)) 5.85/2.39 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.39 eq(var(x0), var(x1)) 5.85/2.39 eq(var(x0), apply(x1, x2)) 5.85/2.39 eq(var(x0), lambda(x1, x2)) 5.85/2.39 eq(apply(x0, x1), var(x2)) 5.85/2.39 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.39 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.39 eq(lambda(x0, x1), var(x2)) 5.85/2.39 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.39 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.39 if(true, var(x0), var(x1)) 5.85/2.39 if(false, var(x0), var(x1)) 5.85/2.39 ren(var(x0), var(x1), var(x2)) 5.85/2.39 ren(x0, x1, apply(x2, x3)) 5.85/2.39 ren(x0, x1, lambda(x2, x3)) 5.85/2.39 5.85/2.39 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (1) DependencyPairsProof (EQUIVALENT) 5.85/2.39 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (2) 5.85/2.39 Obligation: 5.85/2.39 Q DP problem: 5.85/2.39 The TRS P consists of the following rules: 5.85/2.39 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> AND(eq(t, t'), eq(l, l')) 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(t, t') 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(l, l') 5.85/2.39 EQ(var(l), var(l')) -> EQ(l, l') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> AND(eq(t, t'), eq(s, s')) 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(t, t') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(s, s') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> AND(eq(x, x'), eq(t, t')) 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(x, x') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(t, t') 5.85/2.39 REN(var(l), var(k), var(l')) -> IF(eq(l, l'), var(k), var(l')) 5.85/2.39 REN(var(l), var(k), var(l')) -> EQ(l, l') 5.85/2.39 REN(x, y, apply(t, s)) -> REN(x, y, t) 5.85/2.39 REN(x, y, apply(t, s)) -> REN(x, y, s) 5.85/2.39 REN(x, y, lambda(z, t)) -> REN(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t)) 5.85/2.39 REN(x, y, lambda(z, t)) -> REN(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t) 5.85/2.39 5.85/2.39 The TRS R consists of the following rules: 5.85/2.39 5.85/2.39 and(true, y) -> y 5.85/2.39 and(false, y) -> false 5.85/2.39 eq(nil, nil) -> true 5.85/2.39 eq(cons(t, l), nil) -> false 5.85/2.39 eq(nil, cons(t, l)) -> false 5.85/2.39 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.85/2.39 eq(var(l), var(l')) -> eq(l, l') 5.85/2.39 eq(var(l), apply(t, s)) -> false 5.85/2.39 eq(var(l), lambda(x, t)) -> false 5.85/2.39 eq(apply(t, s), var(l)) -> false 5.85/2.39 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.85/2.39 eq(apply(t, s), lambda(x, t)) -> false 5.85/2.39 eq(lambda(x, t), var(l)) -> false 5.85/2.39 eq(lambda(x, t), apply(t, s)) -> false 5.85/2.39 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.85/2.39 if(true, var(k), var(l')) -> var(k) 5.85/2.39 if(false, var(k), var(l')) -> var(l') 5.85/2.39 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.85/2.39 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.85/2.39 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.85/2.39 5.85/2.39 The set Q consists of the following terms: 5.85/2.39 5.85/2.39 and(true, x0) 5.85/2.39 and(false, x0) 5.85/2.39 eq(nil, nil) 5.85/2.39 eq(cons(x0, x1), nil) 5.85/2.39 eq(nil, cons(x0, x1)) 5.85/2.39 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.39 eq(var(x0), var(x1)) 5.85/2.39 eq(var(x0), apply(x1, x2)) 5.85/2.39 eq(var(x0), lambda(x1, x2)) 5.85/2.39 eq(apply(x0, x1), var(x2)) 5.85/2.39 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.39 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.39 eq(lambda(x0, x1), var(x2)) 5.85/2.39 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.39 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.39 if(true, var(x0), var(x1)) 5.85/2.39 if(false, var(x0), var(x1)) 5.85/2.39 ren(var(x0), var(x1), var(x2)) 5.85/2.39 ren(x0, x1, apply(x2, x3)) 5.85/2.39 ren(x0, x1, lambda(x2, x3)) 5.85/2.39 5.85/2.39 We have to consider all minimal (P,Q,R)-chains. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (3) DependencyGraphProof (EQUIVALENT) 5.85/2.39 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 5 less nodes. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (4) 5.85/2.39 Complex Obligation (AND) 5.85/2.39 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (5) 5.85/2.39 Obligation: 5.85/2.39 Q DP problem: 5.85/2.39 The TRS P consists of the following rules: 5.85/2.39 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(l, l') 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(t, t') 5.85/2.39 EQ(var(l), var(l')) -> EQ(l, l') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(t, t') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(s, s') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(x, x') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(t, t') 5.85/2.39 5.85/2.39 The TRS R consists of the following rules: 5.85/2.39 5.85/2.39 and(true, y) -> y 5.85/2.39 and(false, y) -> false 5.85/2.39 eq(nil, nil) -> true 5.85/2.39 eq(cons(t, l), nil) -> false 5.85/2.39 eq(nil, cons(t, l)) -> false 5.85/2.39 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.85/2.39 eq(var(l), var(l')) -> eq(l, l') 5.85/2.39 eq(var(l), apply(t, s)) -> false 5.85/2.39 eq(var(l), lambda(x, t)) -> false 5.85/2.39 eq(apply(t, s), var(l)) -> false 5.85/2.39 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.85/2.39 eq(apply(t, s), lambda(x, t)) -> false 5.85/2.39 eq(lambda(x, t), var(l)) -> false 5.85/2.39 eq(lambda(x, t), apply(t, s)) -> false 5.85/2.39 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.85/2.39 if(true, var(k), var(l')) -> var(k) 5.85/2.39 if(false, var(k), var(l')) -> var(l') 5.85/2.39 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.85/2.39 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.85/2.39 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.85/2.39 5.85/2.39 The set Q consists of the following terms: 5.85/2.39 5.85/2.39 and(true, x0) 5.85/2.39 and(false, x0) 5.85/2.39 eq(nil, nil) 5.85/2.39 eq(cons(x0, x1), nil) 5.85/2.39 eq(nil, cons(x0, x1)) 5.85/2.39 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.39 eq(var(x0), var(x1)) 5.85/2.39 eq(var(x0), apply(x1, x2)) 5.85/2.39 eq(var(x0), lambda(x1, x2)) 5.85/2.39 eq(apply(x0, x1), var(x2)) 5.85/2.39 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.39 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.39 eq(lambda(x0, x1), var(x2)) 5.85/2.39 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.39 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.39 if(true, var(x0), var(x1)) 5.85/2.39 if(false, var(x0), var(x1)) 5.85/2.39 ren(var(x0), var(x1), var(x2)) 5.85/2.39 ren(x0, x1, apply(x2, x3)) 5.85/2.39 ren(x0, x1, lambda(x2, x3)) 5.85/2.39 5.85/2.39 We have to consider all minimal (P,Q,R)-chains. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (6) UsableRulesProof (EQUIVALENT) 5.85/2.39 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. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (7) 5.85/2.39 Obligation: 5.85/2.39 Q DP problem: 5.85/2.39 The TRS P consists of the following rules: 5.85/2.39 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(l, l') 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(t, t') 5.85/2.39 EQ(var(l), var(l')) -> EQ(l, l') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(t, t') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(s, s') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(x, x') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(t, t') 5.85/2.39 5.85/2.39 R is empty. 5.85/2.39 The set Q consists of the following terms: 5.85/2.39 5.85/2.39 and(true, x0) 5.85/2.39 and(false, x0) 5.85/2.39 eq(nil, nil) 5.85/2.39 eq(cons(x0, x1), nil) 5.85/2.39 eq(nil, cons(x0, x1)) 5.85/2.39 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.39 eq(var(x0), var(x1)) 5.85/2.39 eq(var(x0), apply(x1, x2)) 5.85/2.39 eq(var(x0), lambda(x1, x2)) 5.85/2.39 eq(apply(x0, x1), var(x2)) 5.85/2.39 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.39 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.39 eq(lambda(x0, x1), var(x2)) 5.85/2.39 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.39 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.39 if(true, var(x0), var(x1)) 5.85/2.39 if(false, var(x0), var(x1)) 5.85/2.39 ren(var(x0), var(x1), var(x2)) 5.85/2.39 ren(x0, x1, apply(x2, x3)) 5.85/2.39 ren(x0, x1, lambda(x2, x3)) 5.85/2.39 5.85/2.39 We have to consider all minimal (P,Q,R)-chains. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (8) QReductionProof (EQUIVALENT) 5.85/2.39 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 5.85/2.39 5.85/2.39 and(true, x0) 5.85/2.39 and(false, x0) 5.85/2.39 eq(nil, nil) 5.85/2.39 eq(cons(x0, x1), nil) 5.85/2.39 eq(nil, cons(x0, x1)) 5.85/2.39 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.39 eq(var(x0), var(x1)) 5.85/2.39 eq(var(x0), apply(x1, x2)) 5.85/2.39 eq(var(x0), lambda(x1, x2)) 5.85/2.39 eq(apply(x0, x1), var(x2)) 5.85/2.39 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.39 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.39 eq(lambda(x0, x1), var(x2)) 5.85/2.39 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.39 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.39 if(true, var(x0), var(x1)) 5.85/2.39 if(false, var(x0), var(x1)) 5.85/2.39 ren(var(x0), var(x1), var(x2)) 5.85/2.39 ren(x0, x1, apply(x2, x3)) 5.85/2.39 ren(x0, x1, lambda(x2, x3)) 5.85/2.39 5.85/2.39 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (9) 5.85/2.39 Obligation: 5.85/2.39 Q DP problem: 5.85/2.39 The TRS P consists of the following rules: 5.85/2.39 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(l, l') 5.85/2.39 EQ(cons(t, l), cons(t', l')) -> EQ(t, t') 5.85/2.39 EQ(var(l), var(l')) -> EQ(l, l') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(t, t') 5.85/2.39 EQ(apply(t, s), apply(t', s')) -> EQ(s, s') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(x, x') 5.85/2.39 EQ(lambda(x, t), lambda(x', t')) -> EQ(t, t') 5.85/2.39 5.85/2.39 R is empty. 5.85/2.39 Q is empty. 5.85/2.39 We have to consider all minimal (P,Q,R)-chains. 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (10) QDPSizeChangeProof (EQUIVALENT) 5.85/2.39 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. 5.85/2.39 5.85/2.39 From the DPs we obtained the following set of size-change graphs: 5.85/2.39 *EQ(cons(t, l), cons(t', l')) -> EQ(l, l') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 *EQ(cons(t, l), cons(t', l')) -> EQ(t, t') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 *EQ(var(l), var(l')) -> EQ(l, l') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 *EQ(apply(t, s), apply(t', s')) -> EQ(t, t') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 *EQ(apply(t, s), apply(t', s')) -> EQ(s, s') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 *EQ(lambda(x, t), lambda(x', t')) -> EQ(x, x') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 *EQ(lambda(x, t), lambda(x', t')) -> EQ(t, t') 5.85/2.39 The graph contains the following edges 1 > 1, 2 > 2 5.85/2.39 5.85/2.39 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (11) 5.85/2.39 YES 5.85/2.39 5.85/2.39 ---------------------------------------- 5.85/2.39 5.85/2.39 (12) 5.85/2.39 Obligation: 5.85/2.39 Q DP problem: 5.85/2.39 The TRS P consists of the following rules: 5.85/2.39 5.85/2.39 REN(x, y, apply(t, s)) -> REN(x, y, s) 5.85/2.39 REN(x, y, apply(t, s)) -> REN(x, y, t) 5.85/2.39 REN(x, y, lambda(z, t)) -> REN(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t)) 5.85/2.39 REN(x, y, lambda(z, t)) -> REN(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t) 5.85/2.39 5.85/2.39 The TRS R consists of the following rules: 5.85/2.39 5.85/2.39 and(true, y) -> y 5.85/2.39 and(false, y) -> false 5.85/2.39 eq(nil, nil) -> true 5.85/2.39 eq(cons(t, l), nil) -> false 5.85/2.39 eq(nil, cons(t, l)) -> false 5.85/2.39 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.85/2.39 eq(var(l), var(l')) -> eq(l, l') 5.85/2.39 eq(var(l), apply(t, s)) -> false 5.85/2.39 eq(var(l), lambda(x, t)) -> false 5.85/2.39 eq(apply(t, s), var(l)) -> false 5.85/2.39 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.85/2.39 eq(apply(t, s), lambda(x, t)) -> false 5.85/2.39 eq(lambda(x, t), var(l)) -> false 5.85/2.39 eq(lambda(x, t), apply(t, s)) -> false 5.85/2.39 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.85/2.40 if(true, var(k), var(l')) -> var(k) 5.85/2.40 if(false, var(k), var(l')) -> var(l') 5.85/2.40 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.85/2.40 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.85/2.40 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.85/2.40 5.85/2.40 The set Q consists of the following terms: 5.85/2.40 5.85/2.40 and(true, x0) 5.85/2.40 and(false, x0) 5.85/2.40 eq(nil, nil) 5.85/2.40 eq(cons(x0, x1), nil) 5.85/2.40 eq(nil, cons(x0, x1)) 5.85/2.40 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.40 eq(var(x0), var(x1)) 5.85/2.40 eq(var(x0), apply(x1, x2)) 5.85/2.40 eq(var(x0), lambda(x1, x2)) 5.85/2.40 eq(apply(x0, x1), var(x2)) 5.85/2.40 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.40 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.40 eq(lambda(x0, x1), var(x2)) 5.85/2.40 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.40 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.40 if(true, var(x0), var(x1)) 5.85/2.40 if(false, var(x0), var(x1)) 5.85/2.40 ren(var(x0), var(x1), var(x2)) 5.85/2.40 ren(x0, x1, apply(x2, x3)) 5.85/2.40 ren(x0, x1, lambda(x2, x3)) 5.85/2.40 5.85/2.40 We have to consider all minimal (P,Q,R)-chains. 5.85/2.40 ---------------------------------------- 5.85/2.40 5.85/2.40 (13) QDPOrderProof (EQUIVALENT) 5.85/2.40 We use the reduction pair processor [LPAR04,JAR06]. 5.85/2.40 5.85/2.40 5.85/2.40 The following pairs can be oriented strictly and are deleted. 5.85/2.40 5.85/2.40 REN(x, y, apply(t, s)) -> REN(x, y, s) 5.85/2.40 REN(x, y, apply(t, s)) -> REN(x, y, t) 5.85/2.40 REN(x, y, lambda(z, t)) -> REN(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t)) 5.85/2.40 REN(x, y, lambda(z, t)) -> REN(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t) 5.85/2.40 The remaining pairs can at least be oriented weakly. 5.85/2.40 Used ordering: Combined order from the following AFS and order. 5.85/2.40 REN(x1, x2, x3) = x3 5.85/2.40 5.85/2.40 apply(x1, x2) = apply(x1, x2) 5.85/2.40 5.85/2.40 lambda(x1, x2) = lambda(x2) 5.85/2.40 5.85/2.40 ren(x1, x2, x3) = ren(x3) 5.85/2.40 5.85/2.40 var(x1) = var 5.85/2.40 5.85/2.40 if(x1, x2, x3) = if 5.85/2.40 5.85/2.40 5.85/2.40 Knuth-Bendix order [KBO] with precedence:ren_1 > lambda_1 5.85/2.40 ren_1 > if > var 5.85/2.40 ren_1 > apply_2 5.85/2.40 5.85/2.40 and weight map: 5.85/2.40 5.85/2.40 lambda_1=1 5.85/2.40 var=1 5.85/2.40 ren_1=0 5.85/2.40 apply_2=1 5.85/2.40 if=1 5.85/2.40 5.85/2.40 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 5.85/2.40 5.85/2.40 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.85/2.40 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.85/2.40 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.85/2.40 if(true, var(k), var(l')) -> var(k) 5.85/2.40 if(false, var(k), var(l')) -> var(l') 5.85/2.40 5.85/2.40 5.85/2.40 ---------------------------------------- 5.85/2.40 5.85/2.40 (14) 5.85/2.40 Obligation: 5.85/2.40 Q DP problem: 5.85/2.40 P is empty. 5.85/2.40 The TRS R consists of the following rules: 5.85/2.40 5.85/2.40 and(true, y) -> y 5.85/2.40 and(false, y) -> false 5.85/2.40 eq(nil, nil) -> true 5.85/2.40 eq(cons(t, l), nil) -> false 5.85/2.40 eq(nil, cons(t, l)) -> false 5.85/2.40 eq(cons(t, l), cons(t', l')) -> and(eq(t, t'), eq(l, l')) 5.85/2.40 eq(var(l), var(l')) -> eq(l, l') 5.85/2.40 eq(var(l), apply(t, s)) -> false 5.85/2.40 eq(var(l), lambda(x, t)) -> false 5.85/2.40 eq(apply(t, s), var(l)) -> false 5.85/2.40 eq(apply(t, s), apply(t', s')) -> and(eq(t, t'), eq(s, s')) 5.85/2.40 eq(apply(t, s), lambda(x, t)) -> false 5.85/2.40 eq(lambda(x, t), var(l)) -> false 5.85/2.40 eq(lambda(x, t), apply(t, s)) -> false 5.85/2.40 eq(lambda(x, t), lambda(x', t')) -> and(eq(x, x'), eq(t, t')) 5.85/2.40 if(true, var(k), var(l')) -> var(k) 5.85/2.40 if(false, var(k), var(l')) -> var(l') 5.85/2.40 ren(var(l), var(k), var(l')) -> if(eq(l, l'), var(k), var(l')) 5.85/2.40 ren(x, y, apply(t, s)) -> apply(ren(x, y, t), ren(x, y, s)) 5.85/2.40 ren(x, y, lambda(z, t)) -> lambda(var(cons(x, cons(y, cons(lambda(z, t), nil)))), ren(x, y, ren(z, var(cons(x, cons(y, cons(lambda(z, t), nil)))), t))) 5.85/2.40 5.85/2.40 The set Q consists of the following terms: 5.85/2.40 5.85/2.40 and(true, x0) 5.85/2.40 and(false, x0) 5.85/2.40 eq(nil, nil) 5.85/2.40 eq(cons(x0, x1), nil) 5.85/2.40 eq(nil, cons(x0, x1)) 5.85/2.40 eq(cons(x0, x1), cons(x2, x3)) 5.85/2.40 eq(var(x0), var(x1)) 5.85/2.40 eq(var(x0), apply(x1, x2)) 5.85/2.40 eq(var(x0), lambda(x1, x2)) 5.85/2.40 eq(apply(x0, x1), var(x2)) 5.85/2.40 eq(apply(x0, x1), apply(x2, x3)) 5.85/2.40 eq(apply(x0, x1), lambda(x2, x0)) 5.85/2.40 eq(lambda(x0, x1), var(x2)) 5.85/2.40 eq(lambda(x0, x1), apply(x1, x2)) 5.85/2.40 eq(lambda(x0, x1), lambda(x2, x3)) 5.85/2.40 if(true, var(x0), var(x1)) 5.85/2.40 if(false, var(x0), var(x1)) 5.85/2.40 ren(var(x0), var(x1), var(x2)) 5.85/2.40 ren(x0, x1, apply(x2, x3)) 5.85/2.40 ren(x0, x1, lambda(x2, x3)) 5.85/2.40 5.85/2.40 We have to consider all minimal (P,Q,R)-chains. 5.85/2.40 ---------------------------------------- 5.85/2.40 5.85/2.40 (15) PisEmptyProof (EQUIVALENT) 5.85/2.40 The TRS P is empty. Hence, there is no (P,Q,R) chain. 5.85/2.40 ---------------------------------------- 5.85/2.40 5.85/2.40 (16) 5.85/2.40 YES 6.23/2.43 EOF