/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 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) IDependencyGraphProof [EQUIVALENT, 0 ms] (6) IDP (7) IDPtoQDPProof [SOUND, 39 ms] (8) QDP (9) UsableRulesProof [EQUIVALENT, 0 ms] (10) QDP (11) QReductionProof [EQUIVALENT, 0 ms] (12) QDP (13) TransformationProof [EQUIVALENT, 0 ms] (14) QDP (15) DependencyGraphProof [EQUIVALENT, 0 ms] (16) QDP (17) UsableRulesProof [EQUIVALENT, 0 ms] (18) QDP (19) TransformationProof [EQUIVALENT, 0 ms] (20) QDP (21) DependencyGraphProof [EQUIVALENT, 0 ms] (22) QDP (23) UsableRulesProof [EQUIVALENT, 0 ms] (24) QDP (25) QReductionProof [EQUIVALENT, 0 ms] (26) QDP (27) TransformationProof [EQUIVALENT, 0 ms] (28) QDP (29) DependencyGraphProof [EQUIVALENT, 0 ms] (30) QDP (31) TransformationProof [EQUIVALENT, 0 ms] (32) QDP (33) DependencyGraphProof [EQUIVALENT, 0 ms] (34) QDP (35) TransformationProof [EQUIVALENT, 0 ms] (36) QDP (37) TransformationProof [EQUIVALENT, 0 ms] (38) QDP (39) TransformationProof [EQUIVALENT, 0 ms] (40) QDP (41) TransformationProof [EQUIVALENT, 0 ms] (42) QDP (43) MRRProof [EQUIVALENT, 14 ms] (44) QDP (45) DependencyGraphProof [EQUIVALENT, 0 ms] (46) AND (47) QDP (48) UsableRulesProof [EQUIVALENT, 0 ms] (49) QDP (50) QReductionProof [EQUIVALENT, 0 ms] (51) QDP (52) MRRProof [EQUIVALENT, 0 ms] (53) QDP (54) DependencyGraphProof [EQUIVALENT, 0 ms] (55) TRUE (56) QDP (57) UsableRulesProof [EQUIVALENT, 0 ms] (58) QDP (59) QReductionProof [EQUIVALENT, 0 ms] (60) QDP (61) MRRProof [EQUIVALENT, 0 ms] (62) QDP (63) MRRProof [EQUIVALENT, 0 ms] (64) QDP (65) PisEmptyProof [EQUIVALENT, 0 ms] (66) YES ---------------------------------------- (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: random(x) -> rand(x, w(0)) rand(x, y) -> Cond_rand(x = 0, x, y) Cond_rand(TRUE, x, y) -> y rand(x, y) -> Cond_rand1(x > 0, x, y) Cond_rand1(TRUE, x, y) -> rand(x - 1, id_inc(y)) rand(x, y) -> Cond_rand2(0 > x, x, y) Cond_rand2(TRUE, x, y) -> rand(x + 1, id_dec(y)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(x + 1) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(x - 1) The set Q consists of the following terms: random(x0) rand(x0, x1) Cond_rand(TRUE, x0, x1) Cond_rand1(TRUE, x0, x1) Cond_rand2(TRUE, x0, x1) id_inc(w(x0)) id_dec(w(x0)) ---------------------------------------- (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: Integer The ITRS R consists of the following rules: random(x) -> rand(x, w(0)) rand(x, y) -> Cond_rand(x = 0, x, y) Cond_rand(TRUE, x, y) -> y rand(x, y) -> Cond_rand1(x > 0, x, y) Cond_rand1(TRUE, x, y) -> rand(x - 1, id_inc(y)) rand(x, y) -> Cond_rand2(0 > x, x, y) Cond_rand2(TRUE, x, y) -> rand(x + 1, id_dec(y)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(x + 1) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(x - 1) The integer pair graph contains the following rules and edges: (0): RANDOM(x[0]) -> RAND(x[0], w(0)) (1): RAND(x[1], y[1]) -> COND_RAND(x[1] = 0, x[1], y[1]) (2): RAND(x[2], y[2]) -> COND_RAND1(x[2] > 0, x[2], y[2]) (3): COND_RAND1(TRUE, x[3], y[3]) -> RAND(x[3] - 1, id_inc(y[3])) (4): COND_RAND1(TRUE, x[4], y[4]) -> ID_INC(y[4]) (5): RAND(x[5], y[5]) -> COND_RAND2(0 > x[5], x[5], y[5]) (6): COND_RAND2(TRUE, x[6], y[6]) -> RAND(x[6] + 1, id_dec(y[6])) (7): COND_RAND2(TRUE, x[7], y[7]) -> ID_DEC(y[7]) (0) -> (1), if (x[0] ->^* x[1] & w(0) ->^* y[1]) (0) -> (2), if (x[0] ->^* x[2] & w(0) ->^* y[2]) (0) -> (5), if (x[0] ->^* x[5] & w(0) ->^* y[5]) (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4] & y[2] ->^* y[4]) (3) -> (1), if (x[3] - 1 ->^* x[1] & id_inc(y[3]) ->^* y[1]) (3) -> (2), if (x[3] - 1 ->^* x[2] & id_inc(y[3]) ->^* y[2]) (3) -> (5), if (x[3] - 1 ->^* x[5] & id_inc(y[3]) ->^* y[5]) (5) -> (6), if (0 > x[5] & x[5] ->^* x[6] & y[5] ->^* y[6]) (5) -> (7), if (0 > x[5] & x[5] ->^* x[7] & y[5] ->^* y[7]) (6) -> (1), if (x[6] + 1 ->^* x[1] & id_dec(y[6]) ->^* y[1]) (6) -> (2), if (x[6] + 1 ->^* x[2] & id_dec(y[6]) ->^* y[2]) (6) -> (5), if (x[6] + 1 ->^* x[5] & id_dec(y[6]) ->^* y[5]) The set Q consists of the following terms: random(x0) rand(x0, x1) Cond_rand(TRUE, x0, x1) Cond_rand1(TRUE, x0, x1) Cond_rand2(TRUE, x0, x1) id_inc(w(x0)) id_dec(w(x0)) ---------------------------------------- (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: Integer The ITRS R consists of the following rules: id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(x + 1) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(x - 1) The integer pair graph contains the following rules and edges: (0): RANDOM(x[0]) -> RAND(x[0], w(0)) (1): RAND(x[1], y[1]) -> COND_RAND(x[1] = 0, x[1], y[1]) (2): RAND(x[2], y[2]) -> COND_RAND1(x[2] > 0, x[2], y[2]) (3): COND_RAND1(TRUE, x[3], y[3]) -> RAND(x[3] - 1, id_inc(y[3])) (4): COND_RAND1(TRUE, x[4], y[4]) -> ID_INC(y[4]) (5): RAND(x[5], y[5]) -> COND_RAND2(0 > x[5], x[5], y[5]) (6): COND_RAND2(TRUE, x[6], y[6]) -> RAND(x[6] + 1, id_dec(y[6])) (7): COND_RAND2(TRUE, x[7], y[7]) -> ID_DEC(y[7]) (0) -> (1), if (x[0] ->^* x[1] & w(0) ->^* y[1]) (0) -> (2), if (x[0] ->^* x[2] & w(0) ->^* y[2]) (0) -> (5), if (x[0] ->^* x[5] & w(0) ->^* y[5]) (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4] & y[2] ->^* y[4]) (3) -> (1), if (x[3] - 1 ->^* x[1] & id_inc(y[3]) ->^* y[1]) (3) -> (2), if (x[3] - 1 ->^* x[2] & id_inc(y[3]) ->^* y[2]) (3) -> (5), if (x[3] - 1 ->^* x[5] & id_inc(y[3]) ->^* y[5]) (5) -> (6), if (0 > x[5] & x[5] ->^* x[6] & y[5] ->^* y[6]) (5) -> (7), if (0 > x[5] & x[5] ->^* x[7] & y[5] ->^* y[7]) (6) -> (1), if (x[6] + 1 ->^* x[1] & id_dec(y[6]) ->^* y[1]) (6) -> (2), if (x[6] + 1 ->^* x[2] & id_dec(y[6]) ->^* y[2]) (6) -> (5), if (x[6] + 1 ->^* x[5] & id_dec(y[6]) ->^* y[5]) The set Q consists of the following terms: random(x0) rand(x0, x1) Cond_rand(TRUE, x0, x1) Cond_rand1(TRUE, x0, x1) Cond_rand2(TRUE, x0, x1) id_inc(w(x0)) id_dec(w(x0)) ---------------------------------------- (5) IDependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. ---------------------------------------- (6) 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: Integer The ITRS R consists of the following rules: id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(x + 1) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(x - 1) The integer pair graph contains the following rules and edges: (6): COND_RAND2(TRUE, x[6], y[6]) -> RAND(x[6] + 1, id_dec(y[6])) (5): RAND(x[5], y[5]) -> COND_RAND2(0 > x[5], x[5], y[5]) (3): COND_RAND1(TRUE, x[3], y[3]) -> RAND(x[3] - 1, id_inc(y[3])) (2): RAND(x[2], y[2]) -> COND_RAND1(x[2] > 0, x[2], y[2]) (3) -> (2), if (x[3] - 1 ->^* x[2] & id_inc(y[3]) ->^* y[2]) (6) -> (2), if (x[6] + 1 ->^* x[2] & id_dec(y[6]) ->^* y[2]) (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) (3) -> (5), if (x[3] - 1 ->^* x[5] & id_inc(y[3]) ->^* y[5]) (6) -> (5), if (x[6] + 1 ->^* x[5] & id_dec(y[6]) ->^* y[5]) (5) -> (6), if (0 > x[5] & x[5] ->^* x[6] & y[5] ->^* y[6]) The set Q consists of the following terms: random(x0) rand(x0, x1) Cond_rand(TRUE, x0, x1) Cond_rand1(TRUE, x0, x1) Cond_rand2(TRUE, x0, x1) id_inc(w(x0)) id_dec(w(x0)) ---------------------------------------- (7) IDPtoQDPProof (SOUND) Represented integers and predefined function symbols by Terms ---------------------------------------- (8) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) The TRS R consists of the following rules: id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) 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)) 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) 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)) 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)) The set Q consists of the following terms: random(x0) rand(x0, x1) Cond_rand(true, x0, x1) Cond_rand1(true, x0, x1) Cond_rand2(true, x0, x1) id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (9) 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. ---------------------------------------- (10) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) The TRS R consists of the following rules: 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 minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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), neg(01)) -> false greater_int(pos(01), pos(s(y))) -> false greater_int(pos(01), neg(s(y))) -> true id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: random(x0) rand(x0, x1) Cond_rand(true, x0, x1) Cond_rand1(true, x0, x1) Cond_rand2(true, x0, x1) id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (11) 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]. random(x0) rand(x0, x1) Cond_rand(true, x0, x1) Cond_rand1(true, x0, x1) Cond_rand2(true, x0, x1) ---------------------------------------- (12) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) The TRS R consists of the following rules: 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 minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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), neg(01)) -> false greater_int(pos(01), pos(s(y))) -> false greater_int(pos(01), neg(s(y))) -> true id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (13) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) at position [0] we obtained the following new rules [LPAR04]: (RAND(pos(01), y1) -> COND_RAND2(false, pos(01), y1),RAND(pos(01), y1) -> COND_RAND2(false, pos(01), y1)) (RAND(neg(01), y1) -> COND_RAND2(false, neg(01), y1),RAND(neg(01), y1) -> COND_RAND2(false, neg(01), y1)) (RAND(pos(s(x0)), y1) -> COND_RAND2(false, pos(s(x0)), y1),RAND(pos(s(x0)), y1) -> COND_RAND2(false, pos(s(x0)), y1)) (RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1),RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1)) ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) RAND(pos(01), y1) -> COND_RAND2(false, pos(01), y1) RAND(neg(01), y1) -> COND_RAND2(false, neg(01), y1) RAND(pos(s(x0)), y1) -> COND_RAND2(false, pos(s(x0)), y1) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) The TRS R consists of the following rules: 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 minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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), neg(01)) -> false greater_int(pos(01), pos(s(y))) -> false greater_int(pos(01), neg(s(y))) -> true id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) The TRS R consists of the following rules: 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 minus_int(pos(x), pos(y)) -> minus_nat(x, y) minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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), neg(01)) -> false greater_int(pos(01), pos(s(y))) -> false greater_int(pos(01), neg(s(y))) -> true id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) 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. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) The TRS R consists of the following rules: plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) 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) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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 The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) at position [0] we obtained the following new rules [LPAR04]: (RAND(pos(01), y1) -> COND_RAND1(false, pos(01), y1),RAND(pos(01), y1) -> COND_RAND1(false, pos(01), y1)) (RAND(neg(01), y1) -> COND_RAND1(false, neg(01), y1),RAND(neg(01), y1) -> COND_RAND1(false, neg(01), y1)) (RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1),RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1)) (RAND(neg(s(x0)), y1) -> COND_RAND1(false, neg(s(x0)), y1),RAND(neg(s(x0)), y1) -> COND_RAND1(false, neg(s(x0)), y1)) ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(pos(01), y1) -> COND_RAND1(false, pos(01), y1) RAND(neg(01), y1) -> COND_RAND1(false, neg(01), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) RAND(neg(s(x0)), y1) -> COND_RAND1(false, neg(s(x0)), y1) The TRS R consists of the following rules: plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) 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) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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 The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) 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 3 less nodes. ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) The TRS R consists of the following rules: plus_int(pos(x), neg(y)) -> minus_nat(x, y) plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) 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) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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 The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) 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. ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) 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))) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) 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]. 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))) ---------------------------------------- (26) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (27) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND_RAND2(true, x[6], y[6]) -> RAND(plus_int(pos(s(01)), x[6]), id_dec(y[6])) at position [0] we obtained the following new rules [LPAR04]: (COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1)),COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1))) (COND_RAND2(true, pos(x1), y1) -> RAND(pos(plus_nat(s(01), x1)), id_dec(y1)),COND_RAND2(true, pos(x1), y1) -> RAND(pos(plus_nat(s(01), x1)), id_dec(y1))) ---------------------------------------- (28) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1)) COND_RAND2(true, pos(x1), y1) -> RAND(pos(plus_nat(s(01), x1)), id_dec(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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (29) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (30) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (31) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule COND_RAND1(true, x[3], y[3]) -> RAND(minus_int(x[3], pos(s(01))), id_inc(y[3])) at position [0] we obtained the following new rules [LPAR04]: (COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(y1)),COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(y1))) (COND_RAND1(true, neg(x0), y1) -> RAND(neg(plus_nat(x0, s(01))), id_inc(y1)),COND_RAND1(true, neg(x0), y1) -> RAND(neg(plus_nat(x0, s(01))), id_inc(y1))) ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(y1)) COND_RAND1(true, neg(x0), y1) -> RAND(neg(plus_nat(x0, s(01))), id_inc(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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (33) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1)) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (35) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND_RAND2(true, neg(x1), y1) -> RAND(minus_nat(s(01), x1), id_dec(y1)) we obtained the following new rules [LPAR04]: (COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), id_dec(z1)),COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), id_dec(z1))) ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(y1)) COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), id_dec(z1)) 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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), id_dec(z1)) at position [0] we obtained the following new rules [LPAR04]: (COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)),COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1))) ---------------------------------------- (38) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(y1)) COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) 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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (39) TransformationProof (EQUIVALENT) By instantiating [LPAR04] the rule COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(x0, s(01)), id_inc(y1)) we obtained the following new rules [LPAR04]: (COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), id_inc(z1)),COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), id_inc(z1))) ---------------------------------------- (40) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), id_inc(z1)) 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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (41) TransformationProof (EQUIVALENT) By rewriting [LPAR04] the rule COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), id_inc(z1)) at position [0] we obtained the following new rules [LPAR04]: (COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)),COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1))) ---------------------------------------- (42) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)) 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)) id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) 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) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (43) 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: id_inc(w(x)) -> w(x) id_inc(w(x)) -> w(plus_int(pos(s(01)), x)) minus_nat(s(x), s(y)) -> minus_nat(x, y) id_dec(w(x)) -> w(x) id_dec(w(x)) -> w(minus_int(x, pos(s(01)))) Used ordering: Polynomial interpretation [POLO]: POL(01) = 0 POL(COND_RAND1(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(COND_RAND2(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 POL(RAND(x_1, x_2)) = 2*x_1 + x_2 POL(id_dec(x_1)) = 2 + x_1 POL(id_inc(x_1)) = 2 + x_1 POL(minus_int(x_1, x_2)) = x_1 + x_2 POL(minus_nat(x_1, x_2)) = x_1 + x_2 POL(neg(x_1)) = x_1 POL(plus_int(x_1, x_2)) = x_1 + x_2 POL(plus_nat(x_1, x_2)) = x_1 + x_2 POL(pos(x_1)) = x_1 POL(s(x_1)) = 1 + x_1 POL(true) = 0 POL(w(x_1)) = x_1 ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)) 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)) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. ---------------------------------------- (46) Complex Obligation (AND) ---------------------------------------- (47) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), 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)) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (48) 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. ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 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: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) 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]. id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) plus_nat(01, x0) plus_nat(s(x0), 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)) ---------------------------------------- (51) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 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: id_inc(w(x0)) 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. ---------------------------------------- (52) 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, 01) -> pos(01) minus_nat(s(x), 01) -> pos(s(x)) Used ordering: Polynomial interpretation [POLO]: POL(01) = 0 POL(COND_RAND1(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 POL(RAND(x_1, x_2)) = x_1 + 2*x_2 POL(id_inc(x_1)) = x_1 POL(minus_nat(x_1, x_2)) = 1 + x_1 + x_2 POL(pos(x_1)) = x_1 POL(s(x_1)) = 1 + 2*x_1 POL(true) = 0 ---------------------------------------- (53) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(z0, 01), id_inc(z1)) RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) R is empty. The set Q consists of the following terms: id_inc(w(x0)) 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. ---------------------------------------- (54) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. ---------------------------------------- (55) TRUE ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), 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)) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) 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. ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) The TRS R consists of the following rules: minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) The set Q consists of the following terms: id_inc(w(x0)) id_dec(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(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)) minus_int(pos(x0), pos(x1)) minus_int(neg(x0), neg(x1)) minus_int(neg(x0), pos(x1)) minus_int(pos(x0), neg(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) 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]. id_inc(w(x0)) plus_int(pos(x0), neg(x1)) plus_int(neg(x0), pos(x1)) plus_int(neg(x0), neg(x1)) plus_int(pos(x0), pos(x1)) plus_nat(01, x0) plus_nat(s(x0), 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)) ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) The TRS R consists of the following rules: minus_nat(01, 01) -> pos(01) minus_nat(01, s(y)) -> neg(s(y)) The set Q consists of the following terms: id_dec(w(x0)) 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. ---------------------------------------- (61) 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, 01) -> pos(01) Used ordering: Polynomial interpretation [POLO]: POL(01) = 0 POL(COND_RAND2(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 POL(RAND(x_1, x_2)) = 2*x_1 + 2*x_2 POL(id_dec(x_1)) = x_1 POL(minus_nat(x_1, x_2)) = 1 + 2*x_1 + x_2 POL(neg(x_1)) = 1 + x_1 POL(pos(x_1)) = x_1 POL(s(x_1)) = 2*x_1 POL(true) = 0 ---------------------------------------- (62) Obligation: Q DP problem: The TRS P consists of the following rules: COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) The TRS R consists of the following rules: minus_nat(01, s(y)) -> neg(s(y)) The set Q consists of the following terms: id_dec(w(x0)) 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. ---------------------------------------- (63) 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_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(01, z0), id_dec(z1)) RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) Strictly oriented rules of the TRS R: minus_nat(01, s(y)) -> neg(s(y)) Used ordering: Knuth-Bendix order [KBO] with precedence:id_dec_1 > RAND_2 > true > COND_RAND2_3 > minus_nat_2 > neg_1 > s_1 > 01 and weight map: 01=1 true=5 s_1=2 neg_1=1 id_dec_1=1 minus_nat_2=0 COND_RAND2_3=0 RAND_2=5 The variable weight is 1 ---------------------------------------- (64) Obligation: Q DP problem: P is empty. R is empty. The set Q consists of the following terms: id_dec(w(x0)) 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. ---------------------------------------- (65) PisEmptyProof (EQUIVALENT) The TRS P is empty. Hence, there is no (P,Q,R) chain. ---------------------------------------- (66) YES