50.29/18.21 YES 50.29/18.22 proof of /export/starexec/sandbox2/benchmark/theBenchmark.itrs 50.29/18.22 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 50.29/18.22 50.29/18.22 50.29/18.22 Termination of the given ITRS could be proven: 50.29/18.22 50.29/18.22 (0) ITRS 50.29/18.22 (1) ITRStoIDPProof [EQUIVALENT, 0 ms] 50.29/18.22 (2) IDP 50.29/18.22 (3) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (4) IDP 50.29/18.22 (5) IDependencyGraphProof [EQUIVALENT, 0 ms] 50.29/18.22 (6) IDP 50.29/18.22 (7) IDPtoQDPProof [SOUND, 21 ms] 50.29/18.22 (8) QDP 50.29/18.22 (9) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (10) QDP 50.29/18.22 (11) QReductionProof [EQUIVALENT, 2 ms] 50.29/18.22 (12) QDP 50.29/18.22 (13) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (14) QDP 50.29/18.22 (15) DependencyGraphProof [EQUIVALENT, 0 ms] 50.29/18.22 (16) QDP 50.29/18.22 (17) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (18) QDP 50.29/18.22 (19) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (20) QDP 50.29/18.22 (21) DependencyGraphProof [EQUIVALENT, 0 ms] 50.29/18.22 (22) QDP 50.29/18.22 (23) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (24) QDP 50.29/18.22 (25) QReductionProof [EQUIVALENT, 0 ms] 50.29/18.22 (26) QDP 50.29/18.22 (27) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (28) QDP 50.29/18.22 (29) DependencyGraphProof [EQUIVALENT, 0 ms] 50.29/18.22 (30) QDP 50.29/18.22 (31) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (32) QDP 50.29/18.22 (33) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (34) QDP 50.29/18.22 (35) DependencyGraphProof [EQUIVALENT, 0 ms] 50.29/18.22 (36) QDP 50.29/18.22 (37) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (38) QDP 50.29/18.22 (39) QReductionProof [EQUIVALENT, 0 ms] 50.29/18.22 (40) QDP 50.29/18.22 (41) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (42) QDP 50.29/18.22 (43) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (44) QDP 50.29/18.22 (45) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (46) QDP 50.29/18.22 (47) QReductionProof [EQUIVALENT, 0 ms] 50.29/18.22 (48) QDP 50.29/18.22 (49) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (50) QDP 50.29/18.22 (51) UsableRulesProof [EQUIVALENT, 0 ms] 50.29/18.22 (52) QDP 50.29/18.22 (53) QReductionProof [EQUIVALENT, 0 ms] 50.29/18.22 (54) QDP 50.29/18.22 (55) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (56) QDP 50.29/18.22 (57) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (58) QDP 50.29/18.22 (59) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (60) QDP 50.29/18.22 (61) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (62) QDP 50.29/18.22 (63) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (64) QDP 50.29/18.22 (65) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (66) QDP 50.29/18.22 (67) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (68) QDP 50.29/18.22 (69) TransformationProof [EQUIVALENT, 0 ms] 50.29/18.22 (70) QDP 50.29/18.22 (71) MRRProof [EQUIVALENT, 23 ms] 50.29/18.22 (72) QDP 50.29/18.22 (73) DependencyGraphProof [EQUIVALENT, 0 ms] 50.29/18.22 (74) TRUE 50.29/18.22 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (0) 50.29/18.22 Obligation: 50.29/18.22 ITRS problem: 50.29/18.22 50.29/18.22 The following function symbols are pre-defined: 50.29/18.22 <<< 50.29/18.22 & ~ Bwand: (Integer, Integer) -> Integer 50.29/18.22 >= ~ Ge: (Integer, Integer) -> Boolean 50.29/18.22 | ~ Bwor: (Integer, Integer) -> Integer 50.29/18.22 / ~ Div: (Integer, Integer) -> Integer 50.29/18.22 != ~ Neq: (Integer, Integer) -> Boolean 50.29/18.22 && ~ Land: (Boolean, Boolean) -> Boolean 50.29/18.22 ! ~ Lnot: (Boolean) -> Boolean 50.29/18.22 = ~ Eq: (Integer, Integer) -> Boolean 50.29/18.22 <= ~ Le: (Integer, Integer) -> Boolean 50.29/18.22 ^ ~ Bwxor: (Integer, Integer) -> Integer 50.29/18.22 % ~ Mod: (Integer, Integer) -> Integer 50.29/18.22 + ~ Add: (Integer, Integer) -> Integer 50.29/18.22 > ~ Gt: (Integer, Integer) -> Boolean 50.29/18.22 < ~ Lt: (Integer, Integer) -> Boolean 50.29/18.22 || ~ Lor: (Boolean, Boolean) -> Boolean 50.29/18.22 - ~ UnaryMinus: (Integer) -> Integer 50.29/18.22 - ~ Sub: (Integer, Integer) -> Integer 50.29/18.22 ~ ~ Bwnot: (Integer) -> Integer 50.29/18.22 * ~ Mul: (Integer, Integer) -> Integer 50.29/18.22 >>> 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 random(x) -> rand(x, 0) 50.29/18.22 rand(x, y) -> Cond_rand(x = 0, x, y) 50.29/18.22 Cond_rand(TRUE, x, y) -> y 50.29/18.22 rand(x, y) -> Cond_rand1(x > 0, x, y) 50.29/18.22 Cond_rand1(TRUE, x, y) -> rand(-(x) + 1, id_inc(y)) 50.29/18.22 rand(x, y) -> Cond_rand2(0 > x, x, y) 50.29/18.22 Cond_rand2(TRUE, x, y) -> rand(-(x) - 1, id_dec(y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> x + 1 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> x - 1 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(TRUE, x0, x1) 50.29/18.22 Cond_rand1(TRUE, x0, x1) 50.29/18.22 Cond_rand2(TRUE, x0, x1) 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (1) ITRStoIDPProof (EQUIVALENT) 50.29/18.22 Added dependency pairs 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (2) 50.29/18.22 Obligation: 50.29/18.22 IDP problem: 50.29/18.22 The following function symbols are pre-defined: 50.29/18.22 <<< 50.29/18.22 & ~ Bwand: (Integer, Integer) -> Integer 50.29/18.22 >= ~ Ge: (Integer, Integer) -> Boolean 50.29/18.22 | ~ Bwor: (Integer, Integer) -> Integer 50.29/18.22 / ~ Div: (Integer, Integer) -> Integer 50.29/18.22 != ~ Neq: (Integer, Integer) -> Boolean 50.29/18.22 && ~ Land: (Boolean, Boolean) -> Boolean 50.29/18.22 ! ~ Lnot: (Boolean) -> Boolean 50.29/18.22 = ~ Eq: (Integer, Integer) -> Boolean 50.29/18.22 <= ~ Le: (Integer, Integer) -> Boolean 50.29/18.22 ^ ~ Bwxor: (Integer, Integer) -> Integer 50.29/18.22 % ~ Mod: (Integer, Integer) -> Integer 50.29/18.22 + ~ Add: (Integer, Integer) -> Integer 50.29/18.22 > ~ Gt: (Integer, Integer) -> Boolean 50.29/18.22 < ~ Lt: (Integer, Integer) -> Boolean 50.29/18.22 || ~ Lor: (Boolean, Boolean) -> Boolean 50.29/18.22 - ~ UnaryMinus: (Integer) -> Integer 50.29/18.22 - ~ Sub: (Integer, Integer) -> Integer 50.29/18.22 ~ ~ Bwnot: (Integer) -> Integer 50.29/18.22 * ~ Mul: (Integer, Integer) -> Integer 50.29/18.22 >>> 50.29/18.22 50.29/18.22 50.29/18.22 The following domains are used: 50.29/18.22 Integer 50.29/18.22 50.29/18.22 The ITRS R consists of the following rules: 50.29/18.22 random(x) -> rand(x, 0) 50.29/18.22 rand(x, y) -> Cond_rand(x = 0, x, y) 50.29/18.22 Cond_rand(TRUE, x, y) -> y 50.29/18.22 rand(x, y) -> Cond_rand1(x > 0, x, y) 50.29/18.22 Cond_rand1(TRUE, x, y) -> rand(-(x) + 1, id_inc(y)) 50.29/18.22 rand(x, y) -> Cond_rand2(0 > x, x, y) 50.29/18.22 Cond_rand2(TRUE, x, y) -> rand(-(x) - 1, id_dec(y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> x + 1 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> x - 1 50.29/18.22 50.29/18.22 The integer pair graph contains the following rules and edges: 50.29/18.22 (0): RANDOM(x[0]) -> RAND(x[0], 0) 50.29/18.22 (1): RAND(x[1], y[1]) -> COND_RAND(x[1] = 0, x[1], y[1]) 50.29/18.22 (2): RAND(x[2], y[2]) -> COND_RAND1(x[2] > 0, x[2], y[2]) 50.29/18.22 (3): COND_RAND1(TRUE, x[3], y[3]) -> RAND(-(x[3]) + 1, id_inc(y[3])) 50.29/18.22 (4): COND_RAND1(TRUE, x[4], y[4]) -> ID_INC(y[4]) 50.29/18.22 (5): RAND(x[5], y[5]) -> COND_RAND2(0 > x[5], x[5], y[5]) 50.29/18.22 (6): COND_RAND2(TRUE, x[6], y[6]) -> RAND(-(x[6]) - 1, id_dec(y[6])) 50.29/18.22 (7): COND_RAND2(TRUE, x[7], y[7]) -> ID_DEC(y[7]) 50.29/18.22 50.29/18.22 (0) -> (1), if (x[0] ->^* x[1] & 0 ->^* y[1]) 50.29/18.22 (0) -> (2), if (x[0] ->^* x[2] & 0 ->^* y[2]) 50.29/18.22 (0) -> (5), if (x[0] ->^* x[5] & 0 ->^* y[5]) 50.29/18.22 (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) 50.29/18.22 (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4] & y[2] ->^* y[4]) 50.29/18.22 (3) -> (1), if (-(x[3]) + 1 ->^* x[1] & id_inc(y[3]) ->^* y[1]) 50.29/18.22 (3) -> (2), if (-(x[3]) + 1 ->^* x[2] & id_inc(y[3]) ->^* y[2]) 50.29/18.22 (3) -> (5), if (-(x[3]) + 1 ->^* x[5] & id_inc(y[3]) ->^* y[5]) 50.29/18.22 (5) -> (6), if (0 > x[5] & x[5] ->^* x[6] & y[5] ->^* y[6]) 50.29/18.22 (5) -> (7), if (0 > x[5] & x[5] ->^* x[7] & y[5] ->^* y[7]) 50.29/18.22 (6) -> (1), if (-(x[6]) - 1 ->^* x[1] & id_dec(y[6]) ->^* y[1]) 50.29/18.22 (6) -> (2), if (-(x[6]) - 1 ->^* x[2] & id_dec(y[6]) ->^* y[2]) 50.29/18.22 (6) -> (5), if (-(x[6]) - 1 ->^* x[5] & id_dec(y[6]) ->^* y[5]) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(TRUE, x0, x1) 50.29/18.22 Cond_rand1(TRUE, x0, x1) 50.29/18.22 Cond_rand2(TRUE, x0, x1) 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (3) UsableRulesProof (EQUIVALENT) 50.29/18.22 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. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (4) 50.29/18.22 Obligation: 50.29/18.22 IDP problem: 50.29/18.22 The following function symbols are pre-defined: 50.29/18.22 <<< 50.29/18.22 & ~ Bwand: (Integer, Integer) -> Integer 50.29/18.22 >= ~ Ge: (Integer, Integer) -> Boolean 50.29/18.22 | ~ Bwor: (Integer, Integer) -> Integer 50.29/18.22 / ~ Div: (Integer, Integer) -> Integer 50.29/18.22 != ~ Neq: (Integer, Integer) -> Boolean 50.29/18.22 && ~ Land: (Boolean, Boolean) -> Boolean 50.29/18.22 ! ~ Lnot: (Boolean) -> Boolean 50.29/18.22 = ~ Eq: (Integer, Integer) -> Boolean 50.29/18.22 <= ~ Le: (Integer, Integer) -> Boolean 50.29/18.22 ^ ~ Bwxor: (Integer, Integer) -> Integer 50.29/18.22 % ~ Mod: (Integer, Integer) -> Integer 50.29/18.22 + ~ Add: (Integer, Integer) -> Integer 50.29/18.22 > ~ Gt: (Integer, Integer) -> Boolean 50.29/18.22 < ~ Lt: (Integer, Integer) -> Boolean 50.29/18.22 || ~ Lor: (Boolean, Boolean) -> Boolean 50.29/18.22 - ~ UnaryMinus: (Integer) -> Integer 50.29/18.22 - ~ Sub: (Integer, Integer) -> Integer 50.29/18.22 ~ ~ Bwnot: (Integer) -> Integer 50.29/18.22 * ~ Mul: (Integer, Integer) -> Integer 50.29/18.22 >>> 50.29/18.22 50.29/18.22 50.29/18.22 The following domains are used: 50.29/18.22 Integer 50.29/18.22 50.29/18.22 The ITRS R consists of the following rules: 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> x + 1 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> x - 1 50.29/18.22 50.29/18.22 The integer pair graph contains the following rules and edges: 50.29/18.22 (0): RANDOM(x[0]) -> RAND(x[0], 0) 50.29/18.22 (1): RAND(x[1], y[1]) -> COND_RAND(x[1] = 0, x[1], y[1]) 50.29/18.22 (2): RAND(x[2], y[2]) -> COND_RAND1(x[2] > 0, x[2], y[2]) 50.29/18.22 (3): COND_RAND1(TRUE, x[3], y[3]) -> RAND(-(x[3]) + 1, id_inc(y[3])) 50.29/18.22 (4): COND_RAND1(TRUE, x[4], y[4]) -> ID_INC(y[4]) 50.29/18.22 (5): RAND(x[5], y[5]) -> COND_RAND2(0 > x[5], x[5], y[5]) 50.29/18.22 (6): COND_RAND2(TRUE, x[6], y[6]) -> RAND(-(x[6]) - 1, id_dec(y[6])) 50.29/18.22 (7): COND_RAND2(TRUE, x[7], y[7]) -> ID_DEC(y[7]) 50.29/18.22 50.29/18.22 (0) -> (1), if (x[0] ->^* x[1] & 0 ->^* y[1]) 50.29/18.22 (0) -> (2), if (x[0] ->^* x[2] & 0 ->^* y[2]) 50.29/18.22 (0) -> (5), if (x[0] ->^* x[5] & 0 ->^* y[5]) 50.29/18.22 (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) 50.29/18.22 (2) -> (4), if (x[2] > 0 & x[2] ->^* x[4] & y[2] ->^* y[4]) 50.29/18.22 (3) -> (1), if (-(x[3]) + 1 ->^* x[1] & id_inc(y[3]) ->^* y[1]) 50.29/18.22 (3) -> (2), if (-(x[3]) + 1 ->^* x[2] & id_inc(y[3]) ->^* y[2]) 50.29/18.22 (3) -> (5), if (-(x[3]) + 1 ->^* x[5] & id_inc(y[3]) ->^* y[5]) 50.29/18.22 (5) -> (6), if (0 > x[5] & x[5] ->^* x[6] & y[5] ->^* y[6]) 50.29/18.22 (5) -> (7), if (0 > x[5] & x[5] ->^* x[7] & y[5] ->^* y[7]) 50.29/18.22 (6) -> (1), if (-(x[6]) - 1 ->^* x[1] & id_dec(y[6]) ->^* y[1]) 50.29/18.22 (6) -> (2), if (-(x[6]) - 1 ->^* x[2] & id_dec(y[6]) ->^* y[2]) 50.29/18.22 (6) -> (5), if (-(x[6]) - 1 ->^* x[5] & id_dec(y[6]) ->^* y[5]) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(TRUE, x0, x1) 50.29/18.22 Cond_rand1(TRUE, x0, x1) 50.29/18.22 Cond_rand2(TRUE, x0, x1) 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (5) IDependencyGraphProof (EQUIVALENT) 50.29/18.22 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (6) 50.29/18.22 Obligation: 50.29/18.22 IDP problem: 50.29/18.22 The following function symbols are pre-defined: 50.29/18.22 <<< 50.29/18.22 & ~ Bwand: (Integer, Integer) -> Integer 50.29/18.22 >= ~ Ge: (Integer, Integer) -> Boolean 50.29/18.22 | ~ Bwor: (Integer, Integer) -> Integer 50.29/18.22 / ~ Div: (Integer, Integer) -> Integer 50.29/18.22 != ~ Neq: (Integer, Integer) -> Boolean 50.29/18.22 && ~ Land: (Boolean, Boolean) -> Boolean 50.29/18.22 ! ~ Lnot: (Boolean) -> Boolean 50.29/18.22 = ~ Eq: (Integer, Integer) -> Boolean 50.29/18.22 <= ~ Le: (Integer, Integer) -> Boolean 50.29/18.22 ^ ~ Bwxor: (Integer, Integer) -> Integer 50.29/18.22 % ~ Mod: (Integer, Integer) -> Integer 50.29/18.22 + ~ Add: (Integer, Integer) -> Integer 50.29/18.22 > ~ Gt: (Integer, Integer) -> Boolean 50.29/18.22 < ~ Lt: (Integer, Integer) -> Boolean 50.29/18.22 || ~ Lor: (Boolean, Boolean) -> Boolean 50.29/18.22 - ~ UnaryMinus: (Integer) -> Integer 50.29/18.22 - ~ Sub: (Integer, Integer) -> Integer 50.29/18.22 ~ ~ Bwnot: (Integer) -> Integer 50.29/18.22 * ~ Mul: (Integer, Integer) -> Integer 50.29/18.22 >>> 50.29/18.22 50.29/18.22 50.29/18.22 The following domains are used: 50.29/18.22 Integer 50.29/18.22 50.29/18.22 The ITRS R consists of the following rules: 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> x + 1 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> x - 1 50.29/18.22 50.29/18.22 The integer pair graph contains the following rules and edges: 50.29/18.22 (6): COND_RAND2(TRUE, x[6], y[6]) -> RAND(-(x[6]) - 1, id_dec(y[6])) 50.29/18.22 (5): RAND(x[5], y[5]) -> COND_RAND2(0 > x[5], x[5], y[5]) 50.29/18.22 (3): COND_RAND1(TRUE, x[3], y[3]) -> RAND(-(x[3]) + 1, id_inc(y[3])) 50.29/18.22 (2): RAND(x[2], y[2]) -> COND_RAND1(x[2] > 0, x[2], y[2]) 50.29/18.22 50.29/18.22 (3) -> (2), if (-(x[3]) + 1 ->^* x[2] & id_inc(y[3]) ->^* y[2]) 50.29/18.22 (6) -> (2), if (-(x[6]) - 1 ->^* x[2] & id_dec(y[6]) ->^* y[2]) 50.29/18.22 (2) -> (3), if (x[2] > 0 & x[2] ->^* x[3] & y[2] ->^* y[3]) 50.29/18.22 (3) -> (5), if (-(x[3]) + 1 ->^* x[5] & id_inc(y[3]) ->^* y[5]) 50.29/18.22 (6) -> (5), if (-(x[6]) - 1 ->^* x[5] & id_dec(y[6]) ->^* y[5]) 50.29/18.22 (5) -> (6), if (0 > x[5] & x[5] ->^* x[6] & y[5] ->^* y[6]) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(TRUE, x0, x1) 50.29/18.22 Cond_rand1(TRUE, x0, x1) 50.29/18.22 Cond_rand2(TRUE, x0, x1) 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (7) IDPtoQDPProof (SOUND) 50.29/18.22 Represented integers and predefined function symbols by Terms 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (8) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(neg(x), pos(y)) -> minus_nat(y, x) 50.29/18.22 plus_int(neg(x), neg(y)) -> neg(plus_nat(x, y)) 50.29/18.22 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.22 minus_nat(01, 01) -> pos(01) 50.29/18.22 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.22 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.22 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), neg(y)) -> minus_nat(y, x) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y)) 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 greater_int(pos(01), pos(01)) -> false 50.29/18.22 greater_int(pos(01), neg(01)) -> false 50.29/18.22 greater_int(neg(01), pos(01)) -> false 50.29/18.22 greater_int(neg(01), neg(01)) -> false 50.29/18.22 greater_int(pos(01), pos(s(y))) -> false 50.29/18.22 greater_int(neg(01), pos(s(y))) -> false 50.29/18.22 greater_int(pos(01), neg(s(y))) -> true 50.29/18.22 greater_int(neg(01), neg(s(y))) -> true 50.29/18.22 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.22 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.22 greater_int(pos(s(x)), neg(01)) -> true 50.29/18.22 greater_int(neg(s(x)), neg(01)) -> false 50.29/18.22 greater_int(pos(s(x)), neg(s(y))) -> true 50.29/18.22 greater_int(neg(s(x)), pos(s(y))) -> false 50.29/18.22 greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y)) 50.29/18.22 greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y)) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(true, x0, x1) 50.29/18.22 Cond_rand1(true, x0, x1) 50.29/18.22 Cond_rand2(true, x0, x1) 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 plus_int(pos(x0), neg(x1)) 50.29/18.22 plus_int(neg(x0), pos(x1)) 50.29/18.22 plus_int(neg(x0), neg(x1)) 50.29/18.22 plus_int(pos(x0), pos(x1)) 50.29/18.22 plus_nat(01, x0) 50.29/18.22 plus_nat(s(x0), x1) 50.29/18.22 minus_nat(01, 01) 50.29/18.22 minus_nat(01, s(x0)) 50.29/18.22 minus_nat(s(x0), 01) 50.29/18.22 minus_nat(s(x0), s(x1)) 50.29/18.22 minus_int(pos(x0), pos(x1)) 50.29/18.22 minus_int(neg(x0), neg(x1)) 50.29/18.22 minus_int(neg(x0), pos(x1)) 50.29/18.22 minus_int(pos(x0), neg(x1)) 50.29/18.22 neg_int(pos(x0)) 50.29/18.22 neg_int(neg(x0)) 50.29/18.22 greater_int(pos(01), pos(01)) 50.29/18.22 greater_int(pos(01), neg(01)) 50.29/18.22 greater_int(neg(01), pos(01)) 50.29/18.22 greater_int(neg(01), neg(01)) 50.29/18.22 greater_int(pos(01), pos(s(x0))) 50.29/18.22 greater_int(neg(01), pos(s(x0))) 50.29/18.22 greater_int(pos(01), neg(s(x0))) 50.29/18.22 greater_int(neg(01), neg(s(x0))) 50.29/18.22 greater_int(pos(s(x0)), pos(01)) 50.29/18.22 greater_int(neg(s(x0)), pos(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(01)) 50.29/18.22 greater_int(neg(s(x0)), neg(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.22 50.29/18.22 We have to consider all minimal (P,Q,R)-chains. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (9) UsableRulesProof (EQUIVALENT) 50.29/18.22 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. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (10) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 greater_int(pos(01), pos(01)) -> false 50.29/18.22 greater_int(neg(01), pos(01)) -> false 50.29/18.22 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.22 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.22 minus_nat(01, 01) -> pos(01) 50.29/18.22 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.22 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.22 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.22 greater_int(pos(01), neg(01)) -> false 50.29/18.22 greater_int(pos(01), pos(s(y))) -> false 50.29/18.22 greater_int(pos(01), neg(s(y))) -> true 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(true, x0, x1) 50.29/18.22 Cond_rand1(true, x0, x1) 50.29/18.22 Cond_rand2(true, x0, x1) 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 plus_int(pos(x0), neg(x1)) 50.29/18.22 plus_int(neg(x0), pos(x1)) 50.29/18.22 plus_int(neg(x0), neg(x1)) 50.29/18.22 plus_int(pos(x0), pos(x1)) 50.29/18.22 plus_nat(01, x0) 50.29/18.22 plus_nat(s(x0), x1) 50.29/18.22 minus_nat(01, 01) 50.29/18.22 minus_nat(01, s(x0)) 50.29/18.22 minus_nat(s(x0), 01) 50.29/18.22 minus_nat(s(x0), s(x1)) 50.29/18.22 minus_int(pos(x0), pos(x1)) 50.29/18.22 minus_int(neg(x0), neg(x1)) 50.29/18.22 minus_int(neg(x0), pos(x1)) 50.29/18.22 minus_int(pos(x0), neg(x1)) 50.29/18.22 neg_int(pos(x0)) 50.29/18.22 neg_int(neg(x0)) 50.29/18.22 greater_int(pos(01), pos(01)) 50.29/18.22 greater_int(pos(01), neg(01)) 50.29/18.22 greater_int(neg(01), pos(01)) 50.29/18.22 greater_int(neg(01), neg(01)) 50.29/18.22 greater_int(pos(01), pos(s(x0))) 50.29/18.22 greater_int(neg(01), pos(s(x0))) 50.29/18.22 greater_int(pos(01), neg(s(x0))) 50.29/18.22 greater_int(neg(01), neg(s(x0))) 50.29/18.22 greater_int(pos(s(x0)), pos(01)) 50.29/18.22 greater_int(neg(s(x0)), pos(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(01)) 50.29/18.22 greater_int(neg(s(x0)), neg(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.22 50.29/18.22 We have to consider all minimal (P,Q,R)-chains. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (11) QReductionProof (EQUIVALENT) 50.29/18.22 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 50.29/18.22 50.29/18.22 random(x0) 50.29/18.22 rand(x0, x1) 50.29/18.22 Cond_rand(true, x0, x1) 50.29/18.22 Cond_rand1(true, x0, x1) 50.29/18.22 Cond_rand2(true, x0, x1) 50.29/18.22 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (12) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 RAND(x[5], y[5]) -> COND_RAND2(greater_int(pos(01), x[5]), x[5], y[5]) 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 greater_int(pos(01), pos(01)) -> false 50.29/18.22 greater_int(neg(01), pos(01)) -> false 50.29/18.22 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.22 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.22 minus_nat(01, 01) -> pos(01) 50.29/18.22 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.22 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.22 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.22 greater_int(pos(01), neg(01)) -> false 50.29/18.22 greater_int(pos(01), pos(s(y))) -> false 50.29/18.22 greater_int(pos(01), neg(s(y))) -> true 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 plus_int(pos(x0), neg(x1)) 50.29/18.22 plus_int(neg(x0), pos(x1)) 50.29/18.22 plus_int(neg(x0), neg(x1)) 50.29/18.22 plus_int(pos(x0), pos(x1)) 50.29/18.22 plus_nat(01, x0) 50.29/18.22 plus_nat(s(x0), x1) 50.29/18.22 minus_nat(01, 01) 50.29/18.22 minus_nat(01, s(x0)) 50.29/18.22 minus_nat(s(x0), 01) 50.29/18.22 minus_nat(s(x0), s(x1)) 50.29/18.22 minus_int(pos(x0), pos(x1)) 50.29/18.22 minus_int(neg(x0), neg(x1)) 50.29/18.22 minus_int(neg(x0), pos(x1)) 50.29/18.22 minus_int(pos(x0), neg(x1)) 50.29/18.22 neg_int(pos(x0)) 50.29/18.22 neg_int(neg(x0)) 50.29/18.22 greater_int(pos(01), pos(01)) 50.29/18.22 greater_int(pos(01), neg(01)) 50.29/18.22 greater_int(neg(01), pos(01)) 50.29/18.22 greater_int(neg(01), neg(01)) 50.29/18.22 greater_int(pos(01), pos(s(x0))) 50.29/18.22 greater_int(neg(01), pos(s(x0))) 50.29/18.22 greater_int(pos(01), neg(s(x0))) 50.29/18.22 greater_int(neg(01), neg(s(x0))) 50.29/18.22 greater_int(pos(s(x0)), pos(01)) 50.29/18.22 greater_int(neg(s(x0)), pos(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(01)) 50.29/18.22 greater_int(neg(s(x0)), neg(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.22 50.29/18.22 We have to consider all minimal (P,Q,R)-chains. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (13) TransformationProof (EQUIVALENT) 50.29/18.22 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]: 50.29/18.22 50.29/18.22 (RAND(pos(01), y1) -> COND_RAND2(false, pos(01), y1),RAND(pos(01), y1) -> COND_RAND2(false, pos(01), y1)) 50.29/18.22 (RAND(neg(01), y1) -> COND_RAND2(false, neg(01), y1),RAND(neg(01), y1) -> COND_RAND2(false, neg(01), y1)) 50.29/18.22 (RAND(pos(s(x0)), y1) -> COND_RAND2(false, pos(s(x0)), y1),RAND(pos(s(x0)), y1) -> COND_RAND2(false, pos(s(x0)), y1)) 50.29/18.22 (RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1),RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1)) 50.29/18.22 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (14) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) 50.29/18.22 RAND(pos(01), y1) -> COND_RAND2(false, pos(01), y1) 50.29/18.22 RAND(neg(01), y1) -> COND_RAND2(false, neg(01), y1) 50.29/18.22 RAND(pos(s(x0)), y1) -> COND_RAND2(false, pos(s(x0)), y1) 50.29/18.22 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 greater_int(pos(01), pos(01)) -> false 50.29/18.22 greater_int(neg(01), pos(01)) -> false 50.29/18.22 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.22 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.22 minus_nat(01, 01) -> pos(01) 50.29/18.22 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.22 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.22 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.22 greater_int(pos(01), neg(01)) -> false 50.29/18.22 greater_int(pos(01), pos(s(y))) -> false 50.29/18.22 greater_int(pos(01), neg(s(y))) -> true 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 plus_int(pos(x0), neg(x1)) 50.29/18.22 plus_int(neg(x0), pos(x1)) 50.29/18.22 plus_int(neg(x0), neg(x1)) 50.29/18.22 plus_int(pos(x0), pos(x1)) 50.29/18.22 plus_nat(01, x0) 50.29/18.22 plus_nat(s(x0), x1) 50.29/18.22 minus_nat(01, 01) 50.29/18.22 minus_nat(01, s(x0)) 50.29/18.22 minus_nat(s(x0), 01) 50.29/18.22 minus_nat(s(x0), s(x1)) 50.29/18.22 minus_int(pos(x0), pos(x1)) 50.29/18.22 minus_int(neg(x0), neg(x1)) 50.29/18.22 minus_int(neg(x0), pos(x1)) 50.29/18.22 minus_int(pos(x0), neg(x1)) 50.29/18.22 neg_int(pos(x0)) 50.29/18.22 neg_int(neg(x0)) 50.29/18.22 greater_int(pos(01), pos(01)) 50.29/18.22 greater_int(pos(01), neg(01)) 50.29/18.22 greater_int(neg(01), pos(01)) 50.29/18.22 greater_int(neg(01), neg(01)) 50.29/18.22 greater_int(pos(01), pos(s(x0))) 50.29/18.22 greater_int(neg(01), pos(s(x0))) 50.29/18.22 greater_int(pos(01), neg(s(x0))) 50.29/18.22 greater_int(neg(01), neg(s(x0))) 50.29/18.22 greater_int(pos(s(x0)), pos(01)) 50.29/18.22 greater_int(neg(s(x0)), pos(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(01)) 50.29/18.22 greater_int(neg(s(x0)), neg(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.22 50.29/18.22 We have to consider all minimal (P,Q,R)-chains. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (15) DependencyGraphProof (EQUIVALENT) 50.29/18.22 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (16) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 greater_int(pos(01), pos(01)) -> false 50.29/18.22 greater_int(neg(01), pos(01)) -> false 50.29/18.22 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.22 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.22 minus_nat(01, 01) -> pos(01) 50.29/18.22 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.22 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.22 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.22 greater_int(pos(01), neg(01)) -> false 50.29/18.22 greater_int(pos(01), pos(s(y))) -> false 50.29/18.22 greater_int(pos(01), neg(s(y))) -> true 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 plus_int(pos(x0), neg(x1)) 50.29/18.22 plus_int(neg(x0), pos(x1)) 50.29/18.22 plus_int(neg(x0), neg(x1)) 50.29/18.22 plus_int(pos(x0), pos(x1)) 50.29/18.22 plus_nat(01, x0) 50.29/18.22 plus_nat(s(x0), x1) 50.29/18.22 minus_nat(01, 01) 50.29/18.22 minus_nat(01, s(x0)) 50.29/18.22 minus_nat(s(x0), 01) 50.29/18.22 minus_nat(s(x0), s(x1)) 50.29/18.22 minus_int(pos(x0), pos(x1)) 50.29/18.22 minus_int(neg(x0), neg(x1)) 50.29/18.22 minus_int(neg(x0), pos(x1)) 50.29/18.22 minus_int(pos(x0), neg(x1)) 50.29/18.22 neg_int(pos(x0)) 50.29/18.22 neg_int(neg(x0)) 50.29/18.22 greater_int(pos(01), pos(01)) 50.29/18.22 greater_int(pos(01), neg(01)) 50.29/18.22 greater_int(neg(01), pos(01)) 50.29/18.22 greater_int(neg(01), neg(01)) 50.29/18.22 greater_int(pos(01), pos(s(x0))) 50.29/18.22 greater_int(neg(01), pos(s(x0))) 50.29/18.22 greater_int(pos(01), neg(s(x0))) 50.29/18.22 greater_int(neg(01), neg(s(x0))) 50.29/18.22 greater_int(pos(s(x0)), pos(01)) 50.29/18.22 greater_int(neg(s(x0)), pos(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(01)) 50.29/18.22 greater_int(neg(s(x0)), neg(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.22 50.29/18.22 We have to consider all minimal (P,Q,R)-chains. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (17) UsableRulesProof (EQUIVALENT) 50.29/18.22 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. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (18) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 RAND(x[2], y[2]) -> COND_RAND1(greater_int(x[2], pos(01)), x[2], y[2]) 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.22 minus_nat(01, 01) -> pos(01) 50.29/18.22 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.22 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.22 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.22 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.22 id_inc(x) -> x 50.29/18.22 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.22 greater_int(pos(01), pos(01)) -> false 50.29/18.22 greater_int(neg(01), pos(01)) -> false 50.29/18.22 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.22 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.22 50.29/18.22 The set Q consists of the following terms: 50.29/18.22 50.29/18.22 id_inc(x0) 50.29/18.22 id_dec(x0) 50.29/18.22 plus_int(pos(x0), neg(x1)) 50.29/18.22 plus_int(neg(x0), pos(x1)) 50.29/18.22 plus_int(neg(x0), neg(x1)) 50.29/18.22 plus_int(pos(x0), pos(x1)) 50.29/18.22 plus_nat(01, x0) 50.29/18.22 plus_nat(s(x0), x1) 50.29/18.22 minus_nat(01, 01) 50.29/18.22 minus_nat(01, s(x0)) 50.29/18.22 minus_nat(s(x0), 01) 50.29/18.22 minus_nat(s(x0), s(x1)) 50.29/18.22 minus_int(pos(x0), pos(x1)) 50.29/18.22 minus_int(neg(x0), neg(x1)) 50.29/18.22 minus_int(neg(x0), pos(x1)) 50.29/18.22 minus_int(pos(x0), neg(x1)) 50.29/18.22 neg_int(pos(x0)) 50.29/18.22 neg_int(neg(x0)) 50.29/18.22 greater_int(pos(01), pos(01)) 50.29/18.22 greater_int(pos(01), neg(01)) 50.29/18.22 greater_int(neg(01), pos(01)) 50.29/18.22 greater_int(neg(01), neg(01)) 50.29/18.22 greater_int(pos(01), pos(s(x0))) 50.29/18.22 greater_int(neg(01), pos(s(x0))) 50.29/18.22 greater_int(pos(01), neg(s(x0))) 50.29/18.22 greater_int(neg(01), neg(s(x0))) 50.29/18.22 greater_int(pos(s(x0)), pos(01)) 50.29/18.22 greater_int(neg(s(x0)), pos(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(01)) 50.29/18.22 greater_int(neg(s(x0)), neg(01)) 50.29/18.22 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.22 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.22 50.29/18.22 We have to consider all minimal (P,Q,R)-chains. 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (19) TransformationProof (EQUIVALENT) 50.29/18.22 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]: 50.29/18.22 50.29/18.22 (RAND(pos(01), y1) -> COND_RAND1(false, pos(01), y1),RAND(pos(01), y1) -> COND_RAND1(false, pos(01), y1)) 50.29/18.22 (RAND(neg(01), y1) -> COND_RAND1(false, neg(01), y1),RAND(neg(01), y1) -> COND_RAND1(false, neg(01), y1)) 50.29/18.22 (RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1),RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1)) 50.29/18.22 (RAND(neg(s(x0)), y1) -> COND_RAND1(false, neg(s(x0)), y1),RAND(neg(s(x0)), y1) -> COND_RAND1(false, neg(s(x0)), y1)) 50.29/18.22 50.29/18.22 50.29/18.22 ---------------------------------------- 50.29/18.22 50.29/18.22 (20) 50.29/18.22 Obligation: 50.29/18.22 Q DP problem: 50.29/18.22 The TRS P consists of the following rules: 50.29/18.22 50.29/18.22 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.22 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.22 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.22 RAND(pos(01), y1) -> COND_RAND1(false, pos(01), y1) 50.29/18.22 RAND(neg(01), y1) -> COND_RAND1(false, neg(01), y1) 50.29/18.22 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.29/18.22 RAND(neg(s(x0)), y1) -> COND_RAND1(false, neg(s(x0)), y1) 50.29/18.22 50.29/18.22 The TRS R consists of the following rules: 50.29/18.22 50.29/18.22 neg_int(pos(x)) -> neg(x) 50.29/18.22 neg_int(neg(x)) -> pos(x) 50.29/18.22 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.22 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.22 id_dec(x) -> x 50.29/18.22 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.22 plus_nat(01, x) -> x 50.29/18.22 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.23 minus_nat(01, 01) -> pos(01) 50.29/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.23 id_inc(x) -> x 50.29/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.23 greater_int(pos(01), pos(01)) -> false 50.29/18.23 greater_int(neg(01), pos(01)) -> false 50.29/18.23 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.23 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.23 50.29/18.23 The set Q consists of the following terms: 50.29/18.23 50.29/18.23 id_inc(x0) 50.29/18.23 id_dec(x0) 50.29/18.23 plus_int(pos(x0), neg(x1)) 50.29/18.23 plus_int(neg(x0), pos(x1)) 50.29/18.23 plus_int(neg(x0), neg(x1)) 50.29/18.23 plus_int(pos(x0), pos(x1)) 50.29/18.23 plus_nat(01, x0) 50.29/18.23 plus_nat(s(x0), x1) 50.29/18.23 minus_nat(01, 01) 50.29/18.23 minus_nat(01, s(x0)) 50.29/18.23 minus_nat(s(x0), 01) 50.29/18.23 minus_nat(s(x0), s(x1)) 50.29/18.23 minus_int(pos(x0), pos(x1)) 50.29/18.23 minus_int(neg(x0), neg(x1)) 50.29/18.23 minus_int(neg(x0), pos(x1)) 50.29/18.23 minus_int(pos(x0), neg(x1)) 50.29/18.23 neg_int(pos(x0)) 50.29/18.23 neg_int(neg(x0)) 50.29/18.23 greater_int(pos(01), pos(01)) 50.29/18.23 greater_int(pos(01), neg(01)) 50.29/18.23 greater_int(neg(01), pos(01)) 50.29/18.23 greater_int(neg(01), neg(01)) 50.29/18.23 greater_int(pos(01), pos(s(x0))) 50.29/18.23 greater_int(neg(01), pos(s(x0))) 50.29/18.23 greater_int(pos(01), neg(s(x0))) 50.29/18.23 greater_int(neg(01), neg(s(x0))) 50.29/18.23 greater_int(pos(s(x0)), pos(01)) 50.29/18.23 greater_int(neg(s(x0)), pos(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(01)) 50.29/18.23 greater_int(neg(s(x0)), neg(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.23 50.29/18.23 We have to consider all minimal (P,Q,R)-chains. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (21) DependencyGraphProof (EQUIVALENT) 50.29/18.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (22) 50.29/18.23 Obligation: 50.29/18.23 Q DP problem: 50.29/18.23 The TRS P consists of the following rules: 50.29/18.23 50.29/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.23 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.29/18.23 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.23 50.29/18.23 The TRS R consists of the following rules: 50.29/18.23 50.29/18.23 neg_int(pos(x)) -> neg(x) 50.29/18.23 neg_int(neg(x)) -> pos(x) 50.29/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.23 id_dec(x) -> x 50.29/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.23 plus_nat(01, x) -> x 50.29/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.23 minus_nat(01, 01) -> pos(01) 50.29/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.23 id_inc(x) -> x 50.29/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.23 greater_int(pos(01), pos(01)) -> false 50.29/18.23 greater_int(neg(01), pos(01)) -> false 50.29/18.23 greater_int(pos(s(x)), pos(01)) -> true 50.29/18.23 greater_int(neg(s(x)), pos(01)) -> false 50.29/18.23 50.29/18.23 The set Q consists of the following terms: 50.29/18.23 50.29/18.23 id_inc(x0) 50.29/18.23 id_dec(x0) 50.29/18.23 plus_int(pos(x0), neg(x1)) 50.29/18.23 plus_int(neg(x0), pos(x1)) 50.29/18.23 plus_int(neg(x0), neg(x1)) 50.29/18.23 plus_int(pos(x0), pos(x1)) 50.29/18.23 plus_nat(01, x0) 50.29/18.23 plus_nat(s(x0), x1) 50.29/18.23 minus_nat(01, 01) 50.29/18.23 minus_nat(01, s(x0)) 50.29/18.23 minus_nat(s(x0), 01) 50.29/18.23 minus_nat(s(x0), s(x1)) 50.29/18.23 minus_int(pos(x0), pos(x1)) 50.29/18.23 minus_int(neg(x0), neg(x1)) 50.29/18.23 minus_int(neg(x0), pos(x1)) 50.29/18.23 minus_int(pos(x0), neg(x1)) 50.29/18.23 neg_int(pos(x0)) 50.29/18.23 neg_int(neg(x0)) 50.29/18.23 greater_int(pos(01), pos(01)) 50.29/18.23 greater_int(pos(01), neg(01)) 50.29/18.23 greater_int(neg(01), pos(01)) 50.29/18.23 greater_int(neg(01), neg(01)) 50.29/18.23 greater_int(pos(01), pos(s(x0))) 50.29/18.23 greater_int(neg(01), pos(s(x0))) 50.29/18.23 greater_int(pos(01), neg(s(x0))) 50.29/18.23 greater_int(neg(01), neg(s(x0))) 50.29/18.23 greater_int(pos(s(x0)), pos(01)) 50.29/18.23 greater_int(neg(s(x0)), pos(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(01)) 50.29/18.23 greater_int(neg(s(x0)), neg(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.23 50.29/18.23 We have to consider all minimal (P,Q,R)-chains. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (23) UsableRulesProof (EQUIVALENT) 50.29/18.23 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. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (24) 50.29/18.23 Obligation: 50.29/18.23 Q DP problem: 50.29/18.23 The TRS P consists of the following rules: 50.29/18.23 50.29/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.23 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.29/18.23 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.23 50.29/18.23 The TRS R consists of the following rules: 50.29/18.23 50.29/18.23 neg_int(pos(x)) -> neg(x) 50.29/18.23 neg_int(neg(x)) -> pos(x) 50.29/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.23 id_inc(x) -> x 50.29/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.23 plus_nat(01, x) -> x 50.29/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.23 minus_nat(01, 01) -> pos(01) 50.29/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.23 id_dec(x) -> x 50.29/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.23 50.29/18.23 The set Q consists of the following terms: 50.29/18.23 50.29/18.23 id_inc(x0) 50.29/18.23 id_dec(x0) 50.29/18.23 plus_int(pos(x0), neg(x1)) 50.29/18.23 plus_int(neg(x0), pos(x1)) 50.29/18.23 plus_int(neg(x0), neg(x1)) 50.29/18.23 plus_int(pos(x0), pos(x1)) 50.29/18.23 plus_nat(01, x0) 50.29/18.23 plus_nat(s(x0), x1) 50.29/18.23 minus_nat(01, 01) 50.29/18.23 minus_nat(01, s(x0)) 50.29/18.23 minus_nat(s(x0), 01) 50.29/18.23 minus_nat(s(x0), s(x1)) 50.29/18.23 minus_int(pos(x0), pos(x1)) 50.29/18.23 minus_int(neg(x0), neg(x1)) 50.29/18.23 minus_int(neg(x0), pos(x1)) 50.29/18.23 minus_int(pos(x0), neg(x1)) 50.29/18.23 neg_int(pos(x0)) 50.29/18.23 neg_int(neg(x0)) 50.29/18.23 greater_int(pos(01), pos(01)) 50.29/18.23 greater_int(pos(01), neg(01)) 50.29/18.23 greater_int(neg(01), pos(01)) 50.29/18.23 greater_int(neg(01), neg(01)) 50.29/18.23 greater_int(pos(01), pos(s(x0))) 50.29/18.23 greater_int(neg(01), pos(s(x0))) 50.29/18.23 greater_int(pos(01), neg(s(x0))) 50.29/18.23 greater_int(neg(01), neg(s(x0))) 50.29/18.23 greater_int(pos(s(x0)), pos(01)) 50.29/18.23 greater_int(neg(s(x0)), pos(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(01)) 50.29/18.23 greater_int(neg(s(x0)), neg(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.23 50.29/18.23 We have to consider all minimal (P,Q,R)-chains. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (25) QReductionProof (EQUIVALENT) 50.29/18.23 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 50.29/18.23 50.29/18.23 greater_int(pos(01), pos(01)) 50.29/18.23 greater_int(pos(01), neg(01)) 50.29/18.23 greater_int(neg(01), pos(01)) 50.29/18.23 greater_int(neg(01), neg(01)) 50.29/18.23 greater_int(pos(01), pos(s(x0))) 50.29/18.23 greater_int(neg(01), pos(s(x0))) 50.29/18.23 greater_int(pos(01), neg(s(x0))) 50.29/18.23 greater_int(neg(01), neg(s(x0))) 50.29/18.23 greater_int(pos(s(x0)), pos(01)) 50.29/18.23 greater_int(neg(s(x0)), pos(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(01)) 50.29/18.23 greater_int(neg(s(x0)), neg(01)) 50.29/18.23 greater_int(pos(s(x0)), neg(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(pos(s(x0)), pos(s(x1))) 50.29/18.23 greater_int(neg(s(x0)), neg(s(x1))) 50.29/18.23 50.29/18.23 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (26) 50.29/18.23 Obligation: 50.29/18.23 Q DP problem: 50.29/18.23 The TRS P consists of the following rules: 50.29/18.23 50.29/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.23 COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) 50.29/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.29/18.23 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.23 50.29/18.23 The TRS R consists of the following rules: 50.29/18.23 50.29/18.23 neg_int(pos(x)) -> neg(x) 50.29/18.23 neg_int(neg(x)) -> pos(x) 50.29/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.23 id_inc(x) -> x 50.29/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.23 plus_nat(01, x) -> x 50.29/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.23 minus_nat(01, 01) -> pos(01) 50.29/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.23 id_dec(x) -> x 50.29/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.23 50.29/18.23 The set Q consists of the following terms: 50.29/18.23 50.29/18.23 id_inc(x0) 50.29/18.23 id_dec(x0) 50.29/18.23 plus_int(pos(x0), neg(x1)) 50.29/18.23 plus_int(neg(x0), pos(x1)) 50.29/18.23 plus_int(neg(x0), neg(x1)) 50.29/18.23 plus_int(pos(x0), pos(x1)) 50.29/18.23 plus_nat(01, x0) 50.29/18.23 plus_nat(s(x0), x1) 50.29/18.23 minus_nat(01, 01) 50.29/18.23 minus_nat(01, s(x0)) 50.29/18.23 minus_nat(s(x0), 01) 50.29/18.23 minus_nat(s(x0), s(x1)) 50.29/18.23 minus_int(pos(x0), pos(x1)) 50.29/18.23 minus_int(neg(x0), neg(x1)) 50.29/18.23 minus_int(neg(x0), pos(x1)) 50.29/18.23 minus_int(pos(x0), neg(x1)) 50.29/18.23 neg_int(pos(x0)) 50.29/18.23 neg_int(neg(x0)) 50.29/18.23 50.29/18.23 We have to consider all minimal (P,Q,R)-chains. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (27) TransformationProof (EQUIVALENT) 50.29/18.23 By narrowing [LPAR04] the rule COND_RAND2(true, x[6], y[6]) -> RAND(minus_int(neg_int(x[6]), pos(s(01))), id_dec(y[6])) at position [0] we obtained the following new rules [LPAR04]: 50.29/18.23 50.29/18.23 (COND_RAND2(true, pos(x0), y1) -> RAND(minus_int(neg(x0), pos(s(01))), id_dec(y1)),COND_RAND2(true, pos(x0), y1) -> RAND(minus_int(neg(x0), pos(s(01))), id_dec(y1))) 50.29/18.23 (COND_RAND2(true, neg(x0), y1) -> RAND(minus_int(pos(x0), pos(s(01))), id_dec(y1)),COND_RAND2(true, neg(x0), y1) -> RAND(minus_int(pos(x0), pos(s(01))), id_dec(y1))) 50.29/18.23 50.29/18.23 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (28) 50.29/18.23 Obligation: 50.29/18.23 Q DP problem: 50.29/18.23 The TRS P consists of the following rules: 50.29/18.23 50.29/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.29/18.23 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.23 COND_RAND2(true, pos(x0), y1) -> RAND(minus_int(neg(x0), pos(s(01))), id_dec(y1)) 50.29/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_int(pos(x0), pos(s(01))), id_dec(y1)) 50.29/18.23 50.29/18.23 The TRS R consists of the following rules: 50.29/18.23 50.29/18.23 neg_int(pos(x)) -> neg(x) 50.29/18.23 neg_int(neg(x)) -> pos(x) 50.29/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.23 id_inc(x) -> x 50.29/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.23 plus_nat(01, x) -> x 50.29/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.23 minus_nat(01, 01) -> pos(01) 50.29/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.23 id_dec(x) -> x 50.29/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.23 50.29/18.23 The set Q consists of the following terms: 50.29/18.23 50.29/18.23 id_inc(x0) 50.29/18.23 id_dec(x0) 50.29/18.23 plus_int(pos(x0), neg(x1)) 50.29/18.23 plus_int(neg(x0), pos(x1)) 50.29/18.23 plus_int(neg(x0), neg(x1)) 50.29/18.23 plus_int(pos(x0), pos(x1)) 50.29/18.23 plus_nat(01, x0) 50.29/18.23 plus_nat(s(x0), x1) 50.29/18.23 minus_nat(01, 01) 50.29/18.23 minus_nat(01, s(x0)) 50.29/18.23 minus_nat(s(x0), 01) 50.29/18.23 minus_nat(s(x0), s(x1)) 50.29/18.23 minus_int(pos(x0), pos(x1)) 50.29/18.23 minus_int(neg(x0), neg(x1)) 50.29/18.23 minus_int(neg(x0), pos(x1)) 50.29/18.23 minus_int(pos(x0), neg(x1)) 50.29/18.23 neg_int(pos(x0)) 50.29/18.23 neg_int(neg(x0)) 50.29/18.23 50.29/18.23 We have to consider all minimal (P,Q,R)-chains. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (29) DependencyGraphProof (EQUIVALENT) 50.29/18.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (30) 50.29/18.23 Obligation: 50.29/18.23 Q DP problem: 50.29/18.23 The TRS P consists of the following rules: 50.29/18.23 50.29/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_int(pos(x0), pos(s(01))), id_dec(y1)) 50.29/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.29/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.29/18.23 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.29/18.23 50.29/18.23 The TRS R consists of the following rules: 50.29/18.23 50.29/18.23 neg_int(pos(x)) -> neg(x) 50.29/18.23 neg_int(neg(x)) -> pos(x) 50.29/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.29/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.29/18.23 id_inc(x) -> x 50.29/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.29/18.23 plus_nat(01, x) -> x 50.29/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.29/18.23 minus_nat(01, 01) -> pos(01) 50.29/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.29/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.29/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.29/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.29/18.23 id_dec(x) -> x 50.29/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.29/18.23 50.29/18.23 The set Q consists of the following terms: 50.29/18.23 50.29/18.23 id_inc(x0) 50.29/18.23 id_dec(x0) 50.29/18.23 plus_int(pos(x0), neg(x1)) 50.29/18.23 plus_int(neg(x0), pos(x1)) 50.29/18.23 plus_int(neg(x0), neg(x1)) 50.29/18.23 plus_int(pos(x0), pos(x1)) 50.29/18.23 plus_nat(01, x0) 50.29/18.23 plus_nat(s(x0), x1) 50.29/18.23 minus_nat(01, 01) 50.29/18.23 minus_nat(01, s(x0)) 50.29/18.23 minus_nat(s(x0), 01) 50.29/18.23 minus_nat(s(x0), s(x1)) 50.29/18.23 minus_int(pos(x0), pos(x1)) 50.29/18.23 minus_int(neg(x0), neg(x1)) 50.29/18.23 minus_int(neg(x0), pos(x1)) 50.29/18.23 minus_int(pos(x0), neg(x1)) 50.29/18.23 neg_int(pos(x0)) 50.29/18.23 neg_int(neg(x0)) 50.29/18.23 50.29/18.23 We have to consider all minimal (P,Q,R)-chains. 50.29/18.23 ---------------------------------------- 50.29/18.23 50.29/18.23 (31) TransformationProof (EQUIVALENT) 50.29/18.23 By rewriting [LPAR04] the rule COND_RAND2(true, neg(x0), y1) -> RAND(minus_int(pos(x0), pos(s(01))), id_dec(y1)) at position [0] we obtained the following new rules [LPAR04]: 50.29/18.23 50.29/18.23 (COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)),COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (32) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) 50.44/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 neg_int(pos(x)) -> neg(x) 50.44/18.23 neg_int(neg(x)) -> pos(x) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 neg_int(pos(x0)) 50.44/18.23 neg_int(neg(x0)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (33) TransformationProof (EQUIVALENT) 50.44/18.23 By narrowing [LPAR04] the rule COND_RAND1(true, x[3], y[3]) -> RAND(plus_int(pos(s(01)), neg_int(x[3])), id_inc(y[3])) at position [0] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1)),COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1))) 50.44/18.23 (COND_RAND1(true, neg(x0), y1) -> RAND(plus_int(pos(s(01)), pos(x0)), id_inc(y1)),COND_RAND1(true, neg(x0), y1) -> RAND(plus_int(pos(s(01)), pos(x0)), id_inc(y1))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (34) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1)) 50.44/18.23 COND_RAND1(true, neg(x0), y1) -> RAND(plus_int(pos(s(01)), pos(x0)), id_inc(y1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 neg_int(pos(x)) -> neg(x) 50.44/18.23 neg_int(neg(x)) -> pos(x) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 neg_int(pos(x0)) 50.44/18.23 neg_int(neg(x0)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (35) DependencyGraphProof (EQUIVALENT) 50.44/18.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (36) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 neg_int(pos(x)) -> neg(x) 50.44/18.23 neg_int(neg(x)) -> pos(x) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 neg_int(pos(x0)) 50.44/18.23 neg_int(neg(x0)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (37) UsableRulesProof (EQUIVALENT) 50.44/18.23 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. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (38) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 neg_int(pos(x0)) 50.44/18.23 neg_int(neg(x0)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (39) QReductionProof (EQUIVALENT) 50.44/18.23 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 50.44/18.23 50.44/18.23 neg_int(pos(x0)) 50.44/18.23 neg_int(neg(x0)) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (40) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (41) TransformationProof (EQUIVALENT) 50.44/18.23 By rewriting [LPAR04] the rule COND_RAND1(true, pos(x0), y1) -> RAND(plus_int(pos(s(01)), neg(x0)), id_inc(y1)) at position [0] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1)),COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (42) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (43) TransformationProof (EQUIVALENT) 50.44/18.23 By narrowing [LPAR04] the rule COND_RAND2(true, neg(x0), y1) -> RAND(minus_nat(x0, s(01)), id_dec(y1)) at position [1] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0),COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0)) 50.44/18.23 (COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))),COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01))))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (44) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1)) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 id_dec(x) -> x 50.44/18.23 id_dec(x) -> minus_int(x, pos(s(01))) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (45) UsableRulesProof (EQUIVALENT) 50.44/18.23 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. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (46) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1)) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 id_dec(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (47) QReductionProof (EQUIVALENT) 50.44/18.23 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 50.44/18.23 50.44/18.23 id_dec(x0) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (48) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1)) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (49) TransformationProof (EQUIVALENT) 50.44/18.23 By narrowing [LPAR04] the rule COND_RAND1(true, pos(x0), y1) -> RAND(minus_nat(s(01), x0), id_inc(y1)) at position [1] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0),COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0)) 50.44/18.23 (COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)),COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (50) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 id_inc(x) -> x 50.44/18.23 id_inc(x) -> plus_int(pos(s(01)), x) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (51) UsableRulesProof (EQUIVALENT) 50.44/18.23 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. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (52) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (53) QReductionProof (EQUIVALENT) 50.44/18.23 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 50.44/18.23 50.44/18.23 id_inc(x0) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (54) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (55) TransformationProof (EQUIVALENT) 50.44/18.23 By instantiating [LPAR04] the rule COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), x0) we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), z1),COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), z1)) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (56) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), z1) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (57) TransformationProof (EQUIVALENT) 50.44/18.23 By rewriting [LPAR04] the rule COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), z1) at position [0] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1),COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1)) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (58) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (59) TransformationProof (EQUIVALENT) 50.44/18.23 By instantiating [LPAR04] the rule COND_RAND2(true, neg(y0), x0) -> RAND(minus_nat(y0, s(01)), minus_int(x0, pos(s(01)))) we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), minus_int(z1, pos(s(01)))),COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), minus_int(z1, pos(s(01))))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (60) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), minus_int(z1, pos(s(01)))) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (61) TransformationProof (EQUIVALENT) 50.44/18.23 By rewriting [LPAR04] the rule COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(s(z0), s(01)), minus_int(z1, pos(s(01)))) at position [0] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))),COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01))))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (62) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (63) TransformationProof (EQUIVALENT) 50.44/18.23 By instantiating [LPAR04] the rule COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), x0) we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), z1),COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), z1)) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (64) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), z1) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (65) TransformationProof (EQUIVALENT) 50.44/18.23 By rewriting [LPAR04] the rule COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), z1) at position [0] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), z1),COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), z1)) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (66) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), z1) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (67) TransformationProof (EQUIVALENT) 50.44/18.23 By instantiating [LPAR04] the rule COND_RAND1(true, pos(y0), x0) -> RAND(minus_nat(s(01), y0), plus_int(pos(s(01)), x0)) we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), plus_int(pos(s(01)), z1)),COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), plus_int(pos(s(01)), z1))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (68) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), z1) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), plus_int(pos(s(01)), z1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (69) TransformationProof (EQUIVALENT) 50.44/18.23 By rewriting [LPAR04] the rule COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(s(01), s(z0)), plus_int(pos(s(01)), z1)) at position [0] we obtained the following new rules [LPAR04]: 50.44/18.23 50.44/18.23 (COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), plus_int(pos(s(01)), z1)),COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), plus_int(pos(s(01)), z1))) 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (70) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), z1) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), plus_int(pos(s(01)), z1)) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (71) MRRProof (EQUIVALENT) 50.44/18.23 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. 50.44/18.23 50.44/18.23 Strictly oriented dependency pairs: 50.44/18.23 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), z1) 50.44/18.23 COND_RAND2(true, neg(s(z0)), z1) -> RAND(minus_nat(z0, 01), minus_int(z1, pos(s(01)))) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), z1) 50.44/18.23 COND_RAND1(true, pos(s(z0)), z1) -> RAND(minus_nat(01, z0), plus_int(pos(s(01)), z1)) 50.44/18.23 50.44/18.23 Strictly oriented rules of the TRS R: 50.44/18.23 50.44/18.23 minus_nat(s(x), s(y)) -> minus_nat(x, y) 50.44/18.23 50.44/18.23 Used ordering: Polynomial interpretation [POLO]: 50.44/18.23 50.44/18.23 POL(01) = 0 50.44/18.23 POL(COND_RAND1(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 50.44/18.23 POL(COND_RAND2(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 50.44/18.23 POL(RAND(x_1, x_2)) = 2*x_1 + x_2 50.44/18.23 POL(minus_int(x_1, x_2)) = x_1 + x_2 50.44/18.23 POL(minus_nat(x_1, x_2)) = x_1 + x_2 50.44/18.23 POL(neg(x_1)) = x_1 50.44/18.23 POL(plus_int(x_1, x_2)) = x_1 + x_2 50.44/18.23 POL(plus_nat(x_1, x_2)) = x_1 + x_2 50.44/18.23 POL(pos(x_1)) = x_1 50.44/18.23 POL(s(x_1)) = 1 + x_1 50.44/18.23 POL(true) = 0 50.44/18.23 50.44/18.23 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (72) 50.44/18.23 Obligation: 50.44/18.23 Q DP problem: 50.44/18.23 The TRS P consists of the following rules: 50.44/18.23 50.44/18.23 RAND(neg(s(x0)), y1) -> COND_RAND2(true, neg(s(x0)), y1) 50.44/18.23 RAND(pos(s(x0)), y1) -> COND_RAND1(true, pos(s(x0)), y1) 50.44/18.23 50.44/18.23 The TRS R consists of the following rules: 50.44/18.23 50.44/18.23 minus_nat(s(x), 01) -> pos(s(x)) 50.44/18.23 plus_int(pos(x), neg(y)) -> minus_nat(x, y) 50.44/18.23 plus_int(pos(x), pos(y)) -> pos(plus_nat(x, y)) 50.44/18.23 plus_nat(01, x) -> x 50.44/18.23 plus_nat(s(x), y) -> s(plus_nat(x, y)) 50.44/18.23 minus_nat(01, s(y)) -> neg(s(y)) 50.44/18.23 minus_nat(01, 01) -> pos(01) 50.44/18.23 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 50.44/18.23 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 50.44/18.23 50.44/18.23 The set Q consists of the following terms: 50.44/18.23 50.44/18.23 plus_int(pos(x0), neg(x1)) 50.44/18.23 plus_int(neg(x0), pos(x1)) 50.44/18.23 plus_int(neg(x0), neg(x1)) 50.44/18.23 plus_int(pos(x0), pos(x1)) 50.44/18.23 plus_nat(01, x0) 50.44/18.23 plus_nat(s(x0), x1) 50.44/18.23 minus_nat(01, 01) 50.44/18.23 minus_nat(01, s(x0)) 50.44/18.23 minus_nat(s(x0), 01) 50.44/18.23 minus_nat(s(x0), s(x1)) 50.44/18.23 minus_int(pos(x0), pos(x1)) 50.44/18.23 minus_int(neg(x0), neg(x1)) 50.44/18.23 minus_int(neg(x0), pos(x1)) 50.44/18.23 minus_int(pos(x0), neg(x1)) 50.44/18.23 50.44/18.23 We have to consider all minimal (P,Q,R)-chains. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (73) DependencyGraphProof (EQUIVALENT) 50.44/18.23 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 50.44/18.23 ---------------------------------------- 50.44/18.23 50.44/18.23 (74) 50.44/18.23 TRUE 50.46/18.30 EOF