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