6.19/2.50 YES 6.55/2.51 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 6.55/2.51 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 6.55/2.51 6.55/2.51 6.55/2.51 Termination w.r.t. Q of the given QTRS could be proven: 6.55/2.51 6.55/2.51 (0) QTRS 6.55/2.51 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 6.55/2.51 (2) QDP 6.55/2.51 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 6.55/2.51 (4) AND 6.55/2.51 (5) QDP 6.55/2.51 (6) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (7) QDP 6.55/2.51 (8) QReductionProof [EQUIVALENT, 2 ms] 6.55/2.51 (9) QDP 6.55/2.51 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.55/2.51 (11) YES 6.55/2.51 (12) QDP 6.55/2.51 (13) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (14) QDP 6.55/2.51 (15) QReductionProof [EQUIVALENT, 1 ms] 6.55/2.51 (16) QDP 6.55/2.51 (17) TransformationProof [EQUIVALENT, 0 ms] 6.55/2.51 (18) QDP 6.55/2.51 (19) TransformationProof [EQUIVALENT, 0 ms] 6.55/2.51 (20) QDP 6.55/2.51 (21) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (22) QDP 6.55/2.51 (23) QReductionProof [EQUIVALENT, 0 ms] 6.55/2.51 (24) QDP 6.55/2.51 (25) TransformationProof [EQUIVALENT, 0 ms] 6.55/2.51 (26) QDP 6.55/2.51 (27) TransformationProof [EQUIVALENT, 0 ms] 6.55/2.51 (28) QDP 6.55/2.51 (29) TransformationProof [EQUIVALENT, 0 ms] 6.55/2.51 (30) QDP 6.55/2.51 (31) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (32) QDP 6.55/2.51 (33) QReductionProof [EQUIVALENT, 0 ms] 6.55/2.51 (34) QDP 6.55/2.51 (35) QDPOrderProof [EQUIVALENT, 37 ms] 6.55/2.51 (36) QDP 6.55/2.51 (37) QDPOrderProof [EQUIVALENT, 14 ms] 6.55/2.51 (38) QDP 6.55/2.51 (39) PisEmptyProof [EQUIVALENT, 0 ms] 6.55/2.51 (40) YES 6.55/2.51 (41) QDP 6.55/2.51 (42) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (43) QDP 6.55/2.51 (44) QReductionProof [EQUIVALENT, 0 ms] 6.55/2.51 (45) QDP 6.55/2.51 (46) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.55/2.51 (47) YES 6.55/2.51 (48) QDP 6.55/2.51 (49) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (50) QDP 6.55/2.51 (51) QReductionProof [EQUIVALENT, 0 ms] 6.55/2.51 (52) QDP 6.55/2.51 (53) QDPSizeChangeProof [EQUIVALENT, 0 ms] 6.55/2.51 (54) YES 6.55/2.51 (55) QDP 6.55/2.51 (56) UsableRulesProof [EQUIVALENT, 0 ms] 6.55/2.51 (57) QDP 6.55/2.51 (58) QReductionProof [EQUIVALENT, 0 ms] 6.55/2.51 (59) QDP 6.55/2.51 (60) QDPOrderProof [EQUIVALENT, 34 ms] 6.55/2.51 (61) QDP 6.55/2.51 (62) QDPOrderProof [EQUIVALENT, 18 ms] 6.55/2.51 (63) QDP 6.55/2.51 (64) PisEmptyProof [EQUIVALENT, 0 ms] 6.55/2.51 (65) YES 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (0) 6.55/2.51 Obligation: 6.55/2.51 Q restricted rewrite system: 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (1) DependencyPairsProof (EQUIVALENT) 6.55/2.51 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (2) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 EVEN(s(s(x))) -> EVEN(x) 6.55/2.51 HALF(s(s(x))) -> HALF(x) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))) 6.55/2.51 PLUS(s(x), s(y)) -> IF(gt(x, y), x, y) 6.55/2.51 PLUS(s(x), s(y)) -> GT(x, y) 6.55/2.51 PLUS(s(x), s(y)) -> IF(not(gt(x, y)), id(x), id(y)) 6.55/2.51 PLUS(s(x), s(y)) -> NOT(gt(x, y)) 6.55/2.51 PLUS(s(x), s(y)) -> ID(x) 6.55/2.51 PLUS(s(x), s(y)) -> ID(y) 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 PLUS(s(x), x) -> IF(gt(x, x), id(x), id(x)) 6.55/2.51 PLUS(s(x), x) -> GT(x, x) 6.55/2.51 PLUS(s(x), x) -> ID(x) 6.55/2.51 PLUS(id(x), s(y)) -> PLUS(x, if(gt(s(y), y), y, s(y))) 6.55/2.51 PLUS(id(x), s(y)) -> IF(gt(s(y), y), y, s(y)) 6.55/2.51 PLUS(id(x), s(y)) -> GT(s(y), y) 6.55/2.51 NOT(x) -> IF(x, false, true) 6.55/2.51 GT(s(x), s(y)) -> GT(x, y) 6.55/2.51 TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y) 6.55/2.51 TIMES(s(x), y) -> EVEN(s(x)) 6.55/2.51 IF_TIMES(true, s(x), y) -> PLUS(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y) 6.55/2.51 IF_TIMES(true, s(x), y) -> HALF(s(x)) 6.55/2.51 IF_TIMES(false, s(x), y) -> PLUS(y, times(x, y)) 6.55/2.51 IF_TIMES(false, s(x), y) -> TIMES(x, y) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (3) DependencyGraphProof (EQUIVALENT) 6.55/2.51 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 17 less nodes. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (4) 6.55/2.51 Complex Obligation (AND) 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (5) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 GT(s(x), s(y)) -> GT(x, y) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (6) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (7) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 GT(s(x), s(y)) -> GT(x, y) 6.55/2.51 6.55/2.51 R is empty. 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (8) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (9) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 GT(s(x), s(y)) -> GT(x, y) 6.55/2.51 6.55/2.51 R is empty. 6.55/2.51 Q is empty. 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (10) QDPSizeChangeProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 6.55/2.51 From the DPs we obtained the following set of size-change graphs: 6.55/2.51 *GT(s(x), s(y)) -> GT(x, y) 6.55/2.51 The graph contains the following edges 1 > 1, 2 > 2 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (11) 6.55/2.51 YES 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (12) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (13) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (14) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (15) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (16) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (17) TransformationProof (EQUIVALENT) 6.55/2.51 By rewriting [LPAR04] the rule PLUS(s(x), x) -> PLUS(if(gt(x, x), id(x), id(x)), s(x)) at position [0,1] we obtained the following new rules [LPAR04]: 6.55/2.51 6.55/2.51 (PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x)),PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x))) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (18) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))) 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x)) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (19) TransformationProof (EQUIVALENT) 6.55/2.51 By rewriting [LPAR04] the rule PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))) at position [1,0] we obtained the following new rules [LPAR04]: 6.55/2.51 6.55/2.51 (PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y))),PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y)))) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (20) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (21) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (22) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (23) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 not(x0) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (24) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (25) TransformationProof (EQUIVALENT) 6.55/2.51 By rewriting [LPAR04] the rule PLUS(s(x), x) -> PLUS(if(gt(x, x), x, id(x)), s(x)) at position [0,2] we obtained the following new rules [LPAR04]: 6.55/2.51 6.55/2.51 (PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)),PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x))) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (26) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y))) 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (27) TransformationProof (EQUIVALENT) 6.55/2.51 By rewriting [LPAR04] the rule PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), id(x), id(y))) at position [1,1] we obtained the following new rules [LPAR04]: 6.55/2.51 6.55/2.51 (PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, id(y))),PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, id(y)))) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (28) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, id(y))) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (29) TransformationProof (EQUIVALENT) 6.55/2.51 By rewriting [LPAR04] the rule PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, id(y))) at position [1,2] we obtained the following new rules [LPAR04]: 6.55/2.51 6.55/2.51 (PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y)),PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y))) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (30) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y)) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 id(x) -> x 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (31) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (32) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y)) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (33) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 id(x0) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (34) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)) 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y)) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (35) QDPOrderProof (EQUIVALENT) 6.55/2.51 We use the reduction pair processor [LPAR04,JAR06]. 6.55/2.51 6.55/2.51 6.55/2.51 The following pairs can be oriented strictly and are deleted. 6.55/2.51 6.55/2.51 PLUS(s(x), x) -> PLUS(if(gt(x, x), x, x), s(x)) 6.55/2.51 The remaining pairs can at least be oriented weakly. 6.55/2.51 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(PLUS(x_1, x_2)) = [[-I]] + [[1A]] * x_1 + [[0A]] * x_2 6.55/2.51 >>> 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(s(x_1)) = [[-I]] + [[1A]] * x_1 6.55/2.51 >>> 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(if(x_1, x_2, x_3)) = [[-I]] + [[-I]] * x_1 + [[0A]] * x_2 + [[0A]] * x_3 6.55/2.51 >>> 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(gt(x_1, x_2)) = [[-I]] + [[3A]] * x_1 + [[-I]] * x_2 6.55/2.51 >>> 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(false) = [[0A]] 6.55/2.51 >>> 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(true) = [[5A]] 6.55/2.51 >>> 6.55/2.51 6.55/2.51 <<< 6.55/2.51 POL(zero) = [[2A]] 6.55/2.51 >>> 6.55/2.51 6.55/2.51 6.55/2.51 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.55/2.51 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (36) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y)) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (37) QDPOrderProof (EQUIVALENT) 6.55/2.51 We use the reduction pair processor [LPAR04,JAR06]. 6.55/2.51 6.55/2.51 6.55/2.51 The following pairs can be oriented strictly and are deleted. 6.55/2.51 6.55/2.51 PLUS(s(x), s(y)) -> PLUS(if(gt(x, y), x, y), if(if(gt(x, y), false, true), x, y)) 6.55/2.51 The remaining pairs can at least be oriented weakly. 6.55/2.51 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 6.55/2.51 6.55/2.51 POL( PLUS_2(x_1, x_2) ) = max{0, 2x_1 + 2x_2 - 2} 6.55/2.51 POL( if_3(x_1, ..., x_3) ) = x_2 + x_3 6.55/2.51 POL( gt_2(x_1, x_2) ) = 0 6.55/2.51 POL( s_1(x_1) ) = 2x_1 + 1 6.55/2.51 POL( zero ) = 0 6.55/2.51 POL( true ) = 0 6.55/2.51 POL( false ) = 0 6.55/2.51 6.55/2.51 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.55/2.51 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (38) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 P is empty. 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (39) PisEmptyProof (EQUIVALENT) 6.55/2.51 The TRS P is empty. Hence, there is no (P,Q,R) chain. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (40) 6.55/2.51 YES 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (41) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 HALF(s(s(x))) -> HALF(x) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (42) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (43) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 HALF(s(s(x))) -> HALF(x) 6.55/2.51 6.55/2.51 R is empty. 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (44) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (45) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 HALF(s(s(x))) -> HALF(x) 6.55/2.51 6.55/2.51 R is empty. 6.55/2.51 Q is empty. 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (46) QDPSizeChangeProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 6.55/2.51 From the DPs we obtained the following set of size-change graphs: 6.55/2.51 *HALF(s(s(x))) -> HALF(x) 6.55/2.51 The graph contains the following edges 1 > 1 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (47) 6.55/2.51 YES 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (48) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 EVEN(s(s(x))) -> EVEN(x) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (49) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (50) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 EVEN(s(s(x))) -> EVEN(x) 6.55/2.51 6.55/2.51 R is empty. 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (51) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (52) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 EVEN(s(s(x))) -> EVEN(x) 6.55/2.51 6.55/2.51 R is empty. 6.55/2.51 Q is empty. 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (53) QDPSizeChangeProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 6.55/2.51 From the DPs we obtained the following set of size-change graphs: 6.55/2.51 *EVEN(s(s(x))) -> EVEN(x) 6.55/2.51 The graph contains the following edges 1 > 1 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (54) 6.55/2.51 YES 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (55) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y) 6.55/2.51 IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y) 6.55/2.51 IF_TIMES(false, s(x), y) -> TIMES(x, y) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 even(0) -> true 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 half(0) -> 0 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 plus(s(x), s(y)) -> s(s(plus(if(gt(x, y), x, y), if(not(gt(x, y)), id(x), id(y))))) 6.55/2.51 plus(s(x), x) -> plus(if(gt(x, x), id(x), id(x)), s(x)) 6.55/2.51 plus(zero, y) -> y 6.55/2.51 plus(id(x), s(y)) -> s(plus(x, if(gt(s(y), y), y, s(y)))) 6.55/2.51 id(x) -> x 6.55/2.51 if(true, x, y) -> x 6.55/2.51 if(false, x, y) -> y 6.55/2.51 not(x) -> if(x, false, true) 6.55/2.51 gt(s(x), zero) -> true 6.55/2.51 gt(zero, y) -> false 6.55/2.51 gt(s(x), s(y)) -> gt(x, y) 6.55/2.51 times(0, y) -> 0 6.55/2.51 times(s(x), y) -> if_times(even(s(x)), s(x), y) 6.55/2.51 if_times(true, s(x), y) -> plus(times(half(s(x)), y), times(half(s(x)), y)) 6.55/2.51 if_times(false, s(x), y) -> plus(y, times(x, y)) 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (56) UsableRulesProof (EQUIVALENT) 6.55/2.51 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. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (57) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y) 6.55/2.51 IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y) 6.55/2.51 IF_TIMES(false, s(x), y) -> TIMES(x, y) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 half(0) -> 0 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 even(0) -> true 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (58) QReductionProof (EQUIVALENT) 6.55/2.51 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 6.55/2.51 6.55/2.51 plus(s(x0), s(x1)) 6.55/2.51 plus(s(x0), x0) 6.55/2.51 plus(zero, x0) 6.55/2.51 id(x0) 6.55/2.51 if(true, x0, x1) 6.55/2.51 if(false, x0, x1) 6.55/2.51 not(x0) 6.55/2.51 gt(s(x0), zero) 6.55/2.51 gt(zero, x0) 6.55/2.51 gt(s(x0), s(x1)) 6.55/2.51 times(0, x0) 6.55/2.51 times(s(x0), x1) 6.55/2.51 if_times(true, s(x0), x1) 6.55/2.51 if_times(false, s(x0), x1) 6.55/2.51 6.55/2.51 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (59) 6.55/2.51 Obligation: 6.55/2.51 Q DP problem: 6.55/2.51 The TRS P consists of the following rules: 6.55/2.51 6.55/2.51 TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y) 6.55/2.51 IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y) 6.55/2.51 IF_TIMES(false, s(x), y) -> TIMES(x, y) 6.55/2.51 6.55/2.51 The TRS R consists of the following rules: 6.55/2.51 6.55/2.51 half(s(s(x))) -> s(half(x)) 6.55/2.51 half(0) -> 0 6.55/2.51 even(s(0)) -> false 6.55/2.51 even(s(s(x))) -> even(x) 6.55/2.51 even(0) -> true 6.55/2.51 6.55/2.51 The set Q consists of the following terms: 6.55/2.51 6.55/2.51 even(0) 6.55/2.51 even(s(0)) 6.55/2.51 even(s(s(x0))) 6.55/2.51 half(0) 6.55/2.51 half(s(s(x0))) 6.55/2.51 6.55/2.51 We have to consider all minimal (P,Q,R)-chains. 6.55/2.51 ---------------------------------------- 6.55/2.51 6.55/2.51 (60) QDPOrderProof (EQUIVALENT) 6.55/2.51 We use the reduction pair processor [LPAR04,JAR06]. 6.55/2.51 6.55/2.51 6.55/2.51 The following pairs can be oriented strictly and are deleted. 6.55/2.51 6.55/2.51 IF_TIMES(false, s(x), y) -> TIMES(x, y) 6.55/2.51 The remaining pairs can at least be oriented weakly. 6.55/2.51 Used ordering: Combined order from the following AFS and order. 6.55/2.52 TIMES(x1, x2) = TIMES(x1, x2) 6.55/2.52 6.55/2.52 s(x1) = s(x1) 6.55/2.52 6.55/2.52 IF_TIMES(x1, x2, x3) = IF_TIMES(x2, x3) 6.55/2.52 6.55/2.52 even(x1) = even 6.55/2.52 6.55/2.52 true = true 6.55/2.52 6.55/2.52 half(x1) = x1 6.55/2.52 6.55/2.52 false = false 6.55/2.52 6.55/2.52 0 = 0 6.55/2.52 6.55/2.52 6.55/2.52 Recursive path order with status [RPO]. 6.55/2.52 Quasi-Precedence: [TIMES_2, IF_TIMES_2, true] > s_1 > false 6.55/2.52 [TIMES_2, IF_TIMES_2, true] > even > false 6.55/2.52 6.55/2.52 Status: TIMES_2: multiset status 6.55/2.52 s_1: multiset status 6.55/2.52 IF_TIMES_2: multiset status 6.55/2.52 even: multiset status 6.55/2.52 true: multiset status 6.55/2.52 false: multiset status 6.55/2.52 0: multiset status 6.55/2.52 6.55/2.52 6.55/2.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.55/2.52 6.55/2.52 half(s(s(x))) -> s(half(x)) 6.55/2.52 half(0) -> 0 6.55/2.52 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (61) 6.55/2.52 Obligation: 6.55/2.52 Q DP problem: 6.55/2.52 The TRS P consists of the following rules: 6.55/2.52 6.55/2.52 TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y) 6.55/2.52 IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y) 6.55/2.52 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 half(s(s(x))) -> s(half(x)) 6.55/2.52 half(0) -> 0 6.55/2.52 even(s(0)) -> false 6.55/2.52 even(s(s(x))) -> even(x) 6.55/2.52 even(0) -> true 6.55/2.52 6.55/2.52 The set Q consists of the following terms: 6.55/2.52 6.55/2.52 even(0) 6.55/2.52 even(s(0)) 6.55/2.52 even(s(s(x0))) 6.55/2.52 half(0) 6.55/2.52 half(s(s(x0))) 6.55/2.52 6.55/2.52 We have to consider all minimal (P,Q,R)-chains. 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (62) QDPOrderProof (EQUIVALENT) 6.55/2.52 We use the reduction pair processor [LPAR04,JAR06]. 6.55/2.52 6.55/2.52 6.55/2.52 The following pairs can be oriented strictly and are deleted. 6.55/2.52 6.55/2.52 TIMES(s(x), y) -> IF_TIMES(even(s(x)), s(x), y) 6.55/2.52 IF_TIMES(true, s(x), y) -> TIMES(half(s(x)), y) 6.55/2.52 The remaining pairs can at least be oriented weakly. 6.55/2.52 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 6.55/2.52 6.55/2.52 POL( IF_TIMES_3(x_1, ..., x_3) ) = max{0, x_1 + 2x_2 + 2x_3 - 1} 6.55/2.52 POL( even_1(x_1) ) = 1 6.55/2.52 POL( s_1(x_1) ) = 2x_1 + 2 6.55/2.52 POL( 0 ) = 0 6.55/2.52 POL( false ) = 1 6.55/2.52 POL( TIMES_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 6.55/2.52 POL( half_1(x_1) ) = max{0, x_1 - 2} 6.55/2.52 POL( true ) = 0 6.55/2.52 6.55/2.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 6.55/2.52 6.55/2.52 even(s(0)) -> false 6.55/2.52 even(s(s(x))) -> even(x) 6.55/2.52 half(s(s(x))) -> s(half(x)) 6.55/2.52 half(0) -> 0 6.55/2.52 even(0) -> true 6.55/2.52 6.55/2.52 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (63) 6.55/2.52 Obligation: 6.55/2.52 Q DP problem: 6.55/2.52 P is empty. 6.55/2.52 The TRS R consists of the following rules: 6.55/2.52 6.55/2.52 half(s(s(x))) -> s(half(x)) 6.55/2.52 half(0) -> 0 6.55/2.52 even(s(0)) -> false 6.55/2.52 even(s(s(x))) -> even(x) 6.55/2.52 even(0) -> true 6.55/2.52 6.55/2.52 The set Q consists of the following terms: 6.55/2.52 6.55/2.52 even(0) 6.55/2.52 even(s(0)) 6.55/2.52 even(s(s(x0))) 6.55/2.52 half(0) 6.55/2.52 half(s(s(x0))) 6.55/2.52 6.55/2.52 We have to consider all minimal (P,Q,R)-chains. 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (64) PisEmptyProof (EQUIVALENT) 6.55/2.52 The TRS P is empty. Hence, there is no (P,Q,R) chain. 6.55/2.52 ---------------------------------------- 6.55/2.52 6.55/2.52 (65) 6.55/2.52 YES 6.71/2.61 EOF