79.46/25.66 YES 79.46/25.69 proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs 79.46/25.69 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 79.46/25.69 79.46/25.69 79.46/25.69 Termination of the given ITRS could be proven: 79.46/25.69 79.46/25.69 (0) ITRS 79.46/25.69 (1) ITRStoIDPProof [EQUIVALENT, 0 ms] 79.46/25.69 (2) IDP 79.46/25.69 (3) UsableRulesProof [EQUIVALENT, 0 ms] 79.46/25.69 (4) IDP 79.46/25.69 (5) IDependencyGraphProof [EQUIVALENT, 0 ms] 79.46/25.69 (6) AND 79.46/25.69 (7) IDP 79.46/25.69 (8) UsableRulesProof [EQUIVALENT, 0 ms] 79.46/25.69 (9) IDP 79.46/25.69 (10) IDPNonInfProof [SOUND, 188 ms] 79.46/25.69 (11) IDP 79.46/25.69 (12) IDependencyGraphProof [EQUIVALENT, 0 ms] 79.46/25.69 (13) TRUE 79.46/25.69 (14) IDP 79.46/25.69 (15) UsableRulesProof [EQUIVALENT, 0 ms] 79.46/25.69 (16) IDP 79.46/25.69 (17) IDPNonInfProof [SOUND, 247 ms] 79.46/25.69 (18) IDP 79.46/25.69 (19) IDependencyGraphProof [EQUIVALENT, 0 ms] 79.46/25.69 (20) TRUE 79.46/25.69 (21) IDP 79.46/25.69 (22) UsableRulesProof [EQUIVALENT, 0 ms] 79.46/25.69 (23) IDP 79.46/25.69 (24) IDPtoQDPProof [SOUND, 4 ms] 79.46/25.69 (25) QDP 79.46/25.69 (26) QReductionProof [EQUIVALENT, 0 ms] 79.46/25.69 (27) QDP 79.46/25.69 (28) QDPOrderProof [EQUIVALENT, 25 ms] 79.46/25.69 (29) QDP 79.46/25.69 (30) PisEmptyProof [EQUIVALENT, 0 ms] 79.46/25.69 (31) YES 79.46/25.69 (32) IDP 79.46/25.69 (33) UsableRulesProof [EQUIVALENT, 0 ms] 79.46/25.69 (34) IDP 79.46/25.69 (35) IDPNonInfProof [SOUND, 47 ms] 79.46/25.69 (36) IDP 79.46/25.69 (37) IDependencyGraphProof [EQUIVALENT, 0 ms] 79.46/25.69 (38) TRUE 79.46/25.69 79.46/25.69 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (0) 79.46/25.69 Obligation: 79.46/25.69 ITRS problem: 79.46/25.69 79.46/25.69 The following function symbols are pre-defined: 79.46/25.69 <<< 79.46/25.69 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.69 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.69 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.69 / ~ Div: (Integer, Integer) -> Integer 79.46/25.69 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.69 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.69 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.69 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.69 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.69 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.69 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.69 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.69 + ~ Add: (Integer, Integer) -> Integer 79.46/25.69 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.69 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.69 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.69 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.69 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.69 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.69 >>> 79.46/25.69 79.46/25.69 The TRS R consists of the following rules: 79.46/25.69 primes(x) -> sieve(nats(2, x)) 79.46/25.69 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.69 Cond_nats(TRUE, x, y) -> nil 79.46/25.69 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.69 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.69 sieve(nil) -> nil 79.46/25.69 sieve(cons(x, ys)) -> cons(x, sieve(filter(x, ys))) 79.46/25.69 filter(x, nil) -> nil 79.46/25.69 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.69 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.69 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.69 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.69 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.69 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.69 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.69 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.69 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.69 The set Q consists of the following terms: 79.46/25.69 primes(x0) 79.46/25.69 nats(x0, x1) 79.46/25.69 Cond_nats(TRUE, x0, x1) 79.46/25.69 Cond_nats1(TRUE, x0, x1) 79.46/25.69 sieve(nil) 79.46/25.69 sieve(cons(x0, x1)) 79.46/25.69 filter(x0, nil) 79.46/25.69 filter(x0, cons(x1, x2)) 79.46/25.69 if(TRUE, x0, x1, x2) 79.46/25.69 if(FALSE, x0, x1, x2) 79.46/25.69 Cond_isdiv(TRUE, x0, 0) 79.46/25.69 isdiv(x0, x1) 79.46/25.69 Cond_isdiv1(TRUE, x0, x1) 79.46/25.69 Cond_isdiv2(TRUE, x0, x1) 79.46/25.69 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (1) ITRStoIDPProof (EQUIVALENT) 79.46/25.69 Added dependency pairs 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (2) 79.46/25.69 Obligation: 79.46/25.69 IDP problem: 79.46/25.69 The following function symbols are pre-defined: 79.46/25.69 <<< 79.46/25.69 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.69 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.69 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.69 / ~ Div: (Integer, Integer) -> Integer 79.46/25.69 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.69 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.69 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.69 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.69 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.69 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.69 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.69 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.69 + ~ Add: (Integer, Integer) -> Integer 79.46/25.69 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.69 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.69 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.69 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.69 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.69 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.69 >>> 79.46/25.69 79.46/25.69 79.46/25.69 The following domains are used: 79.46/25.69 Integer, Boolean 79.46/25.69 79.46/25.69 The ITRS R consists of the following rules: 79.46/25.69 primes(x) -> sieve(nats(2, x)) 79.46/25.69 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.69 Cond_nats(TRUE, x, y) -> nil 79.46/25.69 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.69 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.69 sieve(nil) -> nil 79.46/25.69 sieve(cons(x, ys)) -> cons(x, sieve(filter(x, ys))) 79.46/25.69 filter(x, nil) -> nil 79.46/25.69 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.69 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.69 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.69 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.69 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.69 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.69 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.69 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.69 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.69 79.46/25.69 The integer pair graph contains the following rules and edges: 79.46/25.69 (0): PRIMES(x[0]) -> SIEVE(nats(2, x[0])) 79.46/25.69 (1): PRIMES(x[1]) -> NATS(2, x[1]) 79.46/25.69 (2): NATS(x[2], y[2]) -> COND_NATS(x[2] > y[2], x[2], y[2]) 79.46/25.69 (3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3]) 79.46/25.69 (4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4]) 79.46/25.69 (5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.69 (6): SIEVE(cons(x[6], ys[6])) -> FILTER(x[6], ys[6]) 79.46/25.69 (7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.69 (8): FILTER(x[8], cons(y[8], zs[8])) -> ISDIV(x[8], y[8]) 79.46/25.69 (9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.69 (10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.69 (11): ISDIV(x[11], 0) -> COND_ISDIV(x[11] > 0, x[11], 0) 79.46/25.69 (12): ISDIV(x[12], y[12]) -> COND_ISDIV1(x[12] > y[12] && y[12] > 0, x[12], y[12]) 79.46/25.69 (13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13]) 79.46/25.69 (14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14]) 79.46/25.69 79.46/25.69 (0) -> (5), if (nats(2, x[0]) ->^* cons(x[5], ys[5])) 79.46/25.69 (0) -> (6), if (nats(2, x[0]) ->^* cons(x[6], ys[6])) 79.46/25.69 (1) -> (2), if (2 ->^* x[2] & x[1] ->^* y[2]) 79.46/25.69 (1) -> (3), if (2 ->^* x[3] & x[1] ->^* y[3]) 79.46/25.69 (3) -> (4), if (y[3] >= x[3] & x[3] ->^* x[4] & y[3] ->^* y[4]) 79.46/25.69 (4) -> (2), if (x[4] + 1 ->^* x[2] & y[4] ->^* y[2]) 79.46/25.69 (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3]) 79.46/25.69 (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]')) 79.46/25.69 (5) -> (6), if (filter(x[5], ys[5]) ->^* cons(x[6], ys[6])) 79.46/25.69 (6) -> (7), if (x[6] ->^* x[7] & ys[6] ->^* cons(y[7], zs[7])) 79.46/25.69 (6) -> (8), if (x[6] ->^* x[8] & ys[6] ->^* cons(y[8], zs[8])) 79.46/25.69 (7) -> (9), if (isdiv(x[7], y[7]) & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9]) 79.46/25.69 (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10]) 79.46/25.69 (8) -> (11), if (x[8] ->^* x[11] & y[8] ->^* 0) 79.46/25.69 (8) -> (12), if (x[8] ->^* x[12] & y[8] ->^* y[12]) 79.46/25.69 (8) -> (13), if (x[8] ->^* x[13] & y[8] ->^* y[13]) 79.46/25.69 (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7])) 79.46/25.69 (9) -> (8), if (x[9] ->^* x[8] & zs[9] ->^* cons(y[8], zs[8])) 79.46/25.69 (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7])) 79.46/25.69 (10) -> (8), if (x[10] ->^* x[8] & zs[10] ->^* cons(y[8], zs[8])) 79.46/25.69 (13) -> (14), if (y[13] >= x[13] && x[13] > 0 & x[13] ->^* x[14] & y[13] ->^* y[14]) 79.46/25.69 (14) -> (11), if (x[14] ->^* x[11] & y[14] - x[14] ->^* 0) 79.46/25.69 (14) -> (12), if (x[14] ->^* x[12] & y[14] - x[14] ->^* y[12]) 79.46/25.69 (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13]) 79.46/25.69 79.46/25.69 The set Q consists of the following terms: 79.46/25.69 primes(x0) 79.46/25.69 nats(x0, x1) 79.46/25.69 Cond_nats(TRUE, x0, x1) 79.46/25.69 Cond_nats1(TRUE, x0, x1) 79.46/25.69 sieve(nil) 79.46/25.69 sieve(cons(x0, x1)) 79.46/25.69 filter(x0, nil) 79.46/25.69 filter(x0, cons(x1, x2)) 79.46/25.69 if(TRUE, x0, x1, x2) 79.46/25.69 if(FALSE, x0, x1, x2) 79.46/25.69 Cond_isdiv(TRUE, x0, 0) 79.46/25.69 isdiv(x0, x1) 79.46/25.69 Cond_isdiv1(TRUE, x0, x1) 79.46/25.69 Cond_isdiv2(TRUE, x0, x1) 79.46/25.69 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (3) UsableRulesProof (EQUIVALENT) 79.46/25.69 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. 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (4) 79.46/25.69 Obligation: 79.46/25.69 IDP problem: 79.46/25.69 The following function symbols are pre-defined: 79.46/25.69 <<< 79.46/25.69 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.69 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.69 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.69 / ~ Div: (Integer, Integer) -> Integer 79.46/25.69 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.69 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.69 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.69 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.69 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.69 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.69 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.69 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.69 + ~ Add: (Integer, Integer) -> Integer 79.46/25.69 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.69 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.69 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.69 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.69 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.69 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.69 >>> 79.46/25.69 79.46/25.69 79.46/25.69 The following domains are used: 79.46/25.69 Integer, Boolean 79.46/25.69 79.46/25.69 The ITRS R consists of the following rules: 79.46/25.69 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.69 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.69 filter(x, nil) -> nil 79.46/25.69 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.69 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.69 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.69 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.69 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.69 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.69 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.69 Cond_nats(TRUE, x, y) -> nil 79.46/25.69 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.69 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.69 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.69 79.46/25.69 The integer pair graph contains the following rules and edges: 79.46/25.69 (0): PRIMES(x[0]) -> SIEVE(nats(2, x[0])) 79.46/25.69 (1): PRIMES(x[1]) -> NATS(2, x[1]) 79.46/25.69 (2): NATS(x[2], y[2]) -> COND_NATS(x[2] > y[2], x[2], y[2]) 79.46/25.69 (3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3]) 79.46/25.69 (4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4]) 79.46/25.69 (5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.69 (6): SIEVE(cons(x[6], ys[6])) -> FILTER(x[6], ys[6]) 79.46/25.69 (7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.69 (8): FILTER(x[8], cons(y[8], zs[8])) -> ISDIV(x[8], y[8]) 79.46/25.69 (9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.69 (10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.69 (11): ISDIV(x[11], 0) -> COND_ISDIV(x[11] > 0, x[11], 0) 79.46/25.69 (12): ISDIV(x[12], y[12]) -> COND_ISDIV1(x[12] > y[12] && y[12] > 0, x[12], y[12]) 79.46/25.69 (13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13]) 79.46/25.69 (14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14]) 79.46/25.69 79.46/25.69 (0) -> (5), if (nats(2, x[0]) ->^* cons(x[5], ys[5])) 79.46/25.69 (0) -> (6), if (nats(2, x[0]) ->^* cons(x[6], ys[6])) 79.46/25.69 (1) -> (2), if (2 ->^* x[2] & x[1] ->^* y[2]) 79.46/25.69 (1) -> (3), if (2 ->^* x[3] & x[1] ->^* y[3]) 79.46/25.69 (3) -> (4), if (y[3] >= x[3] & x[3] ->^* x[4] & y[3] ->^* y[4]) 79.46/25.69 (4) -> (2), if (x[4] + 1 ->^* x[2] & y[4] ->^* y[2]) 79.46/25.69 (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3]) 79.46/25.69 (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]')) 79.46/25.69 (5) -> (6), if (filter(x[5], ys[5]) ->^* cons(x[6], ys[6])) 79.46/25.69 (6) -> (7), if (x[6] ->^* x[7] & ys[6] ->^* cons(y[7], zs[7])) 79.46/25.69 (6) -> (8), if (x[6] ->^* x[8] & ys[6] ->^* cons(y[8], zs[8])) 79.46/25.69 (7) -> (9), if (isdiv(x[7], y[7]) & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9]) 79.46/25.69 (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10]) 79.46/25.69 (8) -> (11), if (x[8] ->^* x[11] & y[8] ->^* 0) 79.46/25.69 (8) -> (12), if (x[8] ->^* x[12] & y[8] ->^* y[12]) 79.46/25.69 (8) -> (13), if (x[8] ->^* x[13] & y[8] ->^* y[13]) 79.46/25.69 (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7])) 79.46/25.69 (9) -> (8), if (x[9] ->^* x[8] & zs[9] ->^* cons(y[8], zs[8])) 79.46/25.69 (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7])) 79.46/25.69 (10) -> (8), if (x[10] ->^* x[8] & zs[10] ->^* cons(y[8], zs[8])) 79.46/25.69 (13) -> (14), if (y[13] >= x[13] && x[13] > 0 & x[13] ->^* x[14] & y[13] ->^* y[14]) 79.46/25.69 (14) -> (11), if (x[14] ->^* x[11] & y[14] - x[14] ->^* 0) 79.46/25.69 (14) -> (12), if (x[14] ->^* x[12] & y[14] - x[14] ->^* y[12]) 79.46/25.69 (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13]) 79.46/25.69 79.46/25.69 The set Q consists of the following terms: 79.46/25.69 primes(x0) 79.46/25.69 nats(x0, x1) 79.46/25.69 Cond_nats(TRUE, x0, x1) 79.46/25.69 Cond_nats1(TRUE, x0, x1) 79.46/25.69 sieve(nil) 79.46/25.69 sieve(cons(x0, x1)) 79.46/25.69 filter(x0, nil) 79.46/25.69 filter(x0, cons(x1, x2)) 79.46/25.69 if(TRUE, x0, x1, x2) 79.46/25.69 if(FALSE, x0, x1, x2) 79.46/25.69 Cond_isdiv(TRUE, x0, 0) 79.46/25.69 isdiv(x0, x1) 79.46/25.69 Cond_isdiv1(TRUE, x0, x1) 79.46/25.69 Cond_isdiv2(TRUE, x0, x1) 79.46/25.69 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (5) IDependencyGraphProof (EQUIVALENT) 79.46/25.69 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 7 less nodes. 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (6) 79.46/25.69 Complex Obligation (AND) 79.46/25.69 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (7) 79.46/25.69 Obligation: 79.46/25.69 IDP problem: 79.46/25.69 The following function symbols are pre-defined: 79.46/25.69 <<< 79.46/25.69 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.69 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.69 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.69 / ~ Div: (Integer, Integer) -> Integer 79.46/25.69 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.69 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.69 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.69 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.69 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.69 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.69 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.69 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.69 + ~ Add: (Integer, Integer) -> Integer 79.46/25.69 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.69 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.69 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.69 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.69 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.69 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.69 >>> 79.46/25.69 79.46/25.69 79.46/25.69 The following domains are used: 79.46/25.69 Integer, Boolean 79.46/25.69 79.46/25.69 The ITRS R consists of the following rules: 79.46/25.69 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.69 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.69 filter(x, nil) -> nil 79.46/25.69 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.69 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.69 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.69 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.69 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.69 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.69 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.69 Cond_nats(TRUE, x, y) -> nil 79.46/25.69 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.69 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.69 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.69 79.46/25.69 The integer pair graph contains the following rules and edges: 79.46/25.69 (14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14]) 79.46/25.69 (13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13]) 79.46/25.69 79.46/25.69 (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13]) 79.46/25.69 (13) -> (14), if (y[13] >= x[13] && x[13] > 0 & x[13] ->^* x[14] & y[13] ->^* y[14]) 79.46/25.69 79.46/25.69 The set Q consists of the following terms: 79.46/25.69 primes(x0) 79.46/25.69 nats(x0, x1) 79.46/25.69 Cond_nats(TRUE, x0, x1) 79.46/25.69 Cond_nats1(TRUE, x0, x1) 79.46/25.69 sieve(nil) 79.46/25.69 sieve(cons(x0, x1)) 79.46/25.69 filter(x0, nil) 79.46/25.69 filter(x0, cons(x1, x2)) 79.46/25.69 if(TRUE, x0, x1, x2) 79.46/25.69 if(FALSE, x0, x1, x2) 79.46/25.69 Cond_isdiv(TRUE, x0, 0) 79.46/25.69 isdiv(x0, x1) 79.46/25.69 Cond_isdiv1(TRUE, x0, x1) 79.46/25.69 Cond_isdiv2(TRUE, x0, x1) 79.46/25.69 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (8) UsableRulesProof (EQUIVALENT) 79.46/25.69 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. 79.46/25.69 ---------------------------------------- 79.46/25.69 79.46/25.69 (9) 79.46/25.69 Obligation: 79.46/25.69 IDP problem: 79.46/25.69 The following function symbols are pre-defined: 79.46/25.69 <<< 79.46/25.69 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.69 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.69 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.69 / ~ Div: (Integer, Integer) -> Integer 79.46/25.69 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.69 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.69 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.69 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.69 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.69 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.69 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.69 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.69 + ~ Add: (Integer, Integer) -> Integer 79.46/25.69 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.69 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.69 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.69 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.69 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.69 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.69 >>> 79.46/25.69 79.46/25.69 79.46/25.69 The following domains are used: 79.46/25.69 Integer, Boolean 79.46/25.69 79.46/25.69 R is empty. 79.46/25.69 79.46/25.69 The integer pair graph contains the following rules and edges: 79.46/25.71 (14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14]) 79.46/25.71 (13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13]) 79.46/25.71 79.46/25.71 (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13]) 79.46/25.71 (13) -> (14), if (y[13] >= x[13] && x[13] > 0 & x[13] ->^* x[14] & y[13] ->^* y[14]) 79.46/25.71 79.46/25.71 The set Q consists of the following terms: 79.46/25.71 primes(x0) 79.46/25.71 nats(x0, x1) 79.46/25.71 Cond_nats(TRUE, x0, x1) 79.46/25.71 Cond_nats1(TRUE, x0, x1) 79.46/25.71 sieve(nil) 79.46/25.71 sieve(cons(x0, x1)) 79.46/25.71 filter(x0, nil) 79.46/25.71 filter(x0, cons(x1, x2)) 79.46/25.71 if(TRUE, x0, x1, x2) 79.46/25.71 if(FALSE, x0, x1, x2) 79.46/25.71 Cond_isdiv(TRUE, x0, 0) 79.46/25.71 isdiv(x0, x1) 79.46/25.71 Cond_isdiv1(TRUE, x0, x1) 79.46/25.71 Cond_isdiv2(TRUE, x0, x1) 79.46/25.71 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (10) IDPNonInfProof (SOUND) 79.46/25.71 Used the following options for this NonInfProof: 79.46/25.71 79.46/25.71 IDPGPoloSolver: 79.46/25.71 Range: [(-1,2)] 79.46/25.71 IsNat: false 79.46/25.71 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@ea73c8 79.46/25.71 Constraint Generator: NonInfConstraintGenerator: 79.46/25.71 PathGenerator: MetricPathGenerator: 79.46/25.71 Max Left Steps: 1 79.46/25.71 Max Right Steps: 1 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 The constraints were generated the following way: 79.46/25.71 79.46/25.71 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 79.46/25.71 79.46/25.71 Note that final constraints are written in bold face. 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 For Pair COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])) the following chains were created: 79.46/25.71 *We consider the chain ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]), COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])), ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) which results in the following constraint: 79.46/25.71 79.46/25.71 (1) (&&(>=(y[13], x[13]), >(x[13], 0))=TRUE & x[13]=x[14] & y[13]=y[14] & x[14]=x[13]1 & -(y[14], x[14])=y[13]1 ==> COND_ISDIV2(TRUE, x[14], y[14])_>=_NonInfC & COND_ISDIV2(TRUE, x[14], y[14])_>=_ISDIV(x[14], -(y[14], x[14])) & (U^Increasing(ISDIV(x[14], -(y[14], x[14]))), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (1) using rules (III), (IV), (IDP_BOOLEAN) which results in the following new constraint: 79.46/25.71 79.46/25.71 (2) (>=(y[13], x[13])=TRUE & >(x[13], 0)=TRUE ==> COND_ISDIV2(TRUE, x[13], y[13])_>=_NonInfC & COND_ISDIV2(TRUE, x[13], y[13])_>=_ISDIV(x[13], -(y[13], x[13])) & (U^Increasing(ISDIV(x[14], -(y[14], x[14]))), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (3) (y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(ISDIV(x[14], -(y[14], x[14]))), >=) & [(-1)bni_13 + (-1)Bound*bni_13] + [bni_13]y[13] + [(-1)bni_13]x[13] >= 0 & [(-1)bso_14] + x[13] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (4) (y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(ISDIV(x[14], -(y[14], x[14]))), >=) & [(-1)bni_13 + (-1)Bound*bni_13] + [bni_13]y[13] + [(-1)bni_13]x[13] >= 0 & [(-1)bso_14] + x[13] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (5) (y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(ISDIV(x[14], -(y[14], x[14]))), >=) & [(-1)bni_13 + (-1)Bound*bni_13] + [bni_13]y[13] + [(-1)bni_13]x[13] >= 0 & [(-1)bso_14] + x[13] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 For Pair ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) the following chains were created: 79.46/25.71 *We consider the chain ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]), COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])) which results in the following constraint: 79.46/25.71 79.46/25.71 (1) (&&(>=(y[13], x[13]), >(x[13], 0))=TRUE & x[13]=x[14] & y[13]=y[14] ==> ISDIV(x[13], y[13])_>=_NonInfC & ISDIV(x[13], y[13])_>=_COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) & (U^Increasing(COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (1) using rules (IV), (IDP_BOOLEAN) which results in the following new constraint: 79.46/25.71 79.46/25.71 (2) (>=(y[13], x[13])=TRUE & >(x[13], 0)=TRUE ==> ISDIV(x[13], y[13])_>=_NonInfC & ISDIV(x[13], y[13])_>=_COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) & (U^Increasing(COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (3) (y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])), >=) & [(-1)bni_15 + (-1)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [(-1)bso_16] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (4) (y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])), >=) & [(-1)bni_15 + (-1)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [(-1)bso_16] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (5) (y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])), >=) & [(-1)bni_15 + (-1)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [(-1)bso_16] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 To summarize, we get the following constraints P__>=_ for the following pairs. 79.46/25.71 79.46/25.71 *COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])) 79.46/25.71 79.46/25.71 *(y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(ISDIV(x[14], -(y[14], x[14]))), >=) & [(-1)bni_13 + (-1)Bound*bni_13] + [bni_13]y[13] + [(-1)bni_13]x[13] >= 0 & [(-1)bso_14] + x[13] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 *ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) 79.46/25.71 79.46/25.71 *(y[13] + [-1]x[13] >= 0 & x[13] + [-1] >= 0 ==> (U^Increasing(COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])), >=) & [(-1)bni_15 + (-1)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [(-1)bso_16] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. 79.46/25.71 79.46/25.71 Using the following integer polynomial ordering the resulting constraints can be solved 79.46/25.71 79.46/25.71 Polynomial interpretation over integers[POLO]: 79.46/25.71 79.46/25.71 POL(TRUE) = 0 79.46/25.71 POL(FALSE) = 0 79.46/25.71 POL(COND_ISDIV2(x_1, x_2, x_3)) = [-1] + x_3 + [-1]x_2 + [-1]x_1 79.46/25.71 POL(ISDIV(x_1, x_2)) = [-1] + x_2 + [-1]x_1 79.46/25.71 POL(-(x_1, x_2)) = x_1 + [-1]x_2 79.46/25.71 POL(&&(x_1, x_2)) = 0 79.46/25.71 POL(>=(x_1, x_2)) = [-1] 79.46/25.71 POL(>(x_1, x_2)) = [-1] 79.46/25.71 POL(0) = 0 79.46/25.71 79.46/25.71 79.46/25.71 The following pairs are in P_>: 79.46/25.71 79.46/25.71 79.46/25.71 COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])) 79.46/25.71 79.46/25.71 79.46/25.71 The following pairs are in P_bound: 79.46/25.71 79.46/25.71 79.46/25.71 COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])) 79.46/25.71 ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) 79.46/25.71 79.46/25.71 79.46/25.71 The following pairs are in P_>=: 79.46/25.71 79.46/25.71 79.46/25.71 ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13]) 79.46/25.71 79.46/25.71 79.46/25.71 At least the following rules have been oriented under context sensitive arithmetic replacement: 79.46/25.71 79.46/25.71 TRUE^1 -> &&(TRUE, TRUE)^1 79.46/25.71 FALSE^1 -> &&(TRUE, FALSE)^1 79.46/25.71 &&(FALSE, TRUE)^1 <-> FALSE^1 79.46/25.71 &&(FALSE, FALSE)^1 <-> FALSE^1 79.46/25.71 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (11) 79.46/25.71 Obligation: 79.46/25.71 IDP problem: 79.46/25.71 The following function symbols are pre-defined: 79.46/25.71 <<< 79.46/25.71 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.71 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.71 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.71 / ~ Div: (Integer, Integer) -> Integer 79.46/25.71 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.71 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.71 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.71 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.71 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.71 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.71 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.71 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.71 + ~ Add: (Integer, Integer) -> Integer 79.46/25.71 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.71 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.71 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.71 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.71 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.71 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.71 >>> 79.46/25.71 79.46/25.71 79.46/25.71 The following domains are used: 79.46/25.71 Boolean, Integer 79.46/25.71 79.46/25.71 R is empty. 79.46/25.71 79.46/25.71 The integer pair graph contains the following rules and edges: 79.46/25.71 (13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13]) 79.46/25.71 79.46/25.71 79.46/25.71 The set Q consists of the following terms: 79.46/25.71 primes(x0) 79.46/25.71 nats(x0, x1) 79.46/25.71 Cond_nats(TRUE, x0, x1) 79.46/25.71 Cond_nats1(TRUE, x0, x1) 79.46/25.71 sieve(nil) 79.46/25.71 sieve(cons(x0, x1)) 79.46/25.71 filter(x0, nil) 79.46/25.71 filter(x0, cons(x1, x2)) 79.46/25.71 if(TRUE, x0, x1, x2) 79.46/25.71 if(FALSE, x0, x1, x2) 79.46/25.71 Cond_isdiv(TRUE, x0, 0) 79.46/25.71 isdiv(x0, x1) 79.46/25.71 Cond_isdiv1(TRUE, x0, x1) 79.46/25.71 Cond_isdiv2(TRUE, x0, x1) 79.46/25.71 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (12) IDependencyGraphProof (EQUIVALENT) 79.46/25.71 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (13) 79.46/25.71 TRUE 79.46/25.71 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (14) 79.46/25.71 Obligation: 79.46/25.71 IDP problem: 79.46/25.71 The following function symbols are pre-defined: 79.46/25.71 <<< 79.46/25.71 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.71 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.71 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.71 / ~ Div: (Integer, Integer) -> Integer 79.46/25.71 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.71 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.71 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.71 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.71 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.71 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.71 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.71 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.71 + ~ Add: (Integer, Integer) -> Integer 79.46/25.71 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.71 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.71 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.71 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.71 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.71 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.71 >>> 79.46/25.71 79.46/25.71 79.46/25.71 The following domains are used: 79.46/25.71 Integer, Boolean 79.46/25.71 79.46/25.71 The ITRS R consists of the following rules: 79.46/25.71 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.71 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.71 filter(x, nil) -> nil 79.46/25.71 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.71 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.71 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.71 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.71 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.71 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.71 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.71 Cond_nats(TRUE, x, y) -> nil 79.46/25.71 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.71 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.71 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.71 79.46/25.71 The integer pair graph contains the following rules and edges: 79.46/25.71 (10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.71 (9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.71 (7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.71 79.46/25.71 (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7])) 79.46/25.71 (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7])) 79.46/25.71 (7) -> (9), if (isdiv(x[7], y[7]) & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9]) 79.46/25.71 (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10]) 79.46/25.71 79.46/25.71 The set Q consists of the following terms: 79.46/25.71 primes(x0) 79.46/25.71 nats(x0, x1) 79.46/25.71 Cond_nats(TRUE, x0, x1) 79.46/25.71 Cond_nats1(TRUE, x0, x1) 79.46/25.71 sieve(nil) 79.46/25.71 sieve(cons(x0, x1)) 79.46/25.71 filter(x0, nil) 79.46/25.71 filter(x0, cons(x1, x2)) 79.46/25.71 if(TRUE, x0, x1, x2) 79.46/25.71 if(FALSE, x0, x1, x2) 79.46/25.71 Cond_isdiv(TRUE, x0, 0) 79.46/25.71 isdiv(x0, x1) 79.46/25.71 Cond_isdiv1(TRUE, x0, x1) 79.46/25.71 Cond_isdiv2(TRUE, x0, x1) 79.46/25.71 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (15) UsableRulesProof (EQUIVALENT) 79.46/25.71 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. 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (16) 79.46/25.71 Obligation: 79.46/25.71 IDP problem: 79.46/25.71 The following function symbols are pre-defined: 79.46/25.71 <<< 79.46/25.71 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.71 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.71 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.71 / ~ Div: (Integer, Integer) -> Integer 79.46/25.71 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.71 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.71 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.71 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.71 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.71 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.71 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.71 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.71 + ~ Add: (Integer, Integer) -> Integer 79.46/25.71 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.71 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.71 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.71 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.71 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.71 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.71 >>> 79.46/25.71 79.46/25.71 79.46/25.71 The following domains are used: 79.46/25.71 Integer, Boolean 79.46/25.71 79.46/25.71 The ITRS R consists of the following rules: 79.46/25.71 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.71 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.71 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.71 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.71 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.71 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.71 79.46/25.71 The integer pair graph contains the following rules and edges: 79.46/25.71 (10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.71 (9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.71 (7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.71 79.46/25.71 (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7])) 79.46/25.71 (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7])) 79.46/25.71 (7) -> (9), if (isdiv(x[7], y[7]) & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9]) 79.46/25.71 (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10]) 79.46/25.71 79.46/25.71 The set Q consists of the following terms: 79.46/25.71 primes(x0) 79.46/25.71 nats(x0, x1) 79.46/25.71 Cond_nats(TRUE, x0, x1) 79.46/25.71 Cond_nats1(TRUE, x0, x1) 79.46/25.71 sieve(nil) 79.46/25.71 sieve(cons(x0, x1)) 79.46/25.71 filter(x0, nil) 79.46/25.71 filter(x0, cons(x1, x2)) 79.46/25.71 if(TRUE, x0, x1, x2) 79.46/25.71 if(FALSE, x0, x1, x2) 79.46/25.71 Cond_isdiv(TRUE, x0, 0) 79.46/25.71 isdiv(x0, x1) 79.46/25.71 Cond_isdiv1(TRUE, x0, x1) 79.46/25.71 Cond_isdiv2(TRUE, x0, x1) 79.46/25.71 79.46/25.71 ---------------------------------------- 79.46/25.71 79.46/25.71 (17) IDPNonInfProof (SOUND) 79.46/25.71 Used the following options for this NonInfProof: 79.46/25.71 79.46/25.71 IDPGPoloSolver: 79.46/25.71 Range: [(-1,2)] 79.46/25.71 IsNat: true 79.46/25.71 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@4d9bd2f0 79.46/25.71 Constraint Generator: NonInfConstraintGenerator: 79.46/25.71 PathGenerator: MetricPathGenerator: 79.46/25.71 Max Left Steps: 1 79.46/25.71 Max Right Steps: 1 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 The constraints were generated the following way: 79.46/25.71 79.46/25.71 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 79.46/25.71 79.46/25.71 Note that final constraints are written in bold face. 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 For Pair IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) the following chains were created: 79.46/25.71 *We consider the chain IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]), FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) which results in the following constraint: 79.46/25.71 79.46/25.71 (1) (x[10]=x[7] & zs[10]=cons(y[7], zs[7]) ==> IF(FALSE, x[10], y[10], zs[10])_>=_NonInfC & IF(FALSE, x[10], y[10], zs[10])_>=_FILTER(x[10], zs[10]) & (U^Increasing(FILTER(x[10], zs[10])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.71 79.46/25.71 (2) (IF(FALSE, x[10], y[10], cons(y[7], zs[7]))_>=_NonInfC & IF(FALSE, x[10], y[10], cons(y[7], zs[7]))_>=_FILTER(x[10], cons(y[7], zs[7])) & (U^Increasing(FILTER(x[10], zs[10])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (3) ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & [1 + (-1)bso_28] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (4) ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & [1 + (-1)bso_28] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (5) ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & [1 + (-1)bso_28] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (6) ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & 0 >= 0 & [1 + (-1)bso_28] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 For Pair IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) the following chains were created: 79.46/25.71 *We consider the chain IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]), FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) which results in the following constraint: 79.46/25.71 79.46/25.71 (1) (x[9]=x[7] & zs[9]=cons(y[7], zs[7]) ==> IF(TRUE, x[9], y[9], zs[9])_>=_NonInfC & IF(TRUE, x[9], y[9], zs[9])_>=_FILTER(x[9], zs[9]) & (U^Increasing(FILTER(x[9], zs[9])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.71 79.46/25.71 (2) (IF(TRUE, x[9], y[9], cons(y[7], zs[7]))_>=_NonInfC & IF(TRUE, x[9], y[9], cons(y[7], zs[7]))_>=_FILTER(x[9], cons(y[7], zs[7])) & (U^Increasing(FILTER(x[9], zs[9])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (3) ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & [1 + (-1)bso_30] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (4) ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & [1 + (-1)bso_30] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (5) ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & [1 + (-1)bso_30] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (6) ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & 0 >= 0 & [1 + (-1)bso_30] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 For Pair FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) the following chains were created: 79.46/25.71 *We consider the chain IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]), FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]), IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) which results in the following constraint: 79.46/25.71 79.46/25.71 (1) (x[9]=x[7] & zs[9]=cons(y[7], zs[7]) & isdiv(x[7], y[7])=TRUE & x[7]=x[9]1 & y[7]=y[9]1 & zs[7]=zs[9]1 ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.71 79.46/25.71 (2) (isdiv(x[7], y[7])=TRUE ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on isdiv(x[7], y[7])=TRUE which results in the following new constraints: 79.46/25.71 79.46/25.71 (3) (Cond_isdiv(>(x0, 0), x0, 0)=TRUE ==> FILTER(x0, cons(0, zs[7]))_>=_NonInfC & FILTER(x0, cons(0, zs[7]))_>=_IF(isdiv(x0, 0), x0, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 (4) (Cond_isdiv1(&&(>(x2, x1), >(x1, 0)), x2, x1)=TRUE ==> FILTER(x2, cons(x1, zs[7]))_>=_NonInfC & FILTER(x2, cons(x1, zs[7]))_>=_IF(isdiv(x2, x1), x2, x1, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 (5) (Cond_isdiv2(&&(>=(x3, x4), >(x4, 0)), x4, x3)=TRUE ==> FILTER(x4, cons(x3, zs[7]))_>=_NonInfC & FILTER(x4, cons(x3, zs[7]))_>=_IF(isdiv(x4, x3), x4, x3, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (3) using rules (III), (VII) which results in the following new constraint: 79.46/25.71 79.46/25.71 (6) (Cond_isdiv(>(x0, 0), x0, 0)=TRUE ==> FILTER(x0, cons(0, zs[7]))_>=_NonInfC & FILTER(x0, cons(0, zs[7]))_>=_IF(isdiv(x0, 0), x0, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 79.46/25.71 79.46/25.71 (7) (Cond_isdiv1(&&(>(x2, x1), >(x1, 0)), x2, x1)=TRUE ==> FILTER(x2, cons(x1, zs[7]))_>=_NonInfC & FILTER(x2, cons(x1, zs[7]))_>=_IF(isdiv(x2, x1), x2, x1, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 79.46/25.71 79.46/25.71 (8) (Cond_isdiv2(&&(>=(x3, x4), >(x4, 0)), x4, x3)=TRUE ==> FILTER(x4, cons(x3, zs[7]))_>=_NonInfC & FILTER(x4, cons(x3, zs[7]))_>=_IF(isdiv(x4, x3), x4, x3, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (9) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (10) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x1 >= 0 & [3 + (-1)bso_32] + [6]x1 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (11) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x3 >= 0 & [3 + (-1)bso_32] + [6]x3 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (12) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x1 >= 0 & [3 + (-1)bso_32] + [6]x1 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (13) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x3 >= 0 & [3 + (-1)bso_32] + [6]x3 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.71 79.46/25.71 (14) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (15) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x1 >= 0 & [3 + (-1)bso_32] + [6]x1 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (16) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x3 >= 0 & [3 + (-1)bso_32] + [6]x3 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.71 79.46/25.71 (17) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.71 79.46/25.71 (18) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.71 79.46/25.71 (19) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (20) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 *We consider the chain IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]), FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]), IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) which results in the following constraint: 79.46/25.71 79.46/25.71 (1) (x[10]=x[7] & zs[10]=cons(y[7], zs[7]) & isdiv(x[7], y[7])=TRUE & x[7]=x[9] & y[7]=y[9] & zs[7]=zs[9] ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.71 79.46/25.71 (2) (isdiv(x[7], y[7])=TRUE ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on isdiv(x[7], y[7])=TRUE which results in the following new constraints: 79.46/25.71 79.46/25.71 (3) (Cond_isdiv(>(x9, 0), x9, 0)=TRUE ==> FILTER(x9, cons(0, zs[7]))_>=_NonInfC & FILTER(x9, cons(0, zs[7]))_>=_IF(isdiv(x9, 0), x9, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 (4) (Cond_isdiv1(&&(>(x11, x10), >(x10, 0)), x11, x10)=TRUE ==> FILTER(x11, cons(x10, zs[7]))_>=_NonInfC & FILTER(x11, cons(x10, zs[7]))_>=_IF(isdiv(x11, x10), x11, x10, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 (5) (Cond_isdiv2(&&(>=(x12, x13), >(x13, 0)), x13, x12)=TRUE ==> FILTER(x13, cons(x12, zs[7]))_>=_NonInfC & FILTER(x13, cons(x12, zs[7]))_>=_IF(isdiv(x13, x12), x13, x12, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (3) using rules (III), (VII) which results in the following new constraint: 79.46/25.71 79.46/25.71 (6) (Cond_isdiv(>(x9, 0), x9, 0)=TRUE ==> FILTER(x9, cons(0, zs[7]))_>=_NonInfC & FILTER(x9, cons(0, zs[7]))_>=_IF(isdiv(x9, 0), x9, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 79.46/25.71 79.46/25.71 (7) (Cond_isdiv1(&&(>(x11, x10), >(x10, 0)), x11, x10)=TRUE ==> FILTER(x11, cons(x10, zs[7]))_>=_NonInfC & FILTER(x11, cons(x10, zs[7]))_>=_IF(isdiv(x11, x10), x11, x10, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 79.46/25.71 79.46/25.71 (8) (Cond_isdiv2(&&(>=(x12, x13), >(x13, 0)), x13, x12)=TRUE ==> FILTER(x13, cons(x12, zs[7]))_>=_NonInfC & FILTER(x13, cons(x12, zs[7]))_>=_IF(isdiv(x13, x12), x13, x12, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (9) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (10) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x10 >= 0 & [3 + (-1)bso_32] + [6]x10 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.71 79.46/25.71 (11) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x12 >= 0 & [3 + (-1)bso_32] + [6]x12 >= 0) 79.46/25.71 79.46/25.71 79.46/25.71 79.46/25.71 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (12) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x10 >= 0 & [3 + (-1)bso_32] + [6]x10 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (13) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x12 >= 0 & [3 + (-1)bso_32] + [6]x12 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (14) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (15) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x10 >= 0 & [3 + (-1)bso_32] + [6]x10 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (16) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x12 >= 0 & [3 + (-1)bso_32] + [6]x12 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (17) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.72 79.46/25.72 (18) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.72 79.46/25.72 (19) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (20) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 *We consider the chain IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]), FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]), IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) which results in the following constraint: 79.46/25.72 79.46/25.72 (1) (x[9]=x[7] & zs[9]=cons(y[7], zs[7]) & isdiv(x[7], y[7])=FALSE & x[7]=x[10] & y[7]=y[10] & zs[7]=zs[10] ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.72 79.46/25.72 (2) (isdiv(x[7], y[7])=FALSE ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on isdiv(x[7], y[7])=FALSE which results in the following new constraints: 79.46/25.72 79.46/25.72 (3) (Cond_isdiv(>(x18, 0), x18, 0)=FALSE ==> FILTER(x18, cons(0, zs[7]))_>=_NonInfC & FILTER(x18, cons(0, zs[7]))_>=_IF(isdiv(x18, 0), x18, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 (4) (Cond_isdiv1(&&(>(x20, x19), >(x19, 0)), x20, x19)=FALSE ==> FILTER(x20, cons(x19, zs[7]))_>=_NonInfC & FILTER(x20, cons(x19, zs[7]))_>=_IF(isdiv(x20, x19), x20, x19, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 (5) (Cond_isdiv2(&&(>=(x21, x22), >(x22, 0)), x22, x21)=FALSE ==> FILTER(x22, cons(x21, zs[7]))_>=_NonInfC & FILTER(x22, cons(x21, zs[7]))_>=_IF(isdiv(x22, x21), x22, x21, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (3) using rules (III), (VII) which results in the following new constraint: 79.46/25.72 79.46/25.72 (6) (Cond_isdiv(>(x18, 0), x18, 0)=FALSE ==> FILTER(x18, cons(0, zs[7]))_>=_NonInfC & FILTER(x18, cons(0, zs[7]))_>=_IF(isdiv(x18, 0), x18, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 79.46/25.72 79.46/25.72 (7) (Cond_isdiv1(&&(>(x20, x19), >(x19, 0)), x20, x19)=FALSE ==> FILTER(x20, cons(x19, zs[7]))_>=_NonInfC & FILTER(x20, cons(x19, zs[7]))_>=_IF(isdiv(x20, x19), x20, x19, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 79.46/25.72 79.46/25.72 (8) (Cond_isdiv2(&&(>=(x21, x22), >(x22, 0)), x22, x21)=FALSE ==> FILTER(x22, cons(x21, zs[7]))_>=_NonInfC & FILTER(x22, cons(x21, zs[7]))_>=_IF(isdiv(x22, x21), x22, x21, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (9) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (10) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x19 >= 0 & [3 + (-1)bso_32] + [6]x19 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (11) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x21 >= 0 & [3 + (-1)bso_32] + [6]x21 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (12) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x19 >= 0 & [3 + (-1)bso_32] + [6]x19 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (13) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x21 >= 0 & [3 + (-1)bso_32] + [6]x21 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (14) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (15) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x19 >= 0 & [3 + (-1)bso_32] + [6]x19 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (16) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x21 >= 0 & [3 + (-1)bso_32] + [6]x21 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (17) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.72 79.46/25.72 (18) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.72 79.46/25.72 (19) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (20) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 *We consider the chain IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]), FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]), IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) which results in the following constraint: 79.46/25.72 79.46/25.72 (1) (x[10]=x[7] & zs[10]=cons(y[7], zs[7]) & isdiv(x[7], y[7])=FALSE & x[7]=x[10]1 & y[7]=y[10]1 & zs[7]=zs[10]1 ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.72 79.46/25.72 (2) (isdiv(x[7], y[7])=FALSE ==> FILTER(x[7], cons(y[7], zs[7]))_>=_NonInfC & FILTER(x[7], cons(y[7], zs[7]))_>=_IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on isdiv(x[7], y[7])=FALSE which results in the following new constraints: 79.46/25.72 79.46/25.72 (3) (Cond_isdiv(>(x27, 0), x27, 0)=FALSE ==> FILTER(x27, cons(0, zs[7]))_>=_NonInfC & FILTER(x27, cons(0, zs[7]))_>=_IF(isdiv(x27, 0), x27, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 (4) (Cond_isdiv1(&&(>(x29, x28), >(x28, 0)), x29, x28)=FALSE ==> FILTER(x29, cons(x28, zs[7]))_>=_NonInfC & FILTER(x29, cons(x28, zs[7]))_>=_IF(isdiv(x29, x28), x29, x28, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 (5) (Cond_isdiv2(&&(>=(x30, x31), >(x31, 0)), x31, x30)=FALSE ==> FILTER(x31, cons(x30, zs[7]))_>=_NonInfC & FILTER(x31, cons(x30, zs[7]))_>=_IF(isdiv(x31, x30), x31, x30, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (3) using rules (III), (VII) which results in the following new constraint: 79.46/25.72 79.46/25.72 (6) (Cond_isdiv(>(x27, 0), x27, 0)=FALSE ==> FILTER(x27, cons(0, zs[7]))_>=_NonInfC & FILTER(x27, cons(0, zs[7]))_>=_IF(isdiv(x27, 0), x27, 0, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (4) using rules (III), (VII) which results in the following new constraint: 79.46/25.72 79.46/25.72 (7) (Cond_isdiv1(&&(>(x29, x28), >(x28, 0)), x29, x28)=FALSE ==> FILTER(x29, cons(x28, zs[7]))_>=_NonInfC & FILTER(x29, cons(x28, zs[7]))_>=_IF(isdiv(x29, x28), x29, x28, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (5) using rules (III), (VII) which results in the following new constraint: 79.46/25.72 79.46/25.72 (8) (Cond_isdiv2(&&(>=(x30, x31), >(x31, 0)), x31, x30)=FALSE ==> FILTER(x31, cons(x30, zs[7]))_>=_NonInfC & FILTER(x31, cons(x30, zs[7]))_>=_IF(isdiv(x31, x30), x31, x30, zs[7]) & (U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (9) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (10) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x28 >= 0 & [3 + (-1)bso_32] + [6]x28 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (11) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x30 >= 0 & [3 + (-1)bso_32] + [6]x30 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (12) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x28 >= 0 & [3 + (-1)bso_32] + [6]x28 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (13) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x30 >= 0 & [3 + (-1)bso_32] + [6]x30 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (14) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (15) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x28 >= 0 & [3 + (-1)bso_32] + [6]x28 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (16) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] + [(6)bni_31]x30 >= 0 & [3 + (-1)bso_32] + [6]x30 >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (17) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(5)bni_31 + (-1)Bound*bni_31] + [(2)bni_31]zs[7] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.72 79.46/25.72 (18) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint: 79.46/25.72 79.46/25.72 (19) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (20) ((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 To summarize, we get the following constraints P__>=_ for the following pairs. 79.46/25.72 79.46/25.72 *IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.72 79.46/25.72 *((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & 0 >= 0 & [1 + (-1)bso_28] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 *IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.72 79.46/25.72 *((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & 0 >= 0 & [1 + (-1)bso_30] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 *FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *((U^Increasing(IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])), >=) & [(2)bni_31] >= 0 & [(6)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [3 + (-1)bso_32] >= 0 & [1] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. 79.46/25.72 79.46/25.72 Using the following integer polynomial ordering the resulting constraints can be solved 79.46/25.72 79.46/25.72 Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]: 79.46/25.72 79.46/25.72 POL(TRUE) = 0 79.46/25.72 POL(FALSE) = 0 79.46/25.72 POL(isdiv(x_1, x_2)) = 0 79.46/25.72 POL(0) = 0 79.46/25.72 POL(Cond_isdiv(x_1, x_2, x_3)) = 0 79.46/25.72 POL(>(x_1, x_2)) = 0 79.46/25.72 POL(Cond_isdiv1(x_1, x_2, x_3)) = 0 79.46/25.72 POL(&&(x_1, x_2)) = 0 79.46/25.72 POL(Cond_isdiv2(x_1, x_2, x_3)) = [3]x_1 79.46/25.72 POL(>=(x_1, x_2)) = 0 79.46/25.72 POL(-(x_1, x_2)) = 0 79.46/25.72 POL(IF(x_1, x_2, x_3, x_4)) = [2] + [2]x_4 + [-1]x_1 79.46/25.72 POL(FILTER(x_1, x_2)) = [1] + [2]x_2 79.46/25.72 POL(cons(x_1, x_2)) = [2] + x_2 + [3]x_1 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs are in P_>: 79.46/25.72 79.46/25.72 79.46/25.72 IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.72 IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.72 FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs are in P_bound: 79.46/25.72 79.46/25.72 79.46/25.72 FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7]) 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs are in P_>=: 79.46/25.72 79.46/25.72 none 79.46/25.72 79.46/25.72 79.46/25.72 At least the following rules have been oriented under context sensitive arithmetic replacement: 79.46/25.72 79.46/25.72 Cond_isdiv(>(x, 0), x, 0)^1 -> isdiv(x, 0)^1 79.46/25.72 Cond_isdiv1(&&(>(x, y), >(y, 0)), x, y)^1 -> isdiv(x, y)^1 79.46/25.72 isdiv(x, y)^1 <-> Cond_isdiv2(&&(>=(y, x), >(x, 0)), x, y)^1 79.46/25.72 Cond_isdiv2(TRUE, x, y)^1 <-> isdiv(x, -(y, x))^1 79.46/25.72 &&(TRUE, TRUE)^1 <-> TRUE^1 79.46/25.72 &&(TRUE, FALSE)^1 <-> FALSE^1 79.46/25.72 &&(FALSE, TRUE)^1 <-> FALSE^1 79.46/25.72 &&(FALSE, FALSE)^1 <-> FALSE^1 79.46/25.72 Cond_isdiv(TRUE, x, 0)^1 <-> TRUE^1 79.46/25.72 Cond_isdiv1(TRUE, x, y)^1 <-> FALSE^1 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (18) 79.46/25.72 Obligation: 79.46/25.72 IDP problem: 79.46/25.72 The following function symbols are pre-defined: 79.46/25.72 <<< 79.46/25.72 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.72 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.72 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.72 / ~ Div: (Integer, Integer) -> Integer 79.46/25.72 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.72 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.72 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.72 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.72 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.72 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.72 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.72 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.72 + ~ Add: (Integer, Integer) -> Integer 79.46/25.72 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.72 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.72 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.72 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.72 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.72 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.72 >>> 79.46/25.72 79.46/25.72 79.46/25.72 The following domains are used: 79.46/25.72 Integer, Boolean 79.46/25.72 79.46/25.72 The ITRS R consists of the following rules: 79.46/25.72 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.72 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.72 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.72 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.72 79.46/25.72 The integer pair graph contains the following rules and edges: 79.46/25.72 (10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) 79.46/25.72 (9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) 79.46/25.72 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(TRUE, x0, x1) 79.46/25.72 Cond_nats1(TRUE, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(TRUE, x0, x1, x2) 79.46/25.72 if(FALSE, x0, x1, x2) 79.46/25.72 Cond_isdiv(TRUE, x0, 0) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(TRUE, x0, x1) 79.46/25.72 Cond_isdiv2(TRUE, x0, x1) 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (19) IDependencyGraphProof (EQUIVALENT) 79.46/25.72 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (20) 79.46/25.72 TRUE 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (21) 79.46/25.72 Obligation: 79.46/25.72 IDP problem: 79.46/25.72 The following function symbols are pre-defined: 79.46/25.72 <<< 79.46/25.72 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.72 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.72 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.72 / ~ Div: (Integer, Integer) -> Integer 79.46/25.72 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.72 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.72 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.72 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.72 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.72 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.72 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.72 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.72 + ~ Add: (Integer, Integer) -> Integer 79.46/25.72 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.72 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.72 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.72 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.72 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.72 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.72 >>> 79.46/25.72 79.46/25.72 79.46/25.72 The following domains are used: 79.46/25.72 Integer, Boolean 79.46/25.72 79.46/25.72 The ITRS R consists of the following rules: 79.46/25.72 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.72 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.72 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.72 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.72 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.72 Cond_nats(TRUE, x, y) -> nil 79.46/25.72 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.72 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.72 79.46/25.72 The integer pair graph contains the following rules and edges: 79.46/25.72 (5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.72 79.46/25.72 (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]')) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(TRUE, x0, x1) 79.46/25.72 Cond_nats1(TRUE, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(TRUE, x0, x1, x2) 79.46/25.72 if(FALSE, x0, x1, x2) 79.46/25.72 Cond_isdiv(TRUE, x0, 0) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(TRUE, x0, x1) 79.46/25.72 Cond_isdiv2(TRUE, x0, x1) 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (22) UsableRulesProof (EQUIVALENT) 79.46/25.72 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. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (23) 79.46/25.72 Obligation: 79.46/25.72 IDP problem: 79.46/25.72 The following function symbols are pre-defined: 79.46/25.72 <<< 79.46/25.72 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.72 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.72 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.72 / ~ Div: (Integer, Integer) -> Integer 79.46/25.72 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.72 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.72 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.72 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.72 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.72 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.72 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.72 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.72 + ~ Add: (Integer, Integer) -> Integer 79.46/25.72 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.72 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.72 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.72 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.72 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.72 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.72 >>> 79.46/25.72 79.46/25.72 79.46/25.72 The following domains are used: 79.46/25.72 Integer, Boolean 79.46/25.72 79.46/25.72 The ITRS R consists of the following rules: 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.72 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.72 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.72 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.72 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.72 79.46/25.72 The integer pair graph contains the following rules and edges: 79.46/25.72 (5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.72 79.46/25.72 (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]')) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(TRUE, x0, x1) 79.46/25.72 Cond_nats1(TRUE, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(TRUE, x0, x1, x2) 79.46/25.72 if(FALSE, x0, x1, x2) 79.46/25.72 Cond_isdiv(TRUE, x0, 0) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(TRUE, x0, x1) 79.46/25.72 Cond_isdiv2(TRUE, x0, x1) 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (24) IDPtoQDPProof (SOUND) 79.46/25.72 Represented integers and predefined function symbols by Terms 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (25) 79.46/25.72 Obligation: 79.46/25.72 Q DP problem: 79.46/25.72 The TRS P consists of the following rules: 79.46/25.72 79.46/25.72 SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.72 79.46/25.72 The TRS R consists of the following rules: 79.46/25.72 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(true, x, y, zs) -> filter(x, zs) 79.46/25.72 if(false, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 isdiv(x, pos(01)) -> Cond_isdiv(greater_int(x, pos(01)), x, pos(01)) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(and(greater_int(x, y), greater_int(y, pos(01))), x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(and(greatereq_int(y, x), greater_int(x, pos(01))), x, y) 79.46/25.72 Cond_isdiv2(true, x, y) -> isdiv(x, minus_int(y, x)) 79.46/25.72 Cond_isdiv(true, x, pos(01)) -> true 79.46/25.72 Cond_isdiv1(true, x, y) -> false 79.46/25.72 greater_int(pos(01), pos(01)) -> false 79.46/25.72 greater_int(pos(01), neg(01)) -> false 79.46/25.72 greater_int(neg(01), pos(01)) -> false 79.46/25.72 greater_int(neg(01), neg(01)) -> false 79.46/25.72 greater_int(pos(01), pos(s(y))) -> false 79.46/25.72 greater_int(neg(01), pos(s(y))) -> false 79.46/25.72 greater_int(pos(01), neg(s(y))) -> true 79.46/25.72 greater_int(neg(01), neg(s(y))) -> true 79.46/25.72 greater_int(pos(s(x)), pos(01)) -> true 79.46/25.72 greater_int(neg(s(x)), pos(01)) -> false 79.46/25.72 greater_int(pos(s(x)), neg(01)) -> true 79.46/25.72 greater_int(neg(s(x)), neg(01)) -> false 79.46/25.72 greater_int(pos(s(x)), neg(s(y))) -> true 79.46/25.72 greater_int(neg(s(x)), pos(s(y))) -> false 79.46/25.72 greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y)) 79.46/25.72 greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y)) 79.46/25.72 and(false, false) -> false 79.46/25.72 and(false, true) -> false 79.46/25.72 and(true, false) -> false 79.46/25.72 and(true, true) -> true 79.46/25.72 greatereq_int(pos(x), pos(01)) -> true 79.46/25.72 greatereq_int(neg(01), pos(01)) -> true 79.46/25.72 greatereq_int(neg(01), neg(y)) -> true 79.46/25.72 greatereq_int(pos(x), neg(y)) -> true 79.46/25.72 greatereq_int(pos(01), pos(s(y))) -> false 79.46/25.72 greatereq_int(neg(x), pos(s(y))) -> false 79.46/25.72 greatereq_int(neg(s(x)), pos(01)) -> false 79.46/25.72 greatereq_int(neg(s(x)), neg(01)) -> false 79.46/25.72 greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y)) 79.46/25.72 greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y)) 79.46/25.72 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 79.46/25.72 minus_int(neg(x), neg(y)) -> minus_nat(y, x) 79.46/25.72 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 79.46/25.72 minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y)) 79.46/25.72 plus_nat(01, x) -> x 79.46/25.72 plus_nat(s(x), y) -> s(plus_nat(x, y)) 79.46/25.72 minus_nat(01, 01) -> pos(01) 79.46/25.72 minus_nat(01, s(y)) -> neg(s(y)) 79.46/25.72 minus_nat(s(x), 01) -> pos(s(x)) 79.46/25.72 minus_nat(s(x), s(y)) -> minus_nat(x, y) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(true, x0, x1) 79.46/25.72 Cond_nats1(true, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(true, x0, x1, x2) 79.46/25.72 if(false, x0, x1, x2) 79.46/25.72 Cond_isdiv(true, x0, pos(01)) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(true, x0, x1) 79.46/25.72 Cond_isdiv2(true, x0, x1) 79.46/25.72 greater_int(pos(01), pos(01)) 79.46/25.72 greater_int(pos(01), neg(01)) 79.46/25.72 greater_int(neg(01), pos(01)) 79.46/25.72 greater_int(neg(01), neg(01)) 79.46/25.72 greater_int(pos(01), pos(s(x0))) 79.46/25.72 greater_int(neg(01), pos(s(x0))) 79.46/25.72 greater_int(pos(01), neg(s(x0))) 79.46/25.72 greater_int(neg(01), neg(s(x0))) 79.46/25.72 greater_int(pos(s(x0)), pos(01)) 79.46/25.72 greater_int(neg(s(x0)), pos(01)) 79.46/25.72 greater_int(pos(s(x0)), neg(01)) 79.46/25.72 greater_int(neg(s(x0)), neg(01)) 79.46/25.72 greater_int(pos(s(x0)), neg(s(x1))) 79.46/25.72 greater_int(neg(s(x0)), pos(s(x1))) 79.46/25.72 greater_int(pos(s(x0)), pos(s(x1))) 79.46/25.72 greater_int(neg(s(x0)), neg(s(x1))) 79.46/25.72 and(false, false) 79.46/25.72 and(false, true) 79.46/25.72 and(true, false) 79.46/25.72 and(true, true) 79.46/25.72 greatereq_int(pos(x0), pos(01)) 79.46/25.72 greatereq_int(neg(01), pos(01)) 79.46/25.72 greatereq_int(neg(01), neg(x0)) 79.46/25.72 greatereq_int(pos(x0), neg(x1)) 79.46/25.72 greatereq_int(pos(01), pos(s(x0))) 79.46/25.72 greatereq_int(neg(x0), pos(s(x1))) 79.46/25.72 greatereq_int(neg(s(x0)), pos(01)) 79.46/25.72 greatereq_int(neg(s(x0)), neg(01)) 79.46/25.72 greatereq_int(pos(s(x0)), pos(s(x1))) 79.46/25.72 greatereq_int(neg(s(x0)), neg(s(x1))) 79.46/25.72 minus_int(pos(x0), pos(x1)) 79.46/25.72 minus_int(neg(x0), neg(x1)) 79.46/25.72 minus_int(neg(x0), pos(x1)) 79.46/25.72 minus_int(pos(x0), neg(x1)) 79.46/25.72 plus_nat(01, x0) 79.46/25.72 plus_nat(s(x0), x1) 79.46/25.72 minus_nat(01, 01) 79.46/25.72 minus_nat(01, s(x0)) 79.46/25.72 minus_nat(s(x0), 01) 79.46/25.72 minus_nat(s(x0), s(x1)) 79.46/25.72 79.46/25.72 We have to consider all minimal (P,Q,R)-chains. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (26) QReductionProof (EQUIVALENT) 79.46/25.72 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 79.46/25.72 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(true, x0, x1) 79.46/25.72 Cond_nats1(true, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (27) 79.46/25.72 Obligation: 79.46/25.72 Q DP problem: 79.46/25.72 The TRS P consists of the following rules: 79.46/25.72 79.46/25.72 SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.72 79.46/25.72 The TRS R consists of the following rules: 79.46/25.72 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(true, x, y, zs) -> filter(x, zs) 79.46/25.72 if(false, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 isdiv(x, pos(01)) -> Cond_isdiv(greater_int(x, pos(01)), x, pos(01)) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(and(greater_int(x, y), greater_int(y, pos(01))), x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(and(greatereq_int(y, x), greater_int(x, pos(01))), x, y) 79.46/25.72 Cond_isdiv2(true, x, y) -> isdiv(x, minus_int(y, x)) 79.46/25.72 Cond_isdiv(true, x, pos(01)) -> true 79.46/25.72 Cond_isdiv1(true, x, y) -> false 79.46/25.72 greater_int(pos(01), pos(01)) -> false 79.46/25.72 greater_int(pos(01), neg(01)) -> false 79.46/25.72 greater_int(neg(01), pos(01)) -> false 79.46/25.72 greater_int(neg(01), neg(01)) -> false 79.46/25.72 greater_int(pos(01), pos(s(y))) -> false 79.46/25.72 greater_int(neg(01), pos(s(y))) -> false 79.46/25.72 greater_int(pos(01), neg(s(y))) -> true 79.46/25.72 greater_int(neg(01), neg(s(y))) -> true 79.46/25.72 greater_int(pos(s(x)), pos(01)) -> true 79.46/25.72 greater_int(neg(s(x)), pos(01)) -> false 79.46/25.72 greater_int(pos(s(x)), neg(01)) -> true 79.46/25.72 greater_int(neg(s(x)), neg(01)) -> false 79.46/25.72 greater_int(pos(s(x)), neg(s(y))) -> true 79.46/25.72 greater_int(neg(s(x)), pos(s(y))) -> false 79.46/25.72 greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y)) 79.46/25.72 greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y)) 79.46/25.72 and(false, false) -> false 79.46/25.72 and(false, true) -> false 79.46/25.72 and(true, false) -> false 79.46/25.72 and(true, true) -> true 79.46/25.72 greatereq_int(pos(x), pos(01)) -> true 79.46/25.72 greatereq_int(neg(01), pos(01)) -> true 79.46/25.72 greatereq_int(neg(01), neg(y)) -> true 79.46/25.72 greatereq_int(pos(x), neg(y)) -> true 79.46/25.72 greatereq_int(pos(01), pos(s(y))) -> false 79.46/25.72 greatereq_int(neg(x), pos(s(y))) -> false 79.46/25.72 greatereq_int(neg(s(x)), pos(01)) -> false 79.46/25.72 greatereq_int(neg(s(x)), neg(01)) -> false 79.46/25.72 greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y)) 79.46/25.72 greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y)) 79.46/25.72 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 79.46/25.72 minus_int(neg(x), neg(y)) -> minus_nat(y, x) 79.46/25.72 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 79.46/25.72 minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y)) 79.46/25.72 plus_nat(01, x) -> x 79.46/25.72 plus_nat(s(x), y) -> s(plus_nat(x, y)) 79.46/25.72 minus_nat(01, 01) -> pos(01) 79.46/25.72 minus_nat(01, s(y)) -> neg(s(y)) 79.46/25.72 minus_nat(s(x), 01) -> pos(s(x)) 79.46/25.72 minus_nat(s(x), s(y)) -> minus_nat(x, y) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(true, x0, x1, x2) 79.46/25.72 if(false, x0, x1, x2) 79.46/25.72 Cond_isdiv(true, x0, pos(01)) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(true, x0, x1) 79.46/25.72 Cond_isdiv2(true, x0, x1) 79.46/25.72 greater_int(pos(01), pos(01)) 79.46/25.72 greater_int(pos(01), neg(01)) 79.46/25.72 greater_int(neg(01), pos(01)) 79.46/25.72 greater_int(neg(01), neg(01)) 79.46/25.72 greater_int(pos(01), pos(s(x0))) 79.46/25.72 greater_int(neg(01), pos(s(x0))) 79.46/25.72 greater_int(pos(01), neg(s(x0))) 79.46/25.72 greater_int(neg(01), neg(s(x0))) 79.46/25.72 greater_int(pos(s(x0)), pos(01)) 79.46/25.72 greater_int(neg(s(x0)), pos(01)) 79.46/25.72 greater_int(pos(s(x0)), neg(01)) 79.46/25.72 greater_int(neg(s(x0)), neg(01)) 79.46/25.72 greater_int(pos(s(x0)), neg(s(x1))) 79.46/25.72 greater_int(neg(s(x0)), pos(s(x1))) 79.46/25.72 greater_int(pos(s(x0)), pos(s(x1))) 79.46/25.72 greater_int(neg(s(x0)), neg(s(x1))) 79.46/25.72 and(false, false) 79.46/25.72 and(false, true) 79.46/25.72 and(true, false) 79.46/25.72 and(true, true) 79.46/25.72 greatereq_int(pos(x0), pos(01)) 79.46/25.72 greatereq_int(neg(01), pos(01)) 79.46/25.72 greatereq_int(neg(01), neg(x0)) 79.46/25.72 greatereq_int(pos(x0), neg(x1)) 79.46/25.72 greatereq_int(pos(01), pos(s(x0))) 79.46/25.72 greatereq_int(neg(x0), pos(s(x1))) 79.46/25.72 greatereq_int(neg(s(x0)), pos(01)) 79.46/25.72 greatereq_int(neg(s(x0)), neg(01)) 79.46/25.72 greatereq_int(pos(s(x0)), pos(s(x1))) 79.46/25.72 greatereq_int(neg(s(x0)), neg(s(x1))) 79.46/25.72 minus_int(pos(x0), pos(x1)) 79.46/25.72 minus_int(neg(x0), neg(x1)) 79.46/25.72 minus_int(neg(x0), pos(x1)) 79.46/25.72 minus_int(pos(x0), neg(x1)) 79.46/25.72 plus_nat(01, x0) 79.46/25.72 plus_nat(s(x0), x1) 79.46/25.72 minus_nat(01, 01) 79.46/25.72 minus_nat(01, s(x0)) 79.46/25.72 minus_nat(s(x0), 01) 79.46/25.72 minus_nat(s(x0), s(x1)) 79.46/25.72 79.46/25.72 We have to consider all minimal (P,Q,R)-chains. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (28) QDPOrderProof (EQUIVALENT) 79.46/25.72 We use the reduction pair processor [LPAR04,JAR06]. 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs can be oriented strictly and are deleted. 79.46/25.72 79.46/25.72 SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5])) 79.46/25.72 The remaining pairs can at least be oriented weakly. 79.46/25.72 Used ordering: Combined order from the following AFS and order. 79.46/25.72 SIEVE(x1) = x1 79.46/25.72 79.46/25.72 cons(x1, x2) = cons(x2) 79.46/25.72 79.46/25.72 filter(x1, x2) = filter(x2) 79.46/25.72 79.46/25.72 nil = nil 79.46/25.72 79.46/25.72 if(x1, x2, x3, x4) = if(x4) 79.46/25.72 79.46/25.72 79.46/25.72 Knuth-Bendix order [KBO] with precedence:filter_1 > if_1 > cons_1 79.46/25.72 79.46/25.72 and weight map: 79.46/25.72 79.46/25.72 filter_1=1 79.46/25.72 cons_1=2 79.46/25.72 if_1=3 79.46/25.72 nil=1 79.46/25.72 79.46/25.72 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 79.46/25.72 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(true, x, y, zs) -> filter(x, zs) 79.46/25.72 if(false, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (29) 79.46/25.72 Obligation: 79.46/25.72 Q DP problem: 79.46/25.72 P is empty. 79.46/25.72 The TRS R consists of the following rules: 79.46/25.72 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(true, x, y, zs) -> filter(x, zs) 79.46/25.72 if(false, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 isdiv(x, pos(01)) -> Cond_isdiv(greater_int(x, pos(01)), x, pos(01)) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(and(greater_int(x, y), greater_int(y, pos(01))), x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(and(greatereq_int(y, x), greater_int(x, pos(01))), x, y) 79.46/25.72 Cond_isdiv2(true, x, y) -> isdiv(x, minus_int(y, x)) 79.46/25.72 Cond_isdiv(true, x, pos(01)) -> true 79.46/25.72 Cond_isdiv1(true, x, y) -> false 79.46/25.72 greater_int(pos(01), pos(01)) -> false 79.46/25.72 greater_int(pos(01), neg(01)) -> false 79.46/25.72 greater_int(neg(01), pos(01)) -> false 79.46/25.72 greater_int(neg(01), neg(01)) -> false 79.46/25.72 greater_int(pos(01), pos(s(y))) -> false 79.46/25.72 greater_int(neg(01), pos(s(y))) -> false 79.46/25.72 greater_int(pos(01), neg(s(y))) -> true 79.46/25.72 greater_int(neg(01), neg(s(y))) -> true 79.46/25.72 greater_int(pos(s(x)), pos(01)) -> true 79.46/25.72 greater_int(neg(s(x)), pos(01)) -> false 79.46/25.72 greater_int(pos(s(x)), neg(01)) -> true 79.46/25.72 greater_int(neg(s(x)), neg(01)) -> false 79.46/25.72 greater_int(pos(s(x)), neg(s(y))) -> true 79.46/25.72 greater_int(neg(s(x)), pos(s(y))) -> false 79.46/25.72 greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y)) 79.46/25.72 greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y)) 79.46/25.72 and(false, false) -> false 79.46/25.72 and(false, true) -> false 79.46/25.72 and(true, false) -> false 79.46/25.72 and(true, true) -> true 79.46/25.72 greatereq_int(pos(x), pos(01)) -> true 79.46/25.72 greatereq_int(neg(01), pos(01)) -> true 79.46/25.72 greatereq_int(neg(01), neg(y)) -> true 79.46/25.72 greatereq_int(pos(x), neg(y)) -> true 79.46/25.72 greatereq_int(pos(01), pos(s(y))) -> false 79.46/25.72 greatereq_int(neg(x), pos(s(y))) -> false 79.46/25.72 greatereq_int(neg(s(x)), pos(01)) -> false 79.46/25.72 greatereq_int(neg(s(x)), neg(01)) -> false 79.46/25.72 greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y)) 79.46/25.72 greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y)) 79.46/25.72 minus_int(pos(x), pos(y)) -> minus_nat(x, y) 79.46/25.72 minus_int(neg(x), neg(y)) -> minus_nat(y, x) 79.46/25.72 minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y)) 79.46/25.72 minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y)) 79.46/25.72 plus_nat(01, x) -> x 79.46/25.72 plus_nat(s(x), y) -> s(plus_nat(x, y)) 79.46/25.72 minus_nat(01, 01) -> pos(01) 79.46/25.72 minus_nat(01, s(y)) -> neg(s(y)) 79.46/25.72 minus_nat(s(x), 01) -> pos(s(x)) 79.46/25.72 minus_nat(s(x), s(y)) -> minus_nat(x, y) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(true, x0, x1, x2) 79.46/25.72 if(false, x0, x1, x2) 79.46/25.72 Cond_isdiv(true, x0, pos(01)) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(true, x0, x1) 79.46/25.72 Cond_isdiv2(true, x0, x1) 79.46/25.72 greater_int(pos(01), pos(01)) 79.46/25.72 greater_int(pos(01), neg(01)) 79.46/25.72 greater_int(neg(01), pos(01)) 79.46/25.72 greater_int(neg(01), neg(01)) 79.46/25.72 greater_int(pos(01), pos(s(x0))) 79.46/25.72 greater_int(neg(01), pos(s(x0))) 79.46/25.72 greater_int(pos(01), neg(s(x0))) 79.46/25.72 greater_int(neg(01), neg(s(x0))) 79.46/25.72 greater_int(pos(s(x0)), pos(01)) 79.46/25.72 greater_int(neg(s(x0)), pos(01)) 79.46/25.72 greater_int(pos(s(x0)), neg(01)) 79.46/25.72 greater_int(neg(s(x0)), neg(01)) 79.46/25.72 greater_int(pos(s(x0)), neg(s(x1))) 79.46/25.72 greater_int(neg(s(x0)), pos(s(x1))) 79.46/25.72 greater_int(pos(s(x0)), pos(s(x1))) 79.46/25.72 greater_int(neg(s(x0)), neg(s(x1))) 79.46/25.72 and(false, false) 79.46/25.72 and(false, true) 79.46/25.72 and(true, false) 79.46/25.72 and(true, true) 79.46/25.72 greatereq_int(pos(x0), pos(01)) 79.46/25.72 greatereq_int(neg(01), pos(01)) 79.46/25.72 greatereq_int(neg(01), neg(x0)) 79.46/25.72 greatereq_int(pos(x0), neg(x1)) 79.46/25.72 greatereq_int(pos(01), pos(s(x0))) 79.46/25.72 greatereq_int(neg(x0), pos(s(x1))) 79.46/25.72 greatereq_int(neg(s(x0)), pos(01)) 79.46/25.72 greatereq_int(neg(s(x0)), neg(01)) 79.46/25.72 greatereq_int(pos(s(x0)), pos(s(x1))) 79.46/25.72 greatereq_int(neg(s(x0)), neg(s(x1))) 79.46/25.72 minus_int(pos(x0), pos(x1)) 79.46/25.72 minus_int(neg(x0), neg(x1)) 79.46/25.72 minus_int(neg(x0), pos(x1)) 79.46/25.72 minus_int(pos(x0), neg(x1)) 79.46/25.72 plus_nat(01, x0) 79.46/25.72 plus_nat(s(x0), x1) 79.46/25.72 minus_nat(01, 01) 79.46/25.72 minus_nat(01, s(x0)) 79.46/25.72 minus_nat(s(x0), 01) 79.46/25.72 minus_nat(s(x0), s(x1)) 79.46/25.72 79.46/25.72 We have to consider all minimal (P,Q,R)-chains. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (30) PisEmptyProof (EQUIVALENT) 79.46/25.72 The TRS P is empty. Hence, there is no (P,Q,R) chain. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (31) 79.46/25.72 YES 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (32) 79.46/25.72 Obligation: 79.46/25.72 IDP problem: 79.46/25.72 The following function symbols are pre-defined: 79.46/25.72 <<< 79.46/25.72 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.72 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.72 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.72 / ~ Div: (Integer, Integer) -> Integer 79.46/25.72 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.72 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.72 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.72 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.72 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.72 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.72 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.72 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.72 + ~ Add: (Integer, Integer) -> Integer 79.46/25.72 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.72 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.72 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.72 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.72 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.72 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.72 >>> 79.46/25.72 79.46/25.72 79.46/25.72 The following domains are used: 79.46/25.72 Integer, Boolean 79.46/25.72 79.46/25.72 The ITRS R consists of the following rules: 79.46/25.72 nats(x, y) -> Cond_nats(x > y, x, y) 79.46/25.72 nats(x, y) -> Cond_nats1(y >= x, x, y) 79.46/25.72 filter(x, nil) -> nil 79.46/25.72 filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs) 79.46/25.72 if(TRUE, x, y, zs) -> filter(x, zs) 79.46/25.72 isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0) 79.46/25.72 isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y) 79.46/25.72 isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y) 79.46/25.72 Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x) 79.46/25.72 Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y)) 79.46/25.72 Cond_nats(TRUE, x, y) -> nil 79.46/25.72 if(FALSE, x, y, zs) -> cons(y, filter(x, zs)) 79.46/25.72 Cond_isdiv(TRUE, x, 0) -> TRUE 79.46/25.72 Cond_isdiv1(TRUE, x, y) -> FALSE 79.46/25.72 79.46/25.72 The integer pair graph contains the following rules and edges: 79.46/25.72 (4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4]) 79.46/25.72 (3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3]) 79.46/25.72 79.46/25.72 (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3]) 79.46/25.72 (3) -> (4), if (y[3] >= x[3] & x[3] ->^* x[4] & y[3] ->^* y[4]) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(TRUE, x0, x1) 79.46/25.72 Cond_nats1(TRUE, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(TRUE, x0, x1, x2) 79.46/25.72 if(FALSE, x0, x1, x2) 79.46/25.72 Cond_isdiv(TRUE, x0, 0) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(TRUE, x0, x1) 79.46/25.72 Cond_isdiv2(TRUE, x0, x1) 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (33) UsableRulesProof (EQUIVALENT) 79.46/25.72 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. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (34) 79.46/25.72 Obligation: 79.46/25.72 IDP problem: 79.46/25.72 The following function symbols are pre-defined: 79.46/25.72 <<< 79.46/25.72 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.72 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.72 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.72 / ~ Div: (Integer, Integer) -> Integer 79.46/25.72 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.72 && ~ Land: (Boolean, Boolean) -> Boolean 79.46/25.72 ! ~ Lnot: (Boolean) -> Boolean 79.46/25.72 = ~ Eq: (Integer, Integer) -> Boolean 79.46/25.72 <= ~ Le: (Integer, Integer) -> Boolean 79.46/25.72 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.46/25.72 % ~ Mod: (Integer, Integer) -> Integer 79.46/25.72 > ~ Gt: (Integer, Integer) -> Boolean 79.46/25.72 + ~ Add: (Integer, Integer) -> Integer 79.46/25.72 -1 ~ UnaryMinus: (Integer) -> Integer 79.46/25.72 < ~ Lt: (Integer, Integer) -> Boolean 79.46/25.72 || ~ Lor: (Boolean, Boolean) -> Boolean 79.46/25.72 - ~ Sub: (Integer, Integer) -> Integer 79.46/25.72 ~ ~ Bwnot: (Integer) -> Integer 79.46/25.72 * ~ Mul: (Integer, Integer) -> Integer 79.46/25.72 >>> 79.46/25.72 79.46/25.72 79.46/25.72 The following domains are used: 79.46/25.72 Integer 79.46/25.72 79.46/25.72 R is empty. 79.46/25.72 79.46/25.72 The integer pair graph contains the following rules and edges: 79.46/25.72 (4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4]) 79.46/25.72 (3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3]) 79.46/25.72 79.46/25.72 (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3]) 79.46/25.72 (3) -> (4), if (y[3] >= x[3] & x[3] ->^* x[4] & y[3] ->^* y[4]) 79.46/25.72 79.46/25.72 The set Q consists of the following terms: 79.46/25.72 primes(x0) 79.46/25.72 nats(x0, x1) 79.46/25.72 Cond_nats(TRUE, x0, x1) 79.46/25.72 Cond_nats1(TRUE, x0, x1) 79.46/25.72 sieve(nil) 79.46/25.72 sieve(cons(x0, x1)) 79.46/25.72 filter(x0, nil) 79.46/25.72 filter(x0, cons(x1, x2)) 79.46/25.72 if(TRUE, x0, x1, x2) 79.46/25.72 if(FALSE, x0, x1, x2) 79.46/25.72 Cond_isdiv(TRUE, x0, 0) 79.46/25.72 isdiv(x0, x1) 79.46/25.72 Cond_isdiv1(TRUE, x0, x1) 79.46/25.72 Cond_isdiv2(TRUE, x0, x1) 79.46/25.72 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (35) IDPNonInfProof (SOUND) 79.46/25.72 Used the following options for this NonInfProof: 79.46/25.72 79.46/25.72 IDPGPoloSolver: 79.46/25.72 Range: [(-1,2)] 79.46/25.72 IsNat: false 79.46/25.72 Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@ea73c8 79.46/25.72 Constraint Generator: NonInfConstraintGenerator: 79.46/25.72 PathGenerator: MetricPathGenerator: 79.46/25.72 Max Left Steps: 1 79.46/25.72 Max Right Steps: 1 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 The constraints were generated the following way: 79.46/25.72 79.46/25.72 The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: 79.46/25.72 79.46/25.72 Note that final constraints are written in bold face. 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 For Pair COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]) the following chains were created: 79.46/25.72 *We consider the chain NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]), COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]), NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]) which results in the following constraint: 79.46/25.72 79.46/25.72 (1) (>=(y[3], x[3])=TRUE & x[3]=x[4] & y[3]=y[4] & +(x[4], 1)=x[3]1 & y[4]=y[3]1 ==> COND_NATS1(TRUE, x[4], y[4])_>=_NonInfC & COND_NATS1(TRUE, x[4], y[4])_>=_NATS(+(x[4], 1), y[4]) & (U^Increasing(NATS(+(x[4], 1), y[4])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (1) using rules (III), (IV) which results in the following new constraint: 79.46/25.72 79.46/25.72 (2) (>=(y[3], x[3])=TRUE ==> COND_NATS1(TRUE, x[3], y[3])_>=_NonInfC & COND_NATS1(TRUE, x[3], y[3])_>=_NATS(+(x[3], 1), y[3]) & (U^Increasing(NATS(+(x[4], 1), y[4])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (3) (y[3] + [-1]x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] + [(-1)bni_11]x[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (4) (y[3] + [-1]x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] + [(-1)bni_11]x[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (5) (y[3] + [-1]x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] + [(-1)bni_11]x[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (5) using rule (IDP_SMT_SPLIT) which results in the following new constraint: 79.46/25.72 79.46/25.72 (6) (y[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (6) using rule (IDP_SMT_SPLIT) which results in the following new constraints: 79.46/25.72 79.46/25.72 (7) (y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 (8) (y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 For Pair NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]) the following chains were created: 79.46/25.72 *We consider the chain NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]), COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]) which results in the following constraint: 79.46/25.72 79.46/25.72 (1) (>=(y[3], x[3])=TRUE & x[3]=x[4] & y[3]=y[4] ==> NATS(x[3], y[3])_>=_NonInfC & NATS(x[3], y[3])_>=_COND_NATS1(>=(y[3], x[3]), x[3], y[3]) & (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (1) using rule (IV) which results in the following new constraint: 79.46/25.72 79.46/25.72 (2) (>=(y[3], x[3])=TRUE ==> NATS(x[3], y[3])_>=_NonInfC & NATS(x[3], y[3])_>=_COND_NATS1(>=(y[3], x[3]), x[3], y[3]) & (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=)) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint: 79.46/25.72 79.46/25.72 (3) (y[3] + [-1]x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] + [(-1)bni_13]x[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint: 79.46/25.72 79.46/25.72 (4) (y[3] + [-1]x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] + [(-1)bni_13]x[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint: 79.46/25.72 79.46/25.72 (5) (y[3] + [-1]x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] + [(-1)bni_13]x[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (5) using rule (IDP_SMT_SPLIT) which results in the following new constraint: 79.46/25.72 79.46/25.72 (6) (y[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 We simplified constraint (6) using rule (IDP_SMT_SPLIT) which results in the following new constraints: 79.46/25.72 79.46/25.72 (7) (y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 (8) (y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 To summarize, we get the following constraints P__>=_ for the following pairs. 79.46/25.72 79.46/25.72 *COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]) 79.46/25.72 79.46/25.72 *(y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *(y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(NATS(+(x[4], 1), y[4])), >=) & [(-1)bni_11 + (-1)Bound*bni_11] + [bni_11]y[3] >= 0 & [(-1)bso_12] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 *NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]) 79.46/25.72 79.46/25.72 *(y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 *(y[3] >= 0 & x[3] >= 0 ==> (U^Increasing(COND_NATS1(>=(y[3], x[3]), x[3], y[3])), >=) & [(-1)Bound*bni_13] + [bni_13]y[3] >= 0 & [1 + (-1)bso_14] >= 0) 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 79.46/25.72 The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. 79.46/25.72 79.46/25.72 Using the following integer polynomial ordering the resulting constraints can be solved 79.46/25.72 79.46/25.72 Polynomial interpretation over integers[POLO]: 79.46/25.72 79.46/25.72 POL(TRUE) = 0 79.46/25.72 POL(FALSE) = 0 79.46/25.72 POL(COND_NATS1(x_1, x_2, x_3)) = [-1] + x_3 + [-1]x_2 79.46/25.72 POL(NATS(x_1, x_2)) = x_2 + [-1]x_1 79.46/25.72 POL(+(x_1, x_2)) = x_1 + x_2 79.46/25.72 POL(1) = [1] 79.46/25.72 POL(>=(x_1, x_2)) = [-1] 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs are in P_>: 79.46/25.72 79.46/25.72 79.46/25.72 NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]) 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs are in P_bound: 79.46/25.72 79.46/25.72 79.46/25.72 COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]) 79.46/25.72 NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]) 79.46/25.72 79.46/25.72 79.46/25.72 The following pairs are in P_>=: 79.46/25.72 79.46/25.72 79.46/25.72 COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]) 79.46/25.72 79.46/25.72 79.46/25.72 There are no usable rules. 79.46/25.72 ---------------------------------------- 79.46/25.72 79.46/25.72 (36) 79.46/25.72 Obligation: 79.46/25.72 IDP problem: 79.46/25.72 The following function symbols are pre-defined: 79.46/25.72 <<< 79.46/25.72 & ~ Bwand: (Integer, Integer) -> Integer 79.46/25.72 >= ~ Ge: (Integer, Integer) -> Boolean 79.46/25.72 | ~ Bwor: (Integer, Integer) -> Integer 79.46/25.72 / ~ Div: (Integer, Integer) -> Integer 79.46/25.72 != ~ Neq: (Integer, Integer) -> Boolean 79.46/25.72 && ~ Land: (Boolean, Boolean) -> Boolean 79.73/25.72 ! ~ Lnot: (Boolean) -> Boolean 79.73/25.72 = ~ Eq: (Integer, Integer) -> Boolean 79.73/25.72 <= ~ Le: (Integer, Integer) -> Boolean 79.73/25.72 ^ ~ Bwxor: (Integer, Integer) -> Integer 79.73/25.72 % ~ Mod: (Integer, Integer) -> Integer 79.73/25.72 > ~ Gt: (Integer, Integer) -> Boolean 79.73/25.72 + ~ Add: (Integer, Integer) -> Integer 79.73/25.72 -1 ~ UnaryMinus: (Integer) -> Integer 79.73/25.72 < ~ Lt: (Integer, Integer) -> Boolean 79.73/25.72 || ~ Lor: (Boolean, Boolean) -> Boolean 79.73/25.72 - ~ Sub: (Integer, Integer) -> Integer 79.73/25.72 ~ ~ Bwnot: (Integer) -> Integer 79.73/25.72 * ~ Mul: (Integer, Integer) -> Integer 79.73/25.72 >>> 79.73/25.72 79.73/25.72 79.73/25.72 The following domains are used: 79.73/25.72 Integer 79.73/25.72 79.73/25.72 R is empty. 79.73/25.72 79.73/25.72 The integer pair graph contains the following rules and edges: 79.73/25.72 (4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4]) 79.73/25.72 79.73/25.72 79.73/25.72 The set Q consists of the following terms: 79.73/25.72 primes(x0) 79.73/25.72 nats(x0, x1) 79.73/25.72 Cond_nats(TRUE, x0, x1) 79.73/25.72 Cond_nats1(TRUE, x0, x1) 79.73/25.72 sieve(nil) 79.73/25.72 sieve(cons(x0, x1)) 79.73/25.72 filter(x0, nil) 79.73/25.72 filter(x0, cons(x1, x2)) 79.73/25.72 if(TRUE, x0, x1, x2) 79.73/25.72 if(FALSE, x0, x1, x2) 79.73/25.72 Cond_isdiv(TRUE, x0, 0) 79.73/25.72 isdiv(x0, x1) 79.73/25.72 Cond_isdiv1(TRUE, x0, x1) 79.73/25.72 Cond_isdiv2(TRUE, x0, x1) 79.73/25.72 79.73/25.72 ---------------------------------------- 79.73/25.72 79.73/25.72 (37) IDependencyGraphProof (EQUIVALENT) 79.73/25.72 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 79.73/25.72 ---------------------------------------- 79.73/25.72 79.73/25.72 (38) 79.73/25.72 TRUE 79.84/25.79 EOF