4.23/2.18 YES 4.23/2.19 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 4.23/2.19 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.23/2.19 4.23/2.19 4.23/2.19 Termination w.r.t. Q of the given QTRS could be proven: 4.23/2.19 4.23/2.19 (0) QTRS 4.23/2.19 (1) DependencyPairsProof [EQUIVALENT, 20 ms] 4.23/2.19 (2) QDP 4.23/2.19 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 4.23/2.19 (4) AND 4.23/2.19 (5) QDP 4.23/2.19 (6) UsableRulesProof [EQUIVALENT, 0 ms] 4.23/2.19 (7) QDP 4.23/2.19 (8) QReductionProof [EQUIVALENT, 0 ms] 4.23/2.19 (9) QDP 4.23/2.19 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.23/2.19 (11) YES 4.23/2.19 (12) QDP 4.23/2.19 (13) UsableRulesProof [EQUIVALENT, 0 ms] 4.23/2.19 (14) QDP 4.23/2.19 (15) QReductionProof [EQUIVALENT, 0 ms] 4.23/2.19 (16) QDP 4.23/2.19 (17) QDPOrderProof [EQUIVALENT, 13 ms] 4.23/2.19 (18) QDP 4.23/2.19 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 4.23/2.19 (20) TRUE 4.23/2.19 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (0) 4.23/2.19 Obligation: 4.23/2.19 Q restricted rewrite system: 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 minus(x, y) -> if(le(x, y), x, y) 4.23/2.19 if(true, x, y) -> 0 4.23/2.19 if(false, x, y) -> s(minus(p(x), y)) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (1) DependencyPairsProof (EQUIVALENT) 4.23/2.19 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (2) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 LE(s(x), s(y)) -> LE(x, y) 4.23/2.19 MINUS(x, y) -> IF(le(x, y), x, y) 4.23/2.19 MINUS(x, y) -> LE(x, y) 4.23/2.19 IF(false, x, y) -> MINUS(p(x), y) 4.23/2.19 IF(false, x, y) -> P(x) 4.23/2.19 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 minus(x, y) -> if(le(x, y), x, y) 4.23/2.19 if(true, x, y) -> 0 4.23/2.19 if(false, x, y) -> s(minus(p(x), y)) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (3) DependencyGraphProof (EQUIVALENT) 4.23/2.19 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (4) 4.23/2.19 Complex Obligation (AND) 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (5) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 LE(s(x), s(y)) -> LE(x, y) 4.23/2.19 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 minus(x, y) -> if(le(x, y), x, y) 4.23/2.19 if(true, x, y) -> 0 4.23/2.19 if(false, x, y) -> s(minus(p(x), y)) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (6) UsableRulesProof (EQUIVALENT) 4.23/2.19 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.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (7) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 LE(s(x), s(y)) -> LE(x, y) 4.23/2.19 4.23/2.19 R is empty. 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (8) QReductionProof (EQUIVALENT) 4.23/2.19 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (9) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 LE(s(x), s(y)) -> LE(x, y) 4.23/2.19 4.23/2.19 R is empty. 4.23/2.19 Q is empty. 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (10) QDPSizeChangeProof (EQUIVALENT) 4.23/2.19 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.23/2.19 4.23/2.19 From the DPs we obtained the following set of size-change graphs: 4.23/2.19 *LE(s(x), s(y)) -> LE(x, y) 4.23/2.19 The graph contains the following edges 1 > 1, 2 > 2 4.23/2.19 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (11) 4.23/2.19 YES 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (12) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 MINUS(x, y) -> IF(le(x, y), x, y) 4.23/2.19 IF(false, x, y) -> MINUS(p(x), y) 4.23/2.19 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 minus(x, y) -> if(le(x, y), x, y) 4.23/2.19 if(true, x, y) -> 0 4.23/2.19 if(false, x, y) -> s(minus(p(x), y)) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (13) UsableRulesProof (EQUIVALENT) 4.23/2.19 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.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (14) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 MINUS(x, y) -> IF(le(x, y), x, y) 4.23/2.19 IF(false, x, y) -> MINUS(p(x), y) 4.23/2.19 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (15) QReductionProof (EQUIVALENT) 4.23/2.19 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.23/2.19 4.23/2.19 minus(x0, x1) 4.23/2.19 if(true, x0, x1) 4.23/2.19 if(false, x0, x1) 4.23/2.19 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (16) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 MINUS(x, y) -> IF(le(x, y), x, y) 4.23/2.19 IF(false, x, y) -> MINUS(p(x), y) 4.23/2.19 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (17) QDPOrderProof (EQUIVALENT) 4.23/2.19 We use the reduction pair processor [LPAR04,JAR06]. 4.23/2.19 4.23/2.19 4.23/2.19 The following pairs can be oriented strictly and are deleted. 4.23/2.19 4.23/2.19 IF(false, x, y) -> MINUS(p(x), y) 4.23/2.19 The remaining pairs can at least be oriented weakly. 4.23/2.19 Used ordering: Polynomial interpretation [POLO,RATPOLO]: 4.23/2.19 4.23/2.19 POL(0) = 0 4.23/2.19 POL(IF(x_1, x_2, x_3)) = [4]x_1 + [1/2]x_2 4.23/2.19 POL(MINUS(x_1, x_2)) = [2]x_1 4.23/2.19 POL(false) = [1/4] 4.23/2.19 POL(le(x_1, x_2)) = [1/4]x_1 4.23/2.19 POL(p(x_1)) = [1/4]x_1 4.23/2.19 POL(s(x_1)) = [4] + [4]x_1 4.23/2.19 POL(true) = 0 4.23/2.19 The value of delta used in the strict ordering is 1. 4.23/2.19 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 4.23/2.19 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 4.23/2.19 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (18) 4.23/2.19 Obligation: 4.23/2.19 Q DP problem: 4.23/2.19 The TRS P consists of the following rules: 4.23/2.19 4.23/2.19 MINUS(x, y) -> IF(le(x, y), x, y) 4.23/2.19 4.23/2.19 The TRS R consists of the following rules: 4.23/2.19 4.23/2.19 p(0) -> 0 4.23/2.19 p(s(x)) -> x 4.23/2.19 le(0, y) -> true 4.23/2.19 le(s(x), 0) -> false 4.23/2.19 le(s(x), s(y)) -> le(x, y) 4.23/2.19 4.23/2.19 The set Q consists of the following terms: 4.23/2.19 4.23/2.19 p(0) 4.23/2.19 p(s(x0)) 4.23/2.19 le(0, x0) 4.23/2.19 le(s(x0), 0) 4.23/2.19 le(s(x0), s(x1)) 4.23/2.19 4.23/2.19 We have to consider all minimal (P,Q,R)-chains. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (19) DependencyGraphProof (EQUIVALENT) 4.23/2.19 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 4.23/2.19 ---------------------------------------- 4.23/2.19 4.23/2.19 (20) 4.23/2.19 TRUE 4.23/2.23 EOF