/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.itrs /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.itrs # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty Termination of the given ITRS could be proven: (0) ITRS (1) ITRStoIDPProof [EQUIVALENT, 0 ms] (2) IDP (3) UsableRulesProof [EQUIVALENT, 0 ms] (4) IDP (5) IDPtoQDPProof [SOUND, 26 ms] (6) QDP (7) UsableRulesProof [EQUIVALENT, 0 ms] (8) QDP (9) QReductionProof [EQUIVALENT, 0 ms] (10) QDP (11) TransformationProof [EQUIVALENT, 0 ms] (12) QDP (13) TransformationProof [EQUIVALENT, 0 ms] (14) QDP (15) TransformationProof [EQUIVALENT, 0 ms] (16) QDP (17) DependencyGraphProof [EQUIVALENT, 0 ms] (18) QDP (19) TransformationProof [EQUIVALENT, 0 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) QDP (23) TransformationProof [EQUIVALENT, 0 ms] (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) TransformationProof [EQUIVALENT, 0 ms] (30) QDP (31) DependencyGraphProof [EQUIVALENT, 0 ms] (32) QDP (33) TransformationProof [EQUIVALENT, 0 ms] (34) QDP (35) DependencyGraphProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) DependencyGraphProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) DependencyGraphProof [EQUIVALENT, 0 ms] (44) QDP (45) TransformationProof [EQUIVALENT, 0 ms] (46) QDP (47) TransformationProof [EQUIVALENT, 0 ms] (48) QDP (49) DependencyGraphProof [EQUIVALENT, 0 ms] (50) QDP (51) TransformationProof [EQUIVALENT, 0 ms] (52) QDP (53) DependencyGraphProof [EQUIVALENT, 0 ms] (54) QDP (55) TransformationProof [EQUIVALENT, 0 ms] (56) QDP (57) DependencyGraphProof [EQUIVALENT, 0 ms] (58) QDP (59) TransformationProof [EQUIVALENT, 0 ms] (60) QDP (61) DependencyGraphProof [EQUIVALENT, 0 ms] (62) QDP (63) TransformationProof [EQUIVALENT, 0 ms] (64) QDP (65) TransformationProof [EQUIVALENT, 0 ms] (66) QDP (67) DependencyGraphProof [EQUIVALENT, 0 ms] (68) QDP (69) TransformationProof [EQUIVALENT, 0 ms] (70) QDP (71) DependencyGraphProof [EQUIVALENT, 0 ms] (72) QDP (73) TransformationProof [EQUIVALENT, 0 ms] (74) QDP (75) DependencyGraphProof [EQUIVALENT, 0 ms] (76) QDP (77) TransformationProof [EQUIVALENT, 0 ms] (78) QDP (79) DependencyGraphProof [EQUIVALENT, 0 ms] (80) QDP (81) UsableRulesProof [EQUIVALENT, 0 ms] (82) QDP (83) TransformationProof [EQUIVALENT, 0 ms] (84) QDP (85) UsableRulesProof [EQUIVALENT, 0 ms] (86) QDP (87) TransformationProof [EQUIVALENT, 0 ms] (88) QDP (89) DependencyGraphProof [EQUIVALENT, 0 ms] (90) QDP (91) UsableRulesProof [EQUIVALENT, 0 ms] (92) QDP (93) QReductionProof [EQUIVALENT, 0 ms] (94) QDP (95) TransformationProof [EQUIVALENT, 0 ms] (96) QDP (97) DependencyGraphProof [EQUIVALENT, 0 ms] (98) QDP (99) TransformationProof [EQUIVALENT, 0 ms] (100) QDP (101) DependencyGraphProof [EQUIVALENT, 0 ms] (102) QDP (103) UsableRulesProof [EQUIVALENT, 0 ms] (104) QDP (105) QReductionProof [EQUIVALENT, 0 ms] (106) QDP (107) TransformationProof [EQUIVALENT, 0 ms] (108) QDP (109) DependencyGraphProof [EQUIVALENT, 0 ms] (110) QDP (111) UsableRulesProof [EQUIVALENT, 0 ms] (112) QDP (113) QReductionProof [EQUIVALENT, 0 ms] (114) QDP (115) TransformationProof [EQUIVALENT, 0 ms] (116) QDP (117) UsableRulesProof [EQUIVALENT, 0 ms] (118) QDP (119) TransformationProof [EQUIVALENT, 0 ms] (120) QDP (121) UsableRulesProof [EQUIVALENT, 0 ms] (122) QDP (123) QReductionProof [EQUIVALENT, 0 ms] (124) QDP (125) TransformationProof [EQUIVALENT, 0 ms] (126) QDP (127) TransformationProof [EQUIVALENT, 0 ms] (128) QDP (129) TransformationProof [EQUIVALENT, 0 ms] (130) QDP (131) TransformationProof [EQUIVALENT, 0 ms] (132) QDP (133) MRRProof [EQUIVALENT, 4 ms] (134) QDP (135) QDPOrderProof [EQUIVALENT, 83 ms] (136) QDP (137) DependencyGraphProof [EQUIVALENT, 0 ms] (138) QDP (139) TransformationProof [EQUIVALENT, 0 ms] (140) QDP (141) TransformationProof [EQUIVALENT, 0 ms] (142) QDP (143) TransformationProof [EQUIVALENT, 0 ms] (144) QDP (145) UsableRulesProof [EQUIVALENT, 0 ms] (146) QDP (147) TransformationProof [EQUIVALENT, 0 ms] (148) QDP (149) DependencyGraphProof [EQUIVALENT, 0 ms] (150) QDP (151) UsableRulesProof [EQUIVALENT, 0 ms] (152) QDP (153) QReductionProof [EQUIVALENT, 0 ms] (154) QDP (155) TransformationProof [EQUIVALENT, 0 ms] (156) QDP (157) TransformationProof [EQUIVALENT, 0 ms] (158) QDP (159) MRRProof [EQUIVALENT, 3 ms] (160) QDP (161) DependencyGraphProof [EQUIVALENT, 0 ms] (162) TRUE ---------------------------------------- (0) Obligation: ITRS problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The TRS R consists of the following rules: eval(x, y) -> Cond_eval(x > 0 && y > 0, x, y) Cond_eval(TRUE, x, y) -> eval(x - 1, x) eval(x, y) -> Cond_eval1(x > 0 && y > 0, x, y) Cond_eval1(TRUE, x, y) -> eval(y - 2, x + 1) The set Q consists of the following terms: eval(x0, x1) Cond_eval(TRUE, x0, x1) Cond_eval1(TRUE, x0, x1) ---------------------------------------- (1) ITRStoIDPProof (EQUIVALENT) Added dependency pairs ---------------------------------------- (2) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Boolean, Integer The ITRS R consists of the following rules: eval(x, y) -> Cond_eval(x > 0 && y > 0, x, y) Cond_eval(TRUE, x, y) -> eval(x - 1, x) eval(x, y) -> Cond_eval1(x > 0 && y > 0, x, y) Cond_eval1(TRUE, x, y) -> eval(y - 2, x + 1) The integer pair graph contains the following rules and edges: (0): EVAL(x[0], y[0]) -> COND_EVAL(x[0] > 0 && y[0] > 0, x[0], y[0]) (1): COND_EVAL(TRUE, x[1], y[1]) -> EVAL(x[1] - 1, x[1]) (2): EVAL(x[2], y[2]) -> COND_EVAL1(x[2] > 0 && y[2] > 0, x[2], y[2]) (3): COND_EVAL1(TRUE, x[3], y[3]) -> EVAL(y[3] - 2, x[3] + 1) (0) -> (1), if (x[0] > 0 && y[0] > 0 & x[0] ->^* x[1] & y[0] ->^* y[1]) (1) -> (0), if (x[1] - 1 ->^* x[0] & x[1] ->^* y[0]) (1) -> (2), if (x[1] - 1 ->^* x[2] & x[1] ->^* y[2]) (2) -> (3), if (x[2] > 0 && y[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) (3) -> (0), if (y[3] - 2 ->^* x[0] & x[3] + 1 ->^* y[0]) (3) -> (2), if (y[3] - 2 ->^* x[2] & x[3] + 1 ->^* y[2]) The set Q consists of the following terms: eval(x0, x1) Cond_eval(TRUE, x0, x1) Cond_eval1(TRUE, x0, x1) ---------------------------------------- (3) UsableRulesProof (EQUIVALENT) 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) Obligation: IDP problem: The following function symbols are pre-defined: <<< & ~ Bwand: (Integer, Integer) -> Integer >= ~ Ge: (Integer, Integer) -> Boolean | ~ Bwor: (Integer, Integer) -> Integer / ~ Div: (Integer, Integer) -> Integer != ~ Neq: (Integer, Integer) -> Boolean && ~ Land: (Boolean, Boolean) -> Boolean ! ~ Lnot: (Boolean) -> Boolean = ~ Eq: (Integer, Integer) -> Boolean <= ~ Le: (Integer, Integer) -> Boolean ^ ~ Bwxor: (Integer, Integer) -> Integer % ~ Mod: (Integer, Integer) -> Integer > ~ Gt: (Integer, Integer) -> Boolean + ~ Add: (Integer, Integer) -> Integer -1 ~ UnaryMinus: (Integer) -> Integer < ~ Lt: (Integer, Integer) -> Boolean || ~ Lor: (Boolean, Boolean) -> Boolean - ~ Sub: (Integer, Integer) -> Integer ~ ~ Bwnot: (Integer) -> Integer * ~ Mul: (Integer, Integer) -> Integer >>> The following domains are used: Boolean, Integer R is empty. The integer pair graph contains the following rules and edges: (0): EVAL(x[0], y[0]) -> COND_EVAL(x[0] > 0 && y[0] > 0, x[0], y[0]) (1): COND_EVAL(TRUE, x[1], y[1]) -> EVAL(x[1] - 1, x[1]) (2): EVAL(x[2], y[2]) -> COND_EVAL1(x[2] > 0 && y[2] > 0, x[2], y[2]) (3): COND_EVAL1(TRUE, x[3], y[3]) -> EVAL(y[3] - 2, x[3] + 1) (0) -> (1), if (x[0] > 0 && y[0] > 0 & x[0] ->^* x[1] & y[0] ->^* y[1]) (1) -> (0), if (x[1] - 1 ->^* x[0] & x[1] ->^* y[0]) (1) -> (2), if (x[1] - 1 ->^* x[2] & x[1] ->^* y[2]) (2) -> (3), if (x[2] > 0 && y[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) (3) -> (0), if (y[3] - 2 ->^* x[0] & x[3] + 1 ->^* y[0]) (3) -> (2), if (y[3] - 2 ->^* x[2] & x[3] + 1 ->^* y[2]) The set Q consists of the following terms: eval(x0, x1) Cond_eval(TRUE, x0, x1) Cond_eval1(TRUE, x0, x1) ---------------------------------------- (5) IDPtoQDPProof (SOUND) Represented integers and predefined function symbols by Terms ---------------------------------------- (6) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(x[0], y[0]) -> COND_EVAL(and(greater_int(x[0], pos(01)), greater_int(y[0], pos(01))), x[0], y[0]) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(x[2], y[2]) -> COND_EVAL1(and(greater_int(x[2], pos(01)), greater_int(y[2], pos(01))), x[2], y[2]) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true greater_int(pos(01), pos(01)) -> false greater_int(pos(01), neg(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(neg(01), neg(01)) -> false greater_int(pos(01), pos(s(y))) -> false greater_int(neg(01), pos(s(y))) -> false greater_int(pos(01), neg(s(y))) -> true greater_int(neg(01), neg(s(y))) -> true greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false greater_int(pos(s(x)), neg(01)) -> true greater_int(neg(s(x)), neg(01)) -> false greater_int(pos(s(x)), neg(s(y))) -> true greater_int(neg(s(x)), pos(s(y))) -> false greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y)) greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y)) minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), neg(y)) -> minus_nat(y, x) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(neg(x), pos(y)) -> minus_nat(y, x) plus_int(neg(x), neg(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) The set Q consists of the following terms: eval(x0, x1) Cond_eval(true, x0, x1) Cond_eval1(true, x0, x1) and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (7) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(x[0], y[0]) -> COND_EVAL(and(greater_int(x[0], pos(01)), greater_int(y[0], pos(01))), x[0], y[0]) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(x[2], y[2]) -> COND_EVAL1(and(greater_int(x[2], pos(01)), greater_int(y[2], pos(01))), x[2], y[2]) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: eval(x0, x1) Cond_eval(true, x0, x1) Cond_eval1(true, x0, x1) and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. eval(x0, x1) Cond_eval(true, x0, x1) Cond_eval1(true, x0, x1) ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(x[0], y[0]) -> COND_EVAL(and(greater_int(x[0], pos(01)), greater_int(y[0], pos(01))), x[0], y[0]) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(x[2], y[2]) -> COND_EVAL1(and(greater_int(x[2], pos(01)), greater_int(y[2], pos(01))), x[2], y[2]) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(x[0], y[0]) -> COND_EVAL(and(greater_int(x[0], pos(01)), greater_int(y[0], pos(01))), x[0], y[0]) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), pos(01), y1),EVAL(pos(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), pos(01), y1)) (EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1),EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1)) (EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1),EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1)) (EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1),EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1)) (EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)),EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01))) (EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)),EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01))) (EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))),EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0)))) (EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))),EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0)))) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(x[2], y[2]) -> COND_EVAL1(and(greater_int(x[2], pos(01)), greater_int(y[2], pos(01))), x[2], y[2]) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), pos(01), y1) EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(x[2], y[2]) -> COND_EVAL1(and(greater_int(x[2], pos(01)), greater_int(y[2], pos(01))), x[2], y[2]) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1),EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1)) (EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1),EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1)) (EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1),EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1)) (EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1),EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1)) (EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)),EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01))) (EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)),EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01))) (EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))),EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0)))) (EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))),EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0)))) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), pos(01), y1) EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(pos(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), pos(01), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), pos(01)) -> COND_EVAL(and(false, false), pos(01), pos(01)),EVAL(pos(01), pos(01)) -> COND_EVAL(and(false, false), pos(01), pos(01))) (EVAL(pos(01), neg(01)) -> COND_EVAL(and(false, false), pos(01), neg(01)),EVAL(pos(01), neg(01)) -> COND_EVAL(and(false, false), pos(01), neg(01))) (EVAL(pos(01), pos(s(x0))) -> COND_EVAL(and(false, true), pos(01), pos(s(x0))),EVAL(pos(01), pos(s(x0))) -> COND_EVAL(and(false, true), pos(01), pos(s(x0)))) (EVAL(pos(01), neg(s(x0))) -> COND_EVAL(and(false, false), pos(01), neg(s(x0))),EVAL(pos(01), neg(s(x0))) -> COND_EVAL(and(false, false), pos(01), neg(s(x0)))) ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), pos(01)) -> COND_EVAL(and(false, false), pos(01), pos(01)) EVAL(pos(01), neg(01)) -> COND_EVAL(and(false, false), pos(01), neg(01)) EVAL(pos(01), pos(s(x0))) -> COND_EVAL(and(false, true), pos(01), pos(s(x0))) EVAL(pos(01), neg(s(x0))) -> COND_EVAL(and(false, false), pos(01), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(neg(01), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(01), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(neg(01), pos(01)) -> COND_EVAL(and(false, false), neg(01), pos(01)),EVAL(neg(01), pos(01)) -> COND_EVAL(and(false, false), neg(01), pos(01))) (EVAL(neg(01), neg(01)) -> COND_EVAL(and(false, false), neg(01), neg(01)),EVAL(neg(01), neg(01)) -> COND_EVAL(and(false, false), neg(01), neg(01))) (EVAL(neg(01), pos(s(x0))) -> COND_EVAL(and(false, true), neg(01), pos(s(x0))),EVAL(neg(01), pos(s(x0))) -> COND_EVAL(and(false, true), neg(01), pos(s(x0)))) (EVAL(neg(01), neg(s(x0))) -> COND_EVAL(and(false, false), neg(01), neg(s(x0))),EVAL(neg(01), neg(s(x0))) -> COND_EVAL(and(false, false), neg(01), neg(s(x0)))) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(neg(01), pos(01)) -> COND_EVAL(and(false, false), neg(01), pos(01)) EVAL(neg(01), neg(01)) -> COND_EVAL(and(false, false), neg(01), neg(01)) EVAL(neg(01), pos(s(x0))) -> COND_EVAL(and(false, true), neg(01), pos(s(x0))) EVAL(neg(01), neg(s(x0))) -> COND_EVAL(and(false, false), neg(01), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(pos(s(x0)), y1) -> COND_EVAL(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(s(y0)), pos(01)) -> COND_EVAL(and(true, false), pos(s(y0)), pos(01)),EVAL(pos(s(y0)), pos(01)) -> COND_EVAL(and(true, false), pos(s(y0)), pos(01))) (EVAL(pos(s(y0)), neg(01)) -> COND_EVAL(and(true, false), pos(s(y0)), neg(01)),EVAL(pos(s(y0)), neg(01)) -> COND_EVAL(and(true, false), pos(s(y0)), neg(01))) (EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(and(true, true), pos(s(y0)), pos(s(x0))),EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(and(true, true), pos(s(y0)), pos(s(x0)))) (EVAL(pos(s(y0)), neg(s(x0))) -> COND_EVAL(and(true, false), pos(s(y0)), neg(s(x0))),EVAL(pos(s(y0)), neg(s(x0))) -> COND_EVAL(and(true, false), pos(s(y0)), neg(s(x0)))) ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(01)) -> COND_EVAL(and(true, false), pos(s(y0)), pos(01)) EVAL(pos(s(y0)), neg(01)) -> COND_EVAL(and(true, false), pos(s(y0)), neg(01)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(and(true, true), pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), neg(s(x0))) -> COND_EVAL(and(true, false), pos(s(y0)), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(and(true, true), pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(and(true, true), pos(s(y0)), pos(s(x0))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))),EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0)))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(neg(s(x0)), y1) -> COND_EVAL(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(neg(s(y0)), pos(01)) -> COND_EVAL(and(false, false), neg(s(y0)), pos(01)),EVAL(neg(s(y0)), pos(01)) -> COND_EVAL(and(false, false), neg(s(y0)), pos(01))) (EVAL(neg(s(y0)), neg(01)) -> COND_EVAL(and(false, false), neg(s(y0)), neg(01)),EVAL(neg(s(y0)), neg(01)) -> COND_EVAL(and(false, false), neg(s(y0)), neg(01))) (EVAL(neg(s(y0)), pos(s(x0))) -> COND_EVAL(and(false, true), neg(s(y0)), pos(s(x0))),EVAL(neg(s(y0)), pos(s(x0))) -> COND_EVAL(and(false, true), neg(s(y0)), pos(s(x0)))) (EVAL(neg(s(y0)), neg(s(x0))) -> COND_EVAL(and(false, false), neg(s(y0)), neg(s(x0))),EVAL(neg(s(y0)), neg(s(x0))) -> COND_EVAL(and(false, false), neg(s(y0)), neg(s(x0)))) ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(neg(s(y0)), pos(01)) -> COND_EVAL(and(false, false), neg(s(y0)), pos(01)) EVAL(neg(s(y0)), neg(01)) -> COND_EVAL(and(false, false), neg(s(y0)), neg(01)) EVAL(neg(s(y0)), pos(s(x0))) -> COND_EVAL(and(false, true), neg(s(y0)), pos(s(x0))) EVAL(neg(s(y0)), neg(s(x0))) -> COND_EVAL(and(false, false), neg(s(y0)), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, pos(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, pos(01)) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), pos(01)) -> COND_EVAL(and(false, false), pos(01), pos(01)),EVAL(pos(01), pos(01)) -> COND_EVAL(and(false, false), pos(01), pos(01))) (EVAL(neg(01), pos(01)) -> COND_EVAL(and(false, false), neg(01), pos(01)),EVAL(neg(01), pos(01)) -> COND_EVAL(and(false, false), neg(01), pos(01))) (EVAL(pos(s(x0)), pos(01)) -> COND_EVAL(and(true, false), pos(s(x0)), pos(01)),EVAL(pos(s(x0)), pos(01)) -> COND_EVAL(and(true, false), pos(s(x0)), pos(01))) (EVAL(neg(s(x0)), pos(01)) -> COND_EVAL(and(false, false), neg(s(x0)), pos(01)),EVAL(neg(s(x0)), pos(01)) -> COND_EVAL(and(false, false), neg(s(x0)), pos(01))) ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), pos(01)) -> COND_EVAL(and(false, false), pos(01), pos(01)) EVAL(neg(01), pos(01)) -> COND_EVAL(and(false, false), neg(01), pos(01)) EVAL(pos(s(x0)), pos(01)) -> COND_EVAL(and(true, false), pos(s(x0)), pos(01)) EVAL(neg(s(x0)), pos(01)) -> COND_EVAL(and(false, false), neg(s(x0)), pos(01)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, neg(01)) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(01)) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), neg(01)) -> COND_EVAL(and(false, false), pos(01), neg(01)),EVAL(pos(01), neg(01)) -> COND_EVAL(and(false, false), pos(01), neg(01))) (EVAL(neg(01), neg(01)) -> COND_EVAL(and(false, false), neg(01), neg(01)),EVAL(neg(01), neg(01)) -> COND_EVAL(and(false, false), neg(01), neg(01))) (EVAL(pos(s(x0)), neg(01)) -> COND_EVAL(and(true, false), pos(s(x0)), neg(01)),EVAL(pos(s(x0)), neg(01)) -> COND_EVAL(and(true, false), pos(s(x0)), neg(01))) (EVAL(neg(s(x0)), neg(01)) -> COND_EVAL(and(false, false), neg(s(x0)), neg(01)),EVAL(neg(s(x0)), neg(01)) -> COND_EVAL(and(false, false), neg(s(x0)), neg(01))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), neg(01)) -> COND_EVAL(and(false, false), pos(01), neg(01)) EVAL(neg(01), neg(01)) -> COND_EVAL(and(false, false), neg(01), neg(01)) EVAL(pos(s(x0)), neg(01)) -> COND_EVAL(and(true, false), pos(s(x0)), neg(01)) EVAL(neg(s(x0)), neg(01)) -> COND_EVAL(and(false, false), neg(s(x0)), neg(01)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, pos(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), pos(s(y1))) -> COND_EVAL(and(false, true), pos(01), pos(s(y1))),EVAL(pos(01), pos(s(y1))) -> COND_EVAL(and(false, true), pos(01), pos(s(y1)))) (EVAL(neg(01), pos(s(y1))) -> COND_EVAL(and(false, true), neg(01), pos(s(y1))),EVAL(neg(01), pos(s(y1))) -> COND_EVAL(and(false, true), neg(01), pos(s(y1)))) (EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL(and(true, true), pos(s(x0)), pos(s(y1))),EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL(and(true, true), pos(s(x0)), pos(s(y1)))) (EVAL(neg(s(x0)), pos(s(y1))) -> COND_EVAL(and(false, true), neg(s(x0)), pos(s(y1))),EVAL(neg(s(x0)), pos(s(y1))) -> COND_EVAL(and(false, true), neg(s(x0)), pos(s(y1)))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), pos(s(y1))) -> COND_EVAL(and(false, true), pos(01), pos(s(y1))) EVAL(neg(01), pos(s(y1))) -> COND_EVAL(and(false, true), neg(01), pos(s(y1))) EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL(and(true, true), pos(s(x0)), pos(s(y1))) EVAL(neg(s(x0)), pos(s(y1))) -> COND_EVAL(and(false, true), neg(s(x0)), pos(s(y1))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL(and(true, true), pos(s(x0)), pos(s(y1))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL(and(true, true), pos(s(x0)), pos(s(y1))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL(true, pos(s(x0)), pos(s(y1))),EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0)))) ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, neg(s(x0))) -> COND_EVAL(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), neg(s(y1))) -> COND_EVAL(and(false, false), pos(01), neg(s(y1))),EVAL(pos(01), neg(s(y1))) -> COND_EVAL(and(false, false), pos(01), neg(s(y1)))) (EVAL(neg(01), neg(s(y1))) -> COND_EVAL(and(false, false), neg(01), neg(s(y1))),EVAL(neg(01), neg(s(y1))) -> COND_EVAL(and(false, false), neg(01), neg(s(y1)))) (EVAL(pos(s(x0)), neg(s(y1))) -> COND_EVAL(and(true, false), pos(s(x0)), neg(s(y1))),EVAL(pos(s(x0)), neg(s(y1))) -> COND_EVAL(and(true, false), pos(s(x0)), neg(s(y1)))) (EVAL(neg(s(x0)), neg(s(y1))) -> COND_EVAL(and(false, false), neg(s(x0)), neg(s(y1))),EVAL(neg(s(x0)), neg(s(y1))) -> COND_EVAL(and(false, false), neg(s(x0)), neg(s(y1)))) ---------------------------------------- (48) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), neg(s(y1))) -> COND_EVAL(and(false, false), pos(01), neg(s(y1))) EVAL(neg(01), neg(s(y1))) -> COND_EVAL(and(false, false), neg(01), neg(s(y1))) EVAL(pos(s(x0)), neg(s(y1))) -> COND_EVAL(and(true, false), pos(s(x0)), neg(s(y1))) EVAL(neg(s(x0)), neg(s(y1))) -> COND_EVAL(and(false, false), neg(s(x0)), neg(s(y1))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (49) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (50) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (51) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(pos(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), pos(01), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), pos(01)) -> COND_EVAL1(and(false, false), pos(01), pos(01)),EVAL(pos(01), pos(01)) -> COND_EVAL1(and(false, false), pos(01), pos(01))) (EVAL(pos(01), neg(01)) -> COND_EVAL1(and(false, false), pos(01), neg(01)),EVAL(pos(01), neg(01)) -> COND_EVAL1(and(false, false), pos(01), neg(01))) (EVAL(pos(01), pos(s(x0))) -> COND_EVAL1(and(false, true), pos(01), pos(s(x0))),EVAL(pos(01), pos(s(x0))) -> COND_EVAL1(and(false, true), pos(01), pos(s(x0)))) (EVAL(pos(01), neg(s(x0))) -> COND_EVAL1(and(false, false), pos(01), neg(s(x0))),EVAL(pos(01), neg(s(x0))) -> COND_EVAL1(and(false, false), pos(01), neg(s(x0)))) ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(01), pos(01)) -> COND_EVAL1(and(false, false), pos(01), pos(01)) EVAL(pos(01), neg(01)) -> COND_EVAL1(and(false, false), pos(01), neg(01)) EVAL(pos(01), pos(s(x0))) -> COND_EVAL1(and(false, true), pos(01), pos(s(x0))) EVAL(pos(01), neg(s(x0))) -> COND_EVAL1(and(false, false), pos(01), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(neg(01), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(01), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(neg(01), pos(01)) -> COND_EVAL1(and(false, false), neg(01), pos(01)),EVAL(neg(01), pos(01)) -> COND_EVAL1(and(false, false), neg(01), pos(01))) (EVAL(neg(01), neg(01)) -> COND_EVAL1(and(false, false), neg(01), neg(01)),EVAL(neg(01), neg(01)) -> COND_EVAL1(and(false, false), neg(01), neg(01))) (EVAL(neg(01), pos(s(x0))) -> COND_EVAL1(and(false, true), neg(01), pos(s(x0))),EVAL(neg(01), pos(s(x0))) -> COND_EVAL1(and(false, true), neg(01), pos(s(x0)))) (EVAL(neg(01), neg(s(x0))) -> COND_EVAL1(and(false, false), neg(01), neg(s(x0))),EVAL(neg(01), neg(s(x0))) -> COND_EVAL1(and(false, false), neg(01), neg(s(x0)))) ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(neg(01), pos(01)) -> COND_EVAL1(and(false, false), neg(01), pos(01)) EVAL(neg(01), neg(01)) -> COND_EVAL1(and(false, false), neg(01), neg(01)) EVAL(neg(01), pos(s(x0))) -> COND_EVAL1(and(false, true), neg(01), pos(s(x0))) EVAL(neg(01), neg(s(x0))) -> COND_EVAL1(and(false, false), neg(01), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(pos(s(x0)), y1) -> COND_EVAL1(and(true, greater_int(y1, pos(01))), pos(s(x0)), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(s(y0)), pos(01)) -> COND_EVAL1(and(true, false), pos(s(y0)), pos(01)),EVAL(pos(s(y0)), pos(01)) -> COND_EVAL1(and(true, false), pos(s(y0)), pos(01))) (EVAL(pos(s(y0)), neg(01)) -> COND_EVAL1(and(true, false), pos(s(y0)), neg(01)),EVAL(pos(s(y0)), neg(01)) -> COND_EVAL1(and(true, false), pos(s(y0)), neg(01))) (EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(and(true, true), pos(s(y0)), pos(s(x0))),EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(and(true, true), pos(s(y0)), pos(s(x0)))) (EVAL(pos(s(y0)), neg(s(x0))) -> COND_EVAL1(and(true, false), pos(s(y0)), neg(s(x0))),EVAL(pos(s(y0)), neg(s(x0))) -> COND_EVAL1(and(true, false), pos(s(y0)), neg(s(x0)))) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(01)) -> COND_EVAL1(and(true, false), pos(s(y0)), pos(01)) EVAL(pos(s(y0)), neg(01)) -> COND_EVAL1(and(true, false), pos(s(y0)), neg(01)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(and(true, true), pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), neg(s(x0))) -> COND_EVAL1(and(true, false), pos(s(y0)), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(and(true, true), pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (63) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(and(true, true), pos(s(y0)), pos(s(x0))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))),EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0)))) ---------------------------------------- (64) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (65) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(neg(s(x0)), y1) -> COND_EVAL1(and(false, greater_int(y1, pos(01))), neg(s(x0)), y1) at position [0] we obtained the following new rules [LPAR04]: (EVAL(neg(s(y0)), pos(01)) -> COND_EVAL1(and(false, false), neg(s(y0)), pos(01)),EVAL(neg(s(y0)), pos(01)) -> COND_EVAL1(and(false, false), neg(s(y0)), pos(01))) (EVAL(neg(s(y0)), neg(01)) -> COND_EVAL1(and(false, false), neg(s(y0)), neg(01)),EVAL(neg(s(y0)), neg(01)) -> COND_EVAL1(and(false, false), neg(s(y0)), neg(01))) (EVAL(neg(s(y0)), pos(s(x0))) -> COND_EVAL1(and(false, true), neg(s(y0)), pos(s(x0))),EVAL(neg(s(y0)), pos(s(x0))) -> COND_EVAL1(and(false, true), neg(s(y0)), pos(s(x0)))) (EVAL(neg(s(y0)), neg(s(x0))) -> COND_EVAL1(and(false, false), neg(s(y0)), neg(s(x0))),EVAL(neg(s(y0)), neg(s(x0))) -> COND_EVAL1(and(false, false), neg(s(y0)), neg(s(x0)))) ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(neg(s(y0)), pos(01)) -> COND_EVAL1(and(false, false), neg(s(y0)), pos(01)) EVAL(neg(s(y0)), neg(01)) -> COND_EVAL1(and(false, false), neg(s(y0)), neg(01)) EVAL(neg(s(y0)), pos(s(x0))) -> COND_EVAL1(and(false, true), neg(s(y0)), pos(s(x0))) EVAL(neg(s(y0)), neg(s(x0))) -> COND_EVAL1(and(false, false), neg(s(y0)), neg(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (68) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (69) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, pos(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, pos(01)) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), pos(01)) -> COND_EVAL1(and(false, false), pos(01), pos(01)),EVAL(pos(01), pos(01)) -> COND_EVAL1(and(false, false), pos(01), pos(01))) (EVAL(neg(01), pos(01)) -> COND_EVAL1(and(false, false), neg(01), pos(01)),EVAL(neg(01), pos(01)) -> COND_EVAL1(and(false, false), neg(01), pos(01))) (EVAL(pos(s(x0)), pos(01)) -> COND_EVAL1(and(true, false), pos(s(x0)), pos(01)),EVAL(pos(s(x0)), pos(01)) -> COND_EVAL1(and(true, false), pos(s(x0)), pos(01))) (EVAL(neg(s(x0)), pos(01)) -> COND_EVAL1(and(false, false), neg(s(x0)), pos(01)),EVAL(neg(s(x0)), pos(01)) -> COND_EVAL1(and(false, false), neg(s(x0)), pos(01))) ---------------------------------------- (70) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), pos(01)) -> COND_EVAL1(and(false, false), pos(01), pos(01)) EVAL(neg(01), pos(01)) -> COND_EVAL1(and(false, false), neg(01), pos(01)) EVAL(pos(s(x0)), pos(01)) -> COND_EVAL1(and(true, false), pos(s(x0)), pos(01)) EVAL(neg(s(x0)), pos(01)) -> COND_EVAL1(and(false, false), neg(s(x0)), pos(01)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (71) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (72) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (73) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, neg(01)) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(01)) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), neg(01)) -> COND_EVAL1(and(false, false), pos(01), neg(01)),EVAL(pos(01), neg(01)) -> COND_EVAL1(and(false, false), pos(01), neg(01))) (EVAL(neg(01), neg(01)) -> COND_EVAL1(and(false, false), neg(01), neg(01)),EVAL(neg(01), neg(01)) -> COND_EVAL1(and(false, false), neg(01), neg(01))) (EVAL(pos(s(x0)), neg(01)) -> COND_EVAL1(and(true, false), pos(s(x0)), neg(01)),EVAL(pos(s(x0)), neg(01)) -> COND_EVAL1(and(true, false), pos(s(x0)), neg(01))) (EVAL(neg(s(x0)), neg(01)) -> COND_EVAL1(and(false, false), neg(s(x0)), neg(01)),EVAL(neg(s(x0)), neg(01)) -> COND_EVAL1(and(false, false), neg(s(x0)), neg(01))) ---------------------------------------- (74) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), neg(01)) -> COND_EVAL1(and(false, false), pos(01), neg(01)) EVAL(neg(01), neg(01)) -> COND_EVAL1(and(false, false), neg(01), neg(01)) EVAL(pos(s(x0)), neg(01)) -> COND_EVAL1(and(true, false), pos(s(x0)), neg(01)) EVAL(neg(s(x0)), neg(01)) -> COND_EVAL1(and(false, false), neg(s(x0)), neg(01)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (75) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (76) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (77) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, pos(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), true), y0, pos(s(x0))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), pos(s(y1))) -> COND_EVAL1(and(false, true), pos(01), pos(s(y1))),EVAL(pos(01), pos(s(y1))) -> COND_EVAL1(and(false, true), pos(01), pos(s(y1)))) (EVAL(neg(01), pos(s(y1))) -> COND_EVAL1(and(false, true), neg(01), pos(s(y1))),EVAL(neg(01), pos(s(y1))) -> COND_EVAL1(and(false, true), neg(01), pos(s(y1)))) (EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(and(true, true), pos(s(x0)), pos(s(y1))),EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(and(true, true), pos(s(x0)), pos(s(y1)))) (EVAL(neg(s(x0)), pos(s(y1))) -> COND_EVAL1(and(false, true), neg(s(x0)), pos(s(y1))),EVAL(neg(s(x0)), pos(s(y1))) -> COND_EVAL1(and(false, true), neg(s(x0)), pos(s(y1)))) ---------------------------------------- (78) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), pos(s(y1))) -> COND_EVAL1(and(false, true), pos(01), pos(s(y1))) EVAL(neg(01), pos(s(y1))) -> COND_EVAL1(and(false, true), neg(01), pos(s(y1))) EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(and(true, true), pos(s(x0)), pos(s(y1))) EVAL(neg(s(x0)), pos(s(y1))) -> COND_EVAL1(and(false, true), neg(s(x0)), pos(s(y1))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (79) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (80) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(and(true, true), pos(s(x0)), pos(s(y1))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(false, true) -> false and(true, false) -> false and(true, true) -> true The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (81) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (82) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(and(true, true), pos(s(x0)), pos(s(y1))) The TRS R consists of the following rules: and(true, true) -> true minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(true, false) -> false The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (83) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(and(true, true), pos(s(x0)), pos(s(y1))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(s(x0)), pos(s(y1))) -> COND_EVAL1(true, pos(s(x0)), pos(s(y1))),EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0)))) ---------------------------------------- (84) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: and(true, true) -> true minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(true, false) -> false The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (85) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (86) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(true, false) -> false The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (87) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule EVAL(y0, neg(s(x0))) -> COND_EVAL1(and(greater_int(y0, pos(01)), false), y0, neg(s(x0))) at position [0] we obtained the following new rules [LPAR04]: (EVAL(pos(01), neg(s(y1))) -> COND_EVAL1(and(false, false), pos(01), neg(s(y1))),EVAL(pos(01), neg(s(y1))) -> COND_EVAL1(and(false, false), pos(01), neg(s(y1)))) (EVAL(neg(01), neg(s(y1))) -> COND_EVAL1(and(false, false), neg(01), neg(s(y1))),EVAL(neg(01), neg(s(y1))) -> COND_EVAL1(and(false, false), neg(01), neg(s(y1)))) (EVAL(pos(s(x0)), neg(s(y1))) -> COND_EVAL1(and(true, false), pos(s(x0)), neg(s(y1))),EVAL(pos(s(x0)), neg(s(y1))) -> COND_EVAL1(and(true, false), pos(s(x0)), neg(s(y1)))) (EVAL(neg(s(x0)), neg(s(y1))) -> COND_EVAL1(and(false, false), neg(s(x0)), neg(s(y1))),EVAL(neg(s(x0)), neg(s(y1))) -> COND_EVAL1(and(false, false), neg(s(x0)), neg(s(y1)))) ---------------------------------------- (88) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) EVAL(pos(01), neg(s(y1))) -> COND_EVAL1(and(false, false), pos(01), neg(s(y1))) EVAL(neg(01), neg(s(y1))) -> COND_EVAL1(and(false, false), neg(01), neg(s(y1))) EVAL(pos(s(x0)), neg(s(y1))) -> COND_EVAL1(and(true, false), pos(s(x0)), neg(s(y1))) EVAL(neg(s(x0)), neg(s(y1))) -> COND_EVAL1(and(false, false), neg(s(x0)), neg(s(y1))) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(true, false) -> false The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (89) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (90) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) greater_int(pos(01), pos(01)) -> false greater_int(neg(01), pos(01)) -> false greater_int(pos(s(x)), pos(01)) -> true greater_int(neg(s(x)), pos(01)) -> false and(false, false) -> false and(true, false) -> false The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (91) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (92) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) The set Q consists of the following terms: and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (93) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. and(false, false) and(false, true) and(true, false) and(true, true) greater_int(pos(01), pos(01)) greater_int(pos(01), neg(01)) greater_int(neg(01), pos(01)) greater_int(neg(01), neg(01)) greater_int(pos(01), pos(s(x0))) greater_int(neg(01), pos(s(x0))) greater_int(pos(01), neg(s(x0))) greater_int(neg(01), neg(s(x0))) greater_int(pos(s(x0)), pos(01)) greater_int(neg(s(x0)), pos(01)) greater_int(pos(s(x0)), neg(01)) greater_int(neg(s(x0)), neg(01)) greater_int(pos(s(x0)), neg(s(x1))) greater_int(neg(s(x0)), pos(s(x1))) greater_int(pos(s(x0)), pos(s(x1))) greater_int(neg(s(x0)), neg(s(x1))) ---------------------------------------- (94) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) The set Q consists of the following terms: minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (95) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND_EVAL(true, x[1], y[1]) -> EVAL(minus_int(x[1], pos(s(01))), x[1]) at position [0] we obtained the following new rules [LPAR04]: (COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)),COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0))) (COND_EVAL(true, neg(x0), y1) -> EVAL(neg(plus_nat(x0, s(01))), neg(x0)),COND_EVAL(true, neg(x0), y1) -> EVAL(neg(plus_nat(x0, s(01))), neg(x0))) ---------------------------------------- (96) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) COND_EVAL(true, neg(x0), y1) -> EVAL(neg(plus_nat(x0, s(01))), neg(x0)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) The set Q consists of the following terms: minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (97) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (98) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) The set Q consists of the following terms: minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (99) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND_EVAL1(true, x[3], y[3]) -> EVAL(minus_int(y[3], pos(s(s(01)))), plus_int(pos(s(01)), x[3])) at position [0] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0)),COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0))) (COND_EVAL1(true, y0, neg(x0)) -> EVAL(neg(plus_nat(x0, s(s(01)))), plus_int(pos(s(01)), y0)),COND_EVAL1(true, y0, neg(x0)) -> EVAL(neg(plus_nat(x0, s(s(01)))), plus_int(pos(s(01)), y0))) ---------------------------------------- (100) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0)) COND_EVAL1(true, y0, neg(x0)) -> EVAL(neg(plus_nat(x0, s(s(01)))), plus_int(pos(s(01)), y0)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) The set Q consists of the following terms: minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (101) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (102) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0)) The TRS R consists of the following rules: minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) The set Q consists of the following terms: minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (103) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (104) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0)) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (105) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) ---------------------------------------- (106) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0)) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (107) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND_EVAL1(true, y0, pos(x0)) -> EVAL(minus_nat(x0, s(s(01))), plus_int(pos(s(01)), y0)) at position [1] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, neg(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), minus_nat(s(01), x1)),COND_EVAL1(true, neg(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), minus_nat(s(01), x1))) (COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1))),COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1)))) ---------------------------------------- (108) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, neg(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), minus_nat(s(01), x1)) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (109) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (110) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) plus_nat(01, x) -> x plus_nat(s(x), y) -> s(plus_nat(x, y)) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (111) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (112) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_nat(s(x), y) -> s(plus_nat(x, y)) plus_nat(01, x) -> x minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (113) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) ---------------------------------------- (114) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_nat(s(x), y) -> s(plus_nat(x, y)) plus_nat(01, x) -> x minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (115) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(plus_nat(s(01), x1))) at position [1,0] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(plus_nat(01, x1)))),COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(plus_nat(01, x1))))) ---------------------------------------- (116) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(plus_nat(01, x1)))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_nat(s(x), y) -> s(plus_nat(x, y)) plus_nat(01, x) -> x minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (117) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (118) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(plus_nat(01, x1)))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_nat(01, x) -> x minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (119) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(plus_nat(01, x1)))) at position [1,0,0] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))),COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1)))) ---------------------------------------- (120) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) plus_nat(01, x) -> x minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (121) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (122) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: plus_nat(01, x0) plus_nat(s(x0), x1) minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (123) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. plus_nat(01, x0) plus_nat(s(x0), x1) ---------------------------------------- (124) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (125) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND_EVAL(true, pos(x0), y1) -> EVAL(minus_nat(x0, s(01)), pos(x0)) we obtained the following new rules [LPAR04]: (COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z0), s(01)), pos(s(z0))),COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z0), s(01)), pos(s(z0)))) ---------------------------------------- (126) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))) COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z0), s(01)), pos(s(z0))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (127) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z0), s(01)), pos(s(z0))) at position [0] we obtained the following new rules [LPAR04]: (COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0))),COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0)))) ---------------------------------------- (128) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))) COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (129) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND_EVAL1(true, pos(x1), pos(y1)) -> EVAL(minus_nat(y1, s(s(01))), pos(s(x1))) we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z1), s(s(01))), pos(s(s(z0)))),COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z1), s(s(01))), pos(s(s(z0))))) ---------------------------------------- (130) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0))) COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z1), s(s(01))), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (131) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(s(z1), s(s(01))), pos(s(s(z0)))) at position [0] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))),COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0))))) ---------------------------------------- (132) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0))) COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (133) MRRProof (EQUIVALENT) 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. Strictly oriented rules of the TRS R: minus_nat(01, s(y)) -> neg(s(y)) Used ordering: Polynomial interpretation [POLO]: POL(01) = 0 POL(COND_EVAL(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(COND_EVAL1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(EVAL(x_1, x_2)) = 2*x_1 + x_2 POL(minus_nat(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(neg(x_1)) = x_1 POL(pos(x_1)) = 1 + 2*x_1 POL(s(x_1)) = 2*x_1 POL(true) = 0 ---------------------------------------- (134) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0))) COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (135) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. COND_EVAL(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z0, 01), pos(s(z0))) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( EVAL_2(x_1, x_2) ) = 2x_1 + x_2 POL( minus_nat_2(x_1, x_2) ) = x_1 POL( 01 ) = 0 POL( pos_1(x_1) ) = x_1 POL( s_1(x_1) ) = 2x_1 + 2 POL( COND_EVAL_3(x_1, ..., x_3) ) = 2x_1 + 2x_2 POL( true ) = 1 POL( COND_EVAL1_3(x_1, ..., x_3) ) = max{0, 2x_1 + 2x_2 + x_3 - 2} The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) ---------------------------------------- (136) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL(true, pos(s(y0)), pos(s(x0))) EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (137) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (138) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (139) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule EVAL(pos(s(y0)), pos(s(x0))) -> COND_EVAL1(true, pos(s(y0)), pos(s(x0))) we obtained the following new rules [LPAR04]: (EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))),EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0))))) ---------------------------------------- (140) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))) EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (141) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND_EVAL1(true, pos(s(z0)), pos(s(z1))) -> EVAL(minus_nat(z1, s(01)), pos(s(s(z0)))) we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(s(z1), s(01)), pos(s(s(z0)))),COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(s(z1), s(01)), pos(s(s(z0))))) ---------------------------------------- (142) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(s(z1), s(01)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (143) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(s(z1), s(01)), pos(s(s(z0)))) at position [0] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(z1, 01), pos(s(s(z0)))),COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(z1, 01), pos(s(s(z0))))) ---------------------------------------- (144) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(z1, 01), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(s(x), s(y)) -> minus_nat(x, y) minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (145) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (146) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(z1, 01), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (147) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND_EVAL1(true, pos(s(z0)), pos(s(s(z1)))) -> EVAL(minus_nat(z1, 01), pos(s(s(z0)))) at position [0] we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(s(y0)), pos(s(s(01)))) -> EVAL(pos(01), pos(s(s(y0)))),COND_EVAL1(true, pos(s(y0)), pos(s(s(01)))) -> EVAL(pos(01), pos(s(s(y0))))) (COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))),COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0))))) ---------------------------------------- (148) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) COND_EVAL1(true, pos(s(y0)), pos(s(s(01)))) -> EVAL(pos(01), pos(s(s(y0)))) COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))) The TRS R consists of the following rules: minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (149) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (150) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))) EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) The TRS R consists of the following rules: minus_nat(01, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (151) UsableRulesProof (EQUIVALENT) 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. ---------------------------------------- (152) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))) EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) R is empty. The set Q consists of the following terms: minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (153) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. minus_nat(01, 01) minus_nat(01, s(x0)) minus_nat(s(x0), 01) minus_nat(s(x0), s(x1)) ---------------------------------------- (154) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))) EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (155) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule EVAL(pos(s(x0)), pos(s(s(z0)))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(z0)))) we obtained the following new rules [LPAR04]: (EVAL(pos(s(x0)), pos(s(s(s(y_1))))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(s(y_1))))),EVAL(pos(s(x0)), pos(s(s(s(y_1))))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(s(y_1)))))) ---------------------------------------- (156) Obligation: Q DP problem: The TRS P consists of the following rules: COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))) EVAL(pos(s(x0)), pos(s(s(s(y_1))))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(s(y_1))))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (157) TransformationProof (EQUIVALENT) By forward instantiating [JAR06] the rule COND_EVAL1(true, pos(s(y0)), pos(s(s(s(x0))))) -> EVAL(pos(s(x0)), pos(s(s(y0)))) we obtained the following new rules [LPAR04]: (COND_EVAL1(true, pos(s(s(y_1))), pos(s(s(s(x1))))) -> EVAL(pos(s(x1)), pos(s(s(s(y_1))))),COND_EVAL1(true, pos(s(s(y_1))), pos(s(s(s(x1))))) -> EVAL(pos(s(x1)), pos(s(s(s(y_1)))))) ---------------------------------------- (158) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), pos(s(s(s(y_1))))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(s(y_1))))) COND_EVAL1(true, pos(s(s(y_1))), pos(s(s(s(x1))))) -> EVAL(pos(s(x1)), pos(s(s(s(y_1))))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (159) MRRProof (EQUIVALENT) 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. Strictly oriented dependency pairs: COND_EVAL1(true, pos(s(s(y_1))), pos(s(s(s(x1))))) -> EVAL(pos(s(x1)), pos(s(s(s(y_1))))) Used ordering: Polynomial interpretation [POLO]: POL(COND_EVAL1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(EVAL(x_1, x_2)) = 2*x_1 + 2*x_2 POL(pos(x_1)) = 2*x_1 POL(s(x_1)) = 2 + x_1 POL(true) = 0 ---------------------------------------- (160) Obligation: Q DP problem: The TRS P consists of the following rules: EVAL(pos(s(x0)), pos(s(s(s(y_1))))) -> COND_EVAL1(true, pos(s(x0)), pos(s(s(s(y_1))))) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (161) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (162) TRUE