49.71/13.49 YES 53.74/14.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 53.74/14.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 53.74/14.49 53.74/14.49 53.74/14.49 Termination w.r.t. Q of the given QTRS could be proven: 53.74/14.49 53.74/14.49 (0) QTRS 53.74/14.49 (1) QTRSRRRProof [EQUIVALENT, 55 ms] 53.74/14.49 (2) QTRS 53.74/14.49 (3) DependencyPairsProof [EQUIVALENT, 26 ms] 53.74/14.49 (4) QDP 53.74/14.49 (5) DependencyGraphProof [EQUIVALENT, 7 ms] 53.74/14.49 (6) AND 53.74/14.49 (7) QDP 53.74/14.49 (8) UsableRulesProof [EQUIVALENT, 1 ms] 53.74/14.49 (9) QDP 53.74/14.49 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 53.74/14.49 (11) YES 53.74/14.49 (12) QDP 53.74/14.49 (13) UsableRulesProof [EQUIVALENT, 1 ms] 53.74/14.49 (14) QDP 53.74/14.49 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 53.74/14.49 (16) YES 53.74/14.49 (17) QDP 53.74/14.49 (18) UsableRulesProof [EQUIVALENT, 6 ms] 53.74/14.49 (19) QDP 53.74/14.49 (20) MRRProof [EQUIVALENT, 0 ms] 53.74/14.49 (21) QDP 53.74/14.49 (22) DependencyGraphProof [EQUIVALENT, 0 ms] 53.74/14.49 (23) AND 53.74/14.49 (24) QDP 53.74/14.49 (25) UsableRulesProof [EQUIVALENT, 1 ms] 53.74/14.49 (26) QDP 53.74/14.49 (27) MRRProof [EQUIVALENT, 7 ms] 53.74/14.49 (28) QDP 53.74/14.49 (29) MNOCProof [EQUIVALENT, 0 ms] 53.74/14.49 (30) QDP 53.74/14.49 (31) QDPOrderProof [EQUIVALENT, 9 ms] 53.74/14.49 (32) QDP 53.74/14.49 (33) PisEmptyProof [EQUIVALENT, 0 ms] 53.74/14.49 (34) YES 53.74/14.49 (35) QDP 53.74/14.49 (36) QDPOrderProof [EQUIVALENT, 8 ms] 53.74/14.49 (37) QDP 53.74/14.49 (38) QDPOrderProof [EQUIVALENT, 102 ms] 53.74/14.49 (39) QDP 53.74/14.49 (40) PisEmptyProof [EQUIVALENT, 0 ms] 53.74/14.49 (41) YES 53.74/14.49 (42) QDP 53.74/14.49 (43) UsableRulesProof [EQUIVALENT, 4 ms] 53.74/14.49 (44) QDP 53.74/14.49 (45) QDPOrderProof [EQUIVALENT, 54 ms] 53.74/14.49 (46) QDP 53.74/14.49 (47) PisEmptyProof [EQUIVALENT, 0 ms] 53.74/14.49 (48) YES 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (0) 53.74/14.49 Obligation: 53.74/14.49 Q restricted rewrite system: 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 0(x1) -> x1 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (1) QTRSRRRProof (EQUIVALENT) 53.74/14.49 Used ordering: 53.74/14.49 Polynomial interpretation [POLO]: 53.74/14.49 53.74/14.49 POL(0(x_1)) = 1 + x_1 53.74/14.49 POL(half(x_1)) = x_1 53.74/14.49 POL(log(x_1)) = x_1 53.74/14.49 POL(p(x_1)) = x_1 53.74/14.49 POL(s(x_1)) = x_1 53.74/14.49 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 53.74/14.49 53.74/14.49 0(x1) -> x1 53.74/14.49 53.74/14.49 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (2) 53.74/14.49 Obligation: 53.74/14.49 Q restricted rewrite system: 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (3) DependencyPairsProof (EQUIVALENT) 53.74/14.49 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (4) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 LOG(s(x1)) -> S(log(half(s(x1)))) 53.74/14.49 LOG(s(x1)) -> LOG(half(s(x1))) 53.74/14.49 LOG(s(x1)) -> HALF(s(x1)) 53.74/14.49 HALF(0(x1)) -> S(s(half(x1))) 53.74/14.49 HALF(0(x1)) -> S(half(x1)) 53.74/14.49 HALF(0(x1)) -> HALF(x1) 53.74/14.49 HALF(s(s(x1))) -> S(half(p(s(s(x1))))) 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 HALF(s(s(x1))) -> P(s(s(x1))) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> S(s(half(half(x1)))) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> S(half(half(x1))) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(x1) 53.74/14.49 P(s(s(s(x1)))) -> S(p(s(s(x1)))) 53.74/14.49 P(s(s(s(x1)))) -> P(s(s(x1))) 53.74/14.49 S(s(p(s(x1)))) -> S(s(x1)) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (5) DependencyGraphProof (EQUIVALENT) 53.74/14.49 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 9 less nodes. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (6) 53.74/14.49 Complex Obligation (AND) 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (7) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 S(s(p(s(x1)))) -> S(s(x1)) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (8) UsableRulesProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (9) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 S(s(p(s(x1)))) -> S(s(x1)) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (10) QDPSizeChangeProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 53.74/14.49 From the DPs we obtained the following set of size-change graphs: 53.74/14.49 *S(s(p(s(x1)))) -> S(s(x1)) 53.74/14.49 The graph contains the following edges 1 > 1 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (11) 53.74/14.49 YES 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (12) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 P(s(s(s(x1)))) -> P(s(s(x1))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (13) UsableRulesProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (14) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 P(s(s(s(x1)))) -> P(s(s(x1))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (15) QDPSizeChangeProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 53.74/14.49 From the DPs we obtained the following set of size-change graphs: 53.74/14.49 *P(s(s(s(x1)))) -> P(s(s(x1))) 53.74/14.49 The graph contains the following edges 1 > 1 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (16) 53.74/14.49 YES 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (17) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 HALF(0(x1)) -> HALF(x1) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(x1) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (18) UsableRulesProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (19) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 HALF(0(x1)) -> HALF(x1) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(x1) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (20) MRRProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 53.74/14.49 Strictly oriented dependency pairs: 53.74/14.49 53.74/14.49 HALF(0(x1)) -> HALF(x1) 53.74/14.49 53.74/14.49 Strictly oriented rules of the TRS R: 53.74/14.49 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 53.74/14.49 Used ordering: Polynomial interpretation [POLO]: 53.74/14.49 53.74/14.49 POL(0(x_1)) = 1 + x_1 53.74/14.49 POL(HALF(x_1)) = 2*x_1 53.74/14.49 POL(half(x_1)) = 2*x_1 53.74/14.49 POL(p(x_1)) = x_1 53.74/14.49 POL(s(x_1)) = x_1 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (21) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(x1) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (22) DependencyGraphProof (EQUIVALENT) 53.74/14.49 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (23) 53.74/14.49 Complex Obligation (AND) 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (24) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (25) UsableRulesProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (26) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (27) MRRProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 53.74/14.49 53.74/14.49 Strictly oriented rules of the TRS R: 53.74/14.49 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Used ordering: Polynomial interpretation [POLO]: 53.74/14.49 53.74/14.49 POL(HALF(x_1)) = x_1 53.74/14.49 POL(p(x_1)) = x_1 53.74/14.49 POL(s(x_1)) = 2 + 2*x_1 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (28) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (29) MNOCProof (EQUIVALENT) 53.74/14.49 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (30) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 The set Q consists of the following terms: 53.74/14.49 53.74/14.49 p(s(s(s(x0)))) 53.74/14.49 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (31) QDPOrderProof (EQUIVALENT) 53.74/14.49 We use the reduction pair processor [LPAR04,JAR06]. 53.74/14.49 53.74/14.49 53.74/14.49 The following pairs can be oriented strictly and are deleted. 53.74/14.49 53.74/14.49 HALF(s(s(x1))) -> HALF(p(s(s(x1)))) 53.74/14.49 The remaining pairs can at least be oriented weakly. 53.74/14.49 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 53.74/14.49 53.74/14.49 POL( HALF_1(x_1) ) = max{0, 2x_1 - 2} 53.74/14.49 POL( p_1(x_1) ) = max{0, x_1 - 2} 53.74/14.49 POL( s_1(x_1) ) = 2x_1 + 1 53.74/14.49 53.74/14.49 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 53.74/14.49 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (32) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 P is empty. 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 The set Q consists of the following terms: 53.74/14.49 53.74/14.49 p(s(s(s(x0)))) 53.74/14.49 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (33) PisEmptyProof (EQUIVALENT) 53.74/14.49 The TRS P is empty. Hence, there is no (P,Q,R) chain. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (34) 53.74/14.49 YES 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (35) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(x1) 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (36) QDPOrderProof (EQUIVALENT) 53.74/14.49 We use the reduction pair processor [LPAR04,JAR06]. 53.74/14.49 53.74/14.49 53.74/14.49 The following pairs can be oriented strictly and are deleted. 53.74/14.49 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(x1) 53.74/14.49 The remaining pairs can at least be oriented weakly. 53.74/14.49 Used ordering: Polynomial interpretation [POLO]: 53.74/14.49 53.74/14.49 POL(HALF(x_1)) = x_1 53.74/14.49 POL(half(x_1)) = 1 + x_1 53.74/14.49 POL(p(x_1)) = x_1 53.74/14.49 POL(s(x_1)) = x_1 53.74/14.49 53.74/14.49 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (37) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (38) QDPOrderProof (EQUIVALENT) 53.74/14.49 We use the reduction pair processor [LPAR04,JAR06]. 53.74/14.49 53.74/14.49 53.74/14.49 The following pairs can be oriented strictly and are deleted. 53.74/14.49 53.74/14.49 HALF(half(s(s(s(s(x1)))))) -> HALF(half(x1)) 53.74/14.49 The remaining pairs can at least be oriented weakly. 53.74/14.49 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 53.74/14.49 53.74/14.49 <<< 53.74/14.49 POL(HALF(x_1)) = [[-I]] + [[0A, -I, -I]] * x_1 53.74/14.49 >>> 53.74/14.49 53.74/14.49 <<< 53.74/14.49 POL(half(x_1)) = [[-I], [0A], [-I]] + [[0A, -I, -I], [0A, 0A, 0A], [0A, -I, 0A]] * x_1 53.74/14.49 >>> 53.74/14.49 53.74/14.49 <<< 53.74/14.49 POL(s(x_1)) = [[-I], [0A], [-I]] + [[0A, -I, 0A], [0A, -I, 1A], [0A, 0A, 0A]] * x_1 53.74/14.49 >>> 53.74/14.49 53.74/14.49 <<< 53.74/14.49 POL(p(x_1)) = [[-I], [0A], [-I]] + [[0A, -I, -I], [-I, -I, 0A], [0A, -I, -I]] * x_1 53.74/14.49 >>> 53.74/14.49 53.74/14.49 53.74/14.49 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (39) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 P is empty. 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (40) PisEmptyProof (EQUIVALENT) 53.74/14.49 The TRS P is empty. Hence, there is no (P,Q,R) chain. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (41) 53.74/14.49 YES 53.74/14.49 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (42) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 LOG(s(x1)) -> LOG(half(s(x1))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 log(s(x1)) -> s(log(half(s(x1)))) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (43) UsableRulesProof (EQUIVALENT) 53.74/14.49 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. 53.74/14.49 ---------------------------------------- 53.74/14.49 53.74/14.49 (44) 53.74/14.49 Obligation: 53.74/14.49 Q DP problem: 53.74/14.49 The TRS P consists of the following rules: 53.74/14.49 53.74/14.49 LOG(s(x1)) -> LOG(half(s(x1))) 53.74/14.49 53.74/14.49 The TRS R consists of the following rules: 53.74/14.49 53.74/14.49 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.49 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.49 half(s(0(x1))) -> 0(x1) 53.74/14.49 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.49 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.49 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.49 53.74/14.49 Q is empty. 53.74/14.49 We have to consider all minimal (P,Q,R)-chains. 53.74/14.49 ---------------------------------------- 53.74/14.50 53.74/14.50 (45) QDPOrderProof (EQUIVALENT) 53.74/14.50 We use the reduction pair processor [LPAR04,JAR06]. 53.74/14.50 53.74/14.50 53.74/14.50 The following pairs can be oriented strictly and are deleted. 53.74/14.50 53.74/14.50 LOG(s(x1)) -> LOG(half(s(x1))) 53.74/14.50 The remaining pairs can at least be oriented weakly. 53.74/14.50 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 53.74/14.50 53.74/14.50 POL( LOG_1(x_1) ) = x_1 + 2 53.74/14.50 POL( s_1(x_1) ) = x_1 + 1 53.74/14.50 POL( p_1(x_1) ) = max{0, x_1 - 1} 53.74/14.50 POL( half_1(x_1) ) = max{0, x_1 - 1} 53.74/14.50 POL( 0_1(x_1) ) = max{0, -2} 53.74/14.50 53.74/14.50 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 53.74/14.50 53.74/14.50 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.50 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.50 half(s(0(x1))) -> 0(x1) 53.74/14.50 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.50 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.50 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.50 53.74/14.50 53.74/14.50 ---------------------------------------- 53.74/14.50 53.74/14.50 (46) 53.74/14.50 Obligation: 53.74/14.50 Q DP problem: 53.74/14.50 P is empty. 53.74/14.50 The TRS R consists of the following rules: 53.74/14.50 53.74/14.50 s(s(p(s(x1)))) -> s(s(x1)) 53.74/14.50 half(0(x1)) -> 0(s(s(half(x1)))) 53.74/14.50 half(s(0(x1))) -> 0(x1) 53.74/14.50 half(s(s(x1))) -> s(half(p(s(s(x1))))) 53.74/14.50 half(half(s(s(s(s(x1)))))) -> s(s(half(half(x1)))) 53.74/14.50 p(s(s(s(x1)))) -> s(p(s(s(x1)))) 53.74/14.50 53.74/14.50 Q is empty. 53.74/14.50 We have to consider all minimal (P,Q,R)-chains. 53.74/14.50 ---------------------------------------- 53.74/14.50 53.74/14.50 (47) PisEmptyProof (EQUIVALENT) 53.74/14.50 The TRS P is empty. Hence, there is no (P,Q,R) chain. 53.74/14.50 ---------------------------------------- 53.74/14.50 53.74/14.50 (48) 53.74/14.50 YES 53.97/14.59 EOF