/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.itrs /export/starexec/sandbox/output/output_files


--------------------------------------------------------------------------------


YES
proof of /export/starexec/sandbox/benchmark/theBenchmark.itrs
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


Termination of the given ITRS could be proven:

(0) ITRS
(1) ITRStoIDPProof [EQUIVALENT, 0 ms]
(2) IDP
(3) UsableRulesProof [EQUIVALENT, 0 ms]
(4) IDP
(5) IDependencyGraphProof [EQUIVALENT, 0 ms]
(6) AND
    (7) IDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) IDP
        (10) IDPNonInfProof [SOUND, 168 ms]
        (11) IDP
        (12) IDependencyGraphProof [EQUIVALENT, 0 ms]
        (13) TRUE
    (14) IDP
        (15) UsableRulesProof [EQUIVALENT, 0 ms]
        (16) IDP
        (17) IDPNonInfProof [SOUND, 248 ms]
        (18) IDP
        (19) IDependencyGraphProof [EQUIVALENT, 0 ms]
        (20) TRUE
    (21) IDP
        (22) UsableRulesProof [EQUIVALENT, 0 ms]
        (23) IDP
        (24) IDPtoQDPProof [SOUND, 0 ms]
        (25) QDP
        (26) QReductionProof [EQUIVALENT, 0 ms]
        (27) QDP
        (28) QDPOrderProof [EQUIVALENT, 54 ms]
        (29) QDP
        (30) PisEmptyProof [EQUIVALENT, 0 ms]
        (31) YES
    (32) IDP
        (33) UsableRulesProof [EQUIVALENT, 0 ms]
        (34) IDP
        (35) IDPNonInfProof [SOUND, 35 ms]
        (36) IDP
        (37) IDependencyGraphProof [EQUIVALENT, 0 ms]
        (38) TRUE


----------------------------------------

(0)
Obligation:
ITRS problem:

The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>

The TRS R consists of the following rules:
primes(x) -> sieve(nats(2, x))
nats(x, y) -> Cond_nats(x > y, x, y)
Cond_nats(TRUE, x, y) -> nil
nats(x, y) -> Cond_nats1(y >= x, x, y)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
sieve(nil) -> nil
sieve(cons(x, ys)) -> cons(x, sieve(filter(x, ys)))
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
Cond_isdiv(TRUE, x, 0) -> TRUE
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
Cond_isdiv1(TRUE, x, y) -> FALSE
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(1) ITRStoIDPProof (EQUIVALENT)
Added dependency pairs
----------------------------------------

(2)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
primes(x) -> sieve(nats(2, x))
nats(x, y) -> Cond_nats(x > y, x, y)
Cond_nats(TRUE, x, y) -> nil
nats(x, y) -> Cond_nats1(y >= x, x, y)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
sieve(nil) -> nil
sieve(cons(x, ys)) -> cons(x, sieve(filter(x, ys)))
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
Cond_isdiv(TRUE, x, 0) -> TRUE
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
Cond_isdiv1(TRUE, x, y) -> FALSE
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)

The integer pair graph contains the following rules and edges:
(0): PRIMES(x[0]) -> SIEVE(nats(2, x[0]))
(1): PRIMES(x[1]) -> NATS(2, x[1])
(2): NATS(x[2], y[2]) -> COND_NATS(x[2] > y[2], x[2], y[2])
(3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3])
(4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4])
(5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))
(6): SIEVE(cons(x[6], ys[6])) -> FILTER(x[6], ys[6])
(7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])
(8): FILTER(x[8], cons(y[8], zs[8])) -> ISDIV(x[8], y[8])
(9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])
(10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])
(11): ISDIV(x[11], 0) -> COND_ISDIV(x[11] > 0, x[11], 0)
(12): ISDIV(x[12], y[12]) -> COND_ISDIV1(x[12] > y[12] && y[12] > 0, x[12], y[12])
(13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13])
(14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14])

   (0) -> (5), if (nats(2, x[0]) ->^* cons(x[5], ys[5]))
   (0) -> (6), if (nats(2, x[0]) ->^* cons(x[6], ys[6]))
   (1) -> (2), if (2 ->^* x[2] & x[1] ->^* y[2])
   (1) -> (3), if (2 ->^* x[3] & x[1] ->^* y[3])
   (3) -> (4), if (y[3] >= x[3]  & x[3] ->^* x[4] & y[3] ->^* y[4])
   (4) -> (2), if (x[4] + 1 ->^* x[2] & y[4] ->^* y[2])
   (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3])
   (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]'))
   (5) -> (6), if (filter(x[5], ys[5]) ->^* cons(x[6], ys[6]))
   (6) -> (7), if (x[6] ->^* x[7] & ys[6] ->^* cons(y[7], zs[7]))
   (6) -> (8), if (x[6] ->^* x[8] & ys[6] ->^* cons(y[8], zs[8]))
   (7) -> (9), if (isdiv(x[7], y[7])  & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9])
   (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10])
   (8) -> (11), if (x[8] ->^* x[11] & y[8] ->^* 0)
   (8) -> (12), if (x[8] ->^* x[12] & y[8] ->^* y[12])
   (8) -> (13), if (x[8] ->^* x[13] & y[8] ->^* y[13])
   (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7]))
   (9) -> (8), if (x[9] ->^* x[8] & zs[9] ->^* cons(y[8], zs[8]))
   (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7]))
   (10) -> (8), if (x[10] ->^* x[8] & zs[10] ->^* cons(y[8], zs[8]))
   (13) -> (14), if (y[13] >= x[13] && x[13] > 0  & x[13] ->^* x[14] & y[13] ->^* y[14])
   (14) -> (11), if (x[14] ->^* x[11] & y[14] - x[14] ->^* 0)
   (14) -> (12), if (x[14] ->^* x[12] & y[14] - x[14] ->^* y[12])
   (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(3) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(4)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
nats(x, y) -> Cond_nats(x > y, x, y)
nats(x, y) -> Cond_nats1(y >= x, x, y)
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
Cond_nats(TRUE, x, y) -> nil
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(0): PRIMES(x[0]) -> SIEVE(nats(2, x[0]))
(1): PRIMES(x[1]) -> NATS(2, x[1])
(2): NATS(x[2], y[2]) -> COND_NATS(x[2] > y[2], x[2], y[2])
(3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3])
(4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4])
(5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))
(6): SIEVE(cons(x[6], ys[6])) -> FILTER(x[6], ys[6])
(7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])
(8): FILTER(x[8], cons(y[8], zs[8])) -> ISDIV(x[8], y[8])
(9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])
(10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])
(11): ISDIV(x[11], 0) -> COND_ISDIV(x[11] > 0, x[11], 0)
(12): ISDIV(x[12], y[12]) -> COND_ISDIV1(x[12] > y[12] && y[12] > 0, x[12], y[12])
(13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13])
(14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14])

   (0) -> (5), if (nats(2, x[0]) ->^* cons(x[5], ys[5]))
   (0) -> (6), if (nats(2, x[0]) ->^* cons(x[6], ys[6]))
   (1) -> (2), if (2 ->^* x[2] & x[1] ->^* y[2])
   (1) -> (3), if (2 ->^* x[3] & x[1] ->^* y[3])
   (3) -> (4), if (y[3] >= x[3]  & x[3] ->^* x[4] & y[3] ->^* y[4])
   (4) -> (2), if (x[4] + 1 ->^* x[2] & y[4] ->^* y[2])
   (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3])
   (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]'))
   (5) -> (6), if (filter(x[5], ys[5]) ->^* cons(x[6], ys[6]))
   (6) -> (7), if (x[6] ->^* x[7] & ys[6] ->^* cons(y[7], zs[7]))
   (6) -> (8), if (x[6] ->^* x[8] & ys[6] ->^* cons(y[8], zs[8]))
   (7) -> (9), if (isdiv(x[7], y[7])  & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9])
   (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10])
   (8) -> (11), if (x[8] ->^* x[11] & y[8] ->^* 0)
   (8) -> (12), if (x[8] ->^* x[12] & y[8] ->^* y[12])
   (8) -> (13), if (x[8] ->^* x[13] & y[8] ->^* y[13])
   (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7]))
   (9) -> (8), if (x[9] ->^* x[8] & zs[9] ->^* cons(y[8], zs[8]))
   (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7]))
   (10) -> (8), if (x[10] ->^* x[8] & zs[10] ->^* cons(y[8], zs[8]))
   (13) -> (14), if (y[13] >= x[13] && x[13] > 0  & x[13] ->^* x[14] & y[13] ->^* y[14])
   (14) -> (11), if (x[14] ->^* x[11] & y[14] - x[14] ->^* 0)
   (14) -> (12), if (x[14] ->^* x[12] & y[14] - x[14] ->^* y[12])
   (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(5) IDependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 7 less nodes.
----------------------------------------

(6)
Complex Obligation (AND)

----------------------------------------

(7)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
nats(x, y) -> Cond_nats(x > y, x, y)
nats(x, y) -> Cond_nats1(y >= x, x, y)
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
Cond_nats(TRUE, x, y) -> nil
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14])
(13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13])

   (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13])
   (13) -> (14), if (y[13] >= x[13] && x[13] > 0  & x[13] ->^* x[14] & y[13] ->^* y[14])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(8) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(9)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

R is empty.

The integer pair graph contains the following rules and edges:
(14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14])
(13): ISDIV(x[13], y[13]) -> COND_ISDIV2(y[13] >= x[13] && x[13] > 0, x[13], y[13])

   (14) -> (13), if (x[14] ->^* x[13] & y[14] - x[14] ->^* y[13])
   (13) -> (14), if (y[13] >= x[13] && x[13] > 0  & x[13] ->^* x[14] & y[13] ->^* y[14])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(10) IDPNonInfProof (SOUND)
Used the following options for this NonInfProof:

IDPGPoloSolver:
Range: [(-1,2)]
IsNat: false
Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@76f4898b
Constraint Generator: NonInfConstraintGenerator:
PathGenerator: MetricPathGenerator:
Max Left Steps: 1
Max Right Steps: 1



The constraints were generated the following way:

The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps:

Note that final constraints are written in bold face.



For Pair COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14])) the following chains were created:
*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:

(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]))), >=))



We simplified constraint (1) using rules (III), (IV), (IDP_BOOLEAN) which results in the following new constraint:

(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]))), >=))



We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 + (-1)bso_14] + x[13] >= 0)



We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 + (-1)bso_14] + x[13] >= 0)



We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 + (-1)bso_14] + x[13] >= 0)








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:
*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:

(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])), >=))



We simplified constraint (1) using rules (IV), (IDP_BOOLEAN) which results in the following new constraint:

(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])), >=))



We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [1 + (-1)bso_16] >= 0)



We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [1 + (-1)bso_16] >= 0)



We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [1 + (-1)bso_16] >= 0)








To summarize, we get the following constraints P__>=_ for the following pairs.

*COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14]))

*(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 + (-1)bso_14] + x[13] >= 0)




*ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])

*(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)Bound*bni_15] + [bni_15]y[13] + [(-1)bni_15]x[13] >= 0 & [1 + (-1)bso_16] >= 0)








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. 

Using the following integer polynomial ordering the  resulting constraints can be solved 

Polynomial interpretation over integers[POLO]:

   POL(TRUE) = 0
   POL(FALSE) = 0
   POL(COND_ISDIV2(x_1, x_2, x_3)) = [-1] + x_3 + [-1]x_2 + [-1]x_1
   POL(ISDIV(x_1, x_2)) = x_2 + [-1]x_1
   POL(-(x_1, x_2)) = x_1 + [-1]x_2
   POL(&&(x_1, x_2)) = 0
   POL(>=(x_1, x_2)) = [-1]
   POL(>(x_1, x_2)) = [-1]
   POL(0) = 0


The following pairs are in P_>:


   ISDIV(x[13], y[13]) -> COND_ISDIV2(&&(>=(y[13], x[13]), >(x[13], 0)), x[13], y[13])


The following pairs are in P_bound:


   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])


The following pairs are in P_>=:


   COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], -(y[14], x[14]))


At least the following rules have been oriented under context sensitive arithmetic replacement:

   TRUE^1 -> &&(TRUE, TRUE)^1
   FALSE^1 -> &&(TRUE, FALSE)^1
   FALSE^1 -> &&(FALSE, TRUE)^1
   &&(FALSE, FALSE)^1 <-> FALSE^1

----------------------------------------

(11)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

R is empty.

The integer pair graph contains the following rules and edges:
(14): COND_ISDIV2(TRUE, x[14], y[14]) -> ISDIV(x[14], y[14] - x[14])


The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(12) IDependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(13)
TRUE

----------------------------------------

(14)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
nats(x, y) -> Cond_nats(x > y, x, y)
nats(x, y) -> Cond_nats1(y >= x, x, y)
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
Cond_nats(TRUE, x, y) -> nil
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])
(9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])
(7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])

   (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7]))
   (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7]))
   (7) -> (9), if (isdiv(x[7], y[7])  & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9])
   (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(15) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(16)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])
(9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])
(7): FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])

   (9) -> (7), if (x[9] ->^* x[7] & zs[9] ->^* cons(y[7], zs[7]))
   (10) -> (7), if (x[10] ->^* x[7] & zs[10] ->^* cons(y[7], zs[7]))
   (7) -> (9), if (isdiv(x[7], y[7])  & x[7] ->^* x[9] & y[7] ->^* y[9] & zs[7] ->^* zs[9])
   (7) -> (10), if (isdiv(x[7], y[7]) ->^* FALSE & x[7] ->^* x[10] & y[7] ->^* y[10] & zs[7] ->^* zs[10])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(17) IDPNonInfProof (SOUND)
Used the following options for this NonInfProof:

IDPGPoloSolver:
Range: [(-1,2)]
IsNat: true
Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@671b73e5
Constraint Generator: NonInfConstraintGenerator:
PathGenerator: MetricPathGenerator:
Max Left Steps: 1
Max Right Steps: 1



The constraints were generated the following way:

The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps:

Note that final constraints are written in bold face.



For Pair IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10]) the following chains were created:
*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(3)    ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & [(-1)bso_28] >= 0)



We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(4)    ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & [(-1)bso_28] >= 0)



We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(5)    ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & [(-1)bso_28] >= 0)



We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:

(6)    ((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & 0 >= 0 & [(-1)bso_28] >= 0)








For Pair IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9]) the following chains were created:
*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(3)    ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & [(-1)bso_30] >= 0)



We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(4)    ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & [(-1)bso_30] >= 0)



We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(5)    ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & [(-1)bso_30] >= 0)



We simplified constraint (5) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:

(6)    ((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & 0 >= 0 & [(-1)bso_30] >= 0)








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:
*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



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:

(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])), >=))

(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])), >=))

(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])), >=))



We simplified constraint (3) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (4) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (5) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x1 >= 0)



We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x3 >= 0)



We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x1 >= 0)



We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x3 >= 0)



We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x1 >= 0)



We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x3 >= 0)



We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)




*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



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:

(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])), >=))

(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])), >=))

(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])), >=))



We simplified constraint (3) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (4) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (5) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x10 >= 0)



We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x12 >= 0)



We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x10 >= 0)



We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x12 >= 0)



We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x10 >= 0)



We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x12 >= 0)



We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)




*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



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:

(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])), >=))

(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])), >=))

(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])), >=))



We simplified constraint (3) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (4) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (5) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x19 >= 0)



We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x21 >= 0)



We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x19 >= 0)



We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x21 >= 0)



We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x19 >= 0)



We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x21 >= 0)



We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)




*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



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:

(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])), >=))

(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])), >=))

(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])), >=))



We simplified constraint (3) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (4) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (5) using rules (III), (VII) which results in the following new constraint:

(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])), >=))



We simplified constraint (6) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (7) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x28 >= 0)



We simplified constraint (8) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x30 >= 0)



We simplified constraint (10) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x28 >= 0)



We simplified constraint (11) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x30 >= 0)



We simplified constraint (9) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (12) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x28 >= 0)



We simplified constraint (13) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] + [6]x30 >= 0)



We simplified constraint (14) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)



We simplified constraint (15) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (16) using rules (IDP_UNRESTRICTED_VARS), (IDP_POLY_GCD) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)



We simplified constraint (17) using rule (IDP_UNRESTRICTED_VARS) which results in the following new constraint:

(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 & [4 + (-1)bso_32] >= 0)








To summarize, we get the following constraints P__>=_ for the following pairs.

*IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])

*((U^Increasing(FILTER(x[10], zs[10])), >=) & [bni_27] = 0 & 0 >= 0 & [(-1)bso_28] >= 0)




*IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])

*((U^Increasing(FILTER(x[9], zs[9])), >=) & [bni_29] = 0 & 0 >= 0 & [(-1)bso_30] >= 0)




*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])), >=) & [(2)bni_31] >= 0 & 0 >= 0 & [(5)bni_31 + (-1)Bound*bni_31] >= 0 & [4 + (-1)bso_32] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)


*((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 & [4 + (-1)bso_32] >= 0 & [1] >= 0)








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. 

Using the following integer polynomial ordering the  resulting constraints can be solved 

Polynomial interpretation over integers with natural coefficients for non-tuple symbols [NONINF][POLO]:

   POL(TRUE) = 0
   POL(FALSE) = 0
   POL(isdiv(x_1, x_2)) = 0
   POL(0) = 0
   POL(Cond_isdiv(x_1, x_2, x_3)) = 0
   POL(>(x_1, x_2)) = 0
   POL(Cond_isdiv1(x_1, x_2, x_3)) = [3]x_1
   POL(&&(x_1, x_2)) = 0
   POL(Cond_isdiv2(x_1, x_2, x_3)) = [3]x_1
   POL(>=(x_1, x_2)) = 0
   POL(-(x_1, x_2)) = 0
   POL(IF(x_1, x_2, x_3, x_4)) = [1] + [2]x_4 + [-1]x_1
   POL(FILTER(x_1, x_2)) = [1] + [2]x_2
   POL(cons(x_1, x_2)) = [2] + x_2 + [3]x_1


The following pairs are in P_>:


   FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])


The following pairs are in P_bound:


   FILTER(x[7], cons(y[7], zs[7])) -> IF(isdiv(x[7], y[7]), x[7], y[7], zs[7])


The following pairs are in P_>=:


   IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])
   IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])


At least the following rules have been oriented under context sensitive arithmetic replacement:

   Cond_isdiv(>(x, 0), x, 0)^1 -> isdiv(x, 0)^1
   Cond_isdiv1(&&(>(x, y), >(y, 0)), x, y)^1 -> isdiv(x, y)^1
   isdiv(x, y)^1 <-> Cond_isdiv2(&&(>=(y, x), >(x, 0)), x, y)^1
   Cond_isdiv2(TRUE, x, y)^1 <-> isdiv(x, -(y, x))^1
   &&(TRUE, TRUE)^1 <-> TRUE^1
   &&(TRUE, FALSE)^1 <-> FALSE^1
   &&(FALSE, TRUE)^1 <-> FALSE^1
   &&(FALSE, FALSE)^1 <-> FALSE^1
   Cond_isdiv(TRUE, x, 0)^1 <-> TRUE^1
   Cond_isdiv1(TRUE, x, y)^1 <-> FALSE^1

----------------------------------------

(18)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(10): IF(FALSE, x[10], y[10], zs[10]) -> FILTER(x[10], zs[10])
(9): IF(TRUE, x[9], y[9], zs[9]) -> FILTER(x[9], zs[9])


The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(19) IDependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
----------------------------------------

(20)
TRUE

----------------------------------------

(21)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
nats(x, y) -> Cond_nats(x > y, x, y)
nats(x, y) -> Cond_nats1(y >= x, x, y)
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
Cond_nats(TRUE, x, y) -> nil
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))

   (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]'))

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(22) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(23)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(5): SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))

   (5) -> (5), if (filter(x[5], ys[5]) ->^* cons(x[5]', ys[5]'))

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(24) IDPtoQDPProof (SOUND)
Represented integers and predefined function symbols by Terms
----------------------------------------

(25)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))

The TRS R consists of the following rules:

   filter(x, nil) -> nil
   filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
   if(true, x, y, zs) -> filter(x, zs)
   if(false, x, y, zs) -> cons(y, filter(x, zs))
   isdiv(x, pos(01)) -> Cond_isdiv(greater_int(x, pos(01)), x, pos(01))
   isdiv(x, y) -> Cond_isdiv1(and(greater_int(x, y), greater_int(y, pos(01))), x, y)
   isdiv(x, y) -> Cond_isdiv2(and(greatereq_int(y, x), greater_int(x, pos(01))), x, y)
   Cond_isdiv2(true, x, y) -> isdiv(x, minus_int(y, x))
   Cond_isdiv(true, x, pos(01)) -> true
   Cond_isdiv1(true, x, y) -> false
   greater_int(pos(01), pos(01)) -> false
   greater_int(pos(01), neg(01)) -> false
   greater_int(neg(01), pos(01)) -> false
   greater_int(neg(01), neg(01)) -> false
   greater_int(pos(01), pos(s(y))) -> false
   greater_int(neg(01), pos(s(y))) -> false
   greater_int(pos(01), neg(s(y))) -> true
   greater_int(neg(01), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(01)) -> true
   greater_int(neg(s(x)), pos(01)) -> false
   greater_int(pos(s(x)), neg(01)) -> true
   greater_int(neg(s(x)), neg(01)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
   and(false, false) -> false
   and(false, true) -> false
   and(true, false) -> false
   and(true, true) -> true
   greatereq_int(pos(x), pos(01)) -> true
   greatereq_int(neg(01), pos(01)) -> true
   greatereq_int(neg(01), neg(y)) -> true
   greatereq_int(pos(x), neg(y)) -> true
   greatereq_int(pos(01), pos(s(y))) -> false
   greatereq_int(neg(x), pos(s(y))) -> false
   greatereq_int(neg(s(x)), pos(01)) -> false
   greatereq_int(neg(s(x)), neg(01)) -> false
   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
   minus_int(pos(x), pos(y)) -> minus_nat(x, y)
   minus_int(neg(x), neg(y)) -> minus_nat(y, x)
   minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y))
   minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y))
   plus_nat(01, x) -> x
   plus_nat(s(x), y) -> s(plus_nat(x, y))
   minus_nat(01, 01) -> pos(01)
   minus_nat(01, s(y)) -> neg(s(y))
   minus_nat(s(x), 01) -> pos(s(x))
   minus_nat(s(x), s(y)) -> minus_nat(x, y)

The set Q consists of the following terms:

   primes(x0)
   nats(x0, x1)
   Cond_nats(true, x0, x1)
   Cond_nats1(true, x0, x1)
   sieve(nil)
   sieve(cons(x0, x1))
   filter(x0, nil)
   filter(x0, cons(x1, x2))
   if(true, x0, x1, x2)
   if(false, x0, x1, x2)
   Cond_isdiv(true, x0, pos(01))
   isdiv(x0, x1)
   Cond_isdiv1(true, x0, x1)
   Cond_isdiv2(true, x0, x1)
   greater_int(pos(01), pos(01))
   greater_int(pos(01), neg(01))
   greater_int(neg(01), pos(01))
   greater_int(neg(01), neg(01))
   greater_int(pos(01), pos(s(x0)))
   greater_int(neg(01), pos(s(x0)))
   greater_int(pos(01), neg(s(x0)))
   greater_int(neg(01), neg(s(x0)))
   greater_int(pos(s(x0)), pos(01))
   greater_int(neg(s(x0)), pos(01))
   greater_int(pos(s(x0)), neg(01))
   greater_int(neg(s(x0)), neg(01))
   greater_int(pos(s(x0)), neg(s(x1)))
   greater_int(neg(s(x0)), pos(s(x1)))
   greater_int(pos(s(x0)), pos(s(x1)))
   greater_int(neg(s(x0)), neg(s(x1)))
   and(false, false)
   and(false, true)
   and(true, false)
   and(true, true)
   greatereq_int(pos(x0), pos(01))
   greatereq_int(neg(01), pos(01))
   greatereq_int(neg(01), neg(x0))
   greatereq_int(pos(x0), neg(x1))
   greatereq_int(pos(01), pos(s(x0)))
   greatereq_int(neg(x0), pos(s(x1)))
   greatereq_int(neg(s(x0)), pos(01))
   greatereq_int(neg(s(x0)), neg(01))
   greatereq_int(pos(s(x0)), pos(s(x1)))
   greatereq_int(neg(s(x0)), neg(s(x1)))
   minus_int(pos(x0), pos(x1))
   minus_int(neg(x0), neg(x1))
   minus_int(neg(x0), pos(x1))
   minus_int(pos(x0), neg(x1))
   plus_nat(01, x0)
   plus_nat(s(x0), x1)
   minus_nat(01, 01)
   minus_nat(01, s(x0))
   minus_nat(s(x0), 01)
   minus_nat(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(26) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   primes(x0)
   nats(x0, x1)
   Cond_nats(true, x0, x1)
   Cond_nats1(true, x0, x1)
   sieve(nil)
   sieve(cons(x0, x1))


----------------------------------------

(27)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))

The TRS R consists of the following rules:

   filter(x, nil) -> nil
   filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
   if(true, x, y, zs) -> filter(x, zs)
   if(false, x, y, zs) -> cons(y, filter(x, zs))
   isdiv(x, pos(01)) -> Cond_isdiv(greater_int(x, pos(01)), x, pos(01))
   isdiv(x, y) -> Cond_isdiv1(and(greater_int(x, y), greater_int(y, pos(01))), x, y)
   isdiv(x, y) -> Cond_isdiv2(and(greatereq_int(y, x), greater_int(x, pos(01))), x, y)
   Cond_isdiv2(true, x, y) -> isdiv(x, minus_int(y, x))
   Cond_isdiv(true, x, pos(01)) -> true
   Cond_isdiv1(true, x, y) -> false
   greater_int(pos(01), pos(01)) -> false
   greater_int(pos(01), neg(01)) -> false
   greater_int(neg(01), pos(01)) -> false
   greater_int(neg(01), neg(01)) -> false
   greater_int(pos(01), pos(s(y))) -> false
   greater_int(neg(01), pos(s(y))) -> false
   greater_int(pos(01), neg(s(y))) -> true
   greater_int(neg(01), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(01)) -> true
   greater_int(neg(s(x)), pos(01)) -> false
   greater_int(pos(s(x)), neg(01)) -> true
   greater_int(neg(s(x)), neg(01)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
   and(false, false) -> false
   and(false, true) -> false
   and(true, false) -> false
   and(true, true) -> true
   greatereq_int(pos(x), pos(01)) -> true
   greatereq_int(neg(01), pos(01)) -> true
   greatereq_int(neg(01), neg(y)) -> true
   greatereq_int(pos(x), neg(y)) -> true
   greatereq_int(pos(01), pos(s(y))) -> false
   greatereq_int(neg(x), pos(s(y))) -> false
   greatereq_int(neg(s(x)), pos(01)) -> false
   greatereq_int(neg(s(x)), neg(01)) -> false
   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
   minus_int(pos(x), pos(y)) -> minus_nat(x, y)
   minus_int(neg(x), neg(y)) -> minus_nat(y, x)
   minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y))
   minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y))
   plus_nat(01, x) -> x
   plus_nat(s(x), y) -> s(plus_nat(x, y))
   minus_nat(01, 01) -> pos(01)
   minus_nat(01, s(y)) -> neg(s(y))
   minus_nat(s(x), 01) -> pos(s(x))
   minus_nat(s(x), s(y)) -> minus_nat(x, y)

The set Q consists of the following terms:

   filter(x0, nil)
   filter(x0, cons(x1, x2))
   if(true, x0, x1, x2)
   if(false, x0, x1, x2)
   Cond_isdiv(true, x0, pos(01))
   isdiv(x0, x1)
   Cond_isdiv1(true, x0, x1)
   Cond_isdiv2(true, x0, x1)
   greater_int(pos(01), pos(01))
   greater_int(pos(01), neg(01))
   greater_int(neg(01), pos(01))
   greater_int(neg(01), neg(01))
   greater_int(pos(01), pos(s(x0)))
   greater_int(neg(01), pos(s(x0)))
   greater_int(pos(01), neg(s(x0)))
   greater_int(neg(01), neg(s(x0)))
   greater_int(pos(s(x0)), pos(01))
   greater_int(neg(s(x0)), pos(01))
   greater_int(pos(s(x0)), neg(01))
   greater_int(neg(s(x0)), neg(01))
   greater_int(pos(s(x0)), neg(s(x1)))
   greater_int(neg(s(x0)), pos(s(x1)))
   greater_int(pos(s(x0)), pos(s(x1)))
   greater_int(neg(s(x0)), neg(s(x1)))
   and(false, false)
   and(false, true)
   and(true, false)
   and(true, true)
   greatereq_int(pos(x0), pos(01))
   greatereq_int(neg(01), pos(01))
   greatereq_int(neg(01), neg(x0))
   greatereq_int(pos(x0), neg(x1))
   greatereq_int(pos(01), pos(s(x0)))
   greatereq_int(neg(x0), pos(s(x1)))
   greatereq_int(neg(s(x0)), pos(01))
   greatereq_int(neg(s(x0)), neg(01))
   greatereq_int(pos(s(x0)), pos(s(x1)))
   greatereq_int(neg(s(x0)), neg(s(x1)))
   minus_int(pos(x0), pos(x1))
   minus_int(neg(x0), neg(x1))
   minus_int(neg(x0), pos(x1))
   minus_int(pos(x0), neg(x1))
   plus_nat(01, x0)
   plus_nat(s(x0), x1)
   minus_nat(01, 01)
   minus_nat(01, s(x0))
   minus_nat(s(x0), 01)
   minus_nat(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(28) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   SIEVE(cons(x[5], ys[5])) -> SIEVE(filter(x[5], ys[5]))
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
SIEVE(x1)  =  x1

cons(x1, x2)  =  cons(x2)

filter(x1, x2)  =  filter(x2)

nil  =  nil

if(x1, x2, x3, x4)  =  if(x4)


Knuth-Bendix order [KBO] with precedence:filter_1 > if_1 > cons_1

and weight map:

   filter_1=1
   cons_1=2
   if_1=3
   nil=1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   filter(x, nil) -> nil
   filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
   if(true, x, y, zs) -> filter(x, zs)
   if(false, x, y, zs) -> cons(y, filter(x, zs))


----------------------------------------

(29)
Obligation:
Q DP problem:
P is empty.
The TRS R consists of the following rules:

   filter(x, nil) -> nil
   filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
   if(true, x, y, zs) -> filter(x, zs)
   if(false, x, y, zs) -> cons(y, filter(x, zs))
   isdiv(x, pos(01)) -> Cond_isdiv(greater_int(x, pos(01)), x, pos(01))
   isdiv(x, y) -> Cond_isdiv1(and(greater_int(x, y), greater_int(y, pos(01))), x, y)
   isdiv(x, y) -> Cond_isdiv2(and(greatereq_int(y, x), greater_int(x, pos(01))), x, y)
   Cond_isdiv2(true, x, y) -> isdiv(x, minus_int(y, x))
   Cond_isdiv(true, x, pos(01)) -> true
   Cond_isdiv1(true, x, y) -> false
   greater_int(pos(01), pos(01)) -> false
   greater_int(pos(01), neg(01)) -> false
   greater_int(neg(01), pos(01)) -> false
   greater_int(neg(01), neg(01)) -> false
   greater_int(pos(01), pos(s(y))) -> false
   greater_int(neg(01), pos(s(y))) -> false
   greater_int(pos(01), neg(s(y))) -> true
   greater_int(neg(01), neg(s(y))) -> true
   greater_int(pos(s(x)), pos(01)) -> true
   greater_int(neg(s(x)), pos(01)) -> false
   greater_int(pos(s(x)), neg(01)) -> true
   greater_int(neg(s(x)), neg(01)) -> false
   greater_int(pos(s(x)), neg(s(y))) -> true
   greater_int(neg(s(x)), pos(s(y))) -> false
   greater_int(pos(s(x)), pos(s(y))) -> greater_int(pos(x), pos(y))
   greater_int(neg(s(x)), neg(s(y))) -> greater_int(neg(x), neg(y))
   and(false, false) -> false
   and(false, true) -> false
   and(true, false) -> false
   and(true, true) -> true
   greatereq_int(pos(x), pos(01)) -> true
   greatereq_int(neg(01), pos(01)) -> true
   greatereq_int(neg(01), neg(y)) -> true
   greatereq_int(pos(x), neg(y)) -> true
   greatereq_int(pos(01), pos(s(y))) -> false
   greatereq_int(neg(x), pos(s(y))) -> false
   greatereq_int(neg(s(x)), pos(01)) -> false
   greatereq_int(neg(s(x)), neg(01)) -> false
   greatereq_int(pos(s(x)), pos(s(y))) -> greatereq_int(pos(x), pos(y))
   greatereq_int(neg(s(x)), neg(s(y))) -> greatereq_int(neg(x), neg(y))
   minus_int(pos(x), pos(y)) -> minus_nat(x, y)
   minus_int(neg(x), neg(y)) -> minus_nat(y, x)
   minus_int(neg(x), pos(y)) -> neg(plus_nat(x, y))
   minus_int(pos(x), neg(y)) -> pos(plus_nat(x, y))
   plus_nat(01, x) -> x
   plus_nat(s(x), y) -> s(plus_nat(x, y))
   minus_nat(01, 01) -> pos(01)
   minus_nat(01, s(y)) -> neg(s(y))
   minus_nat(s(x), 01) -> pos(s(x))
   minus_nat(s(x), s(y)) -> minus_nat(x, y)

The set Q consists of the following terms:

   filter(x0, nil)
   filter(x0, cons(x1, x2))
   if(true, x0, x1, x2)
   if(false, x0, x1, x2)
   Cond_isdiv(true, x0, pos(01))
   isdiv(x0, x1)
   Cond_isdiv1(true, x0, x1)
   Cond_isdiv2(true, x0, x1)
   greater_int(pos(01), pos(01))
   greater_int(pos(01), neg(01))
   greater_int(neg(01), pos(01))
   greater_int(neg(01), neg(01))
   greater_int(pos(01), pos(s(x0)))
   greater_int(neg(01), pos(s(x0)))
   greater_int(pos(01), neg(s(x0)))
   greater_int(neg(01), neg(s(x0)))
   greater_int(pos(s(x0)), pos(01))
   greater_int(neg(s(x0)), pos(01))
   greater_int(pos(s(x0)), neg(01))
   greater_int(neg(s(x0)), neg(01))
   greater_int(pos(s(x0)), neg(s(x1)))
   greater_int(neg(s(x0)), pos(s(x1)))
   greater_int(pos(s(x0)), pos(s(x1)))
   greater_int(neg(s(x0)), neg(s(x1)))
   and(false, false)
   and(false, true)
   and(true, false)
   and(true, true)
   greatereq_int(pos(x0), pos(01))
   greatereq_int(neg(01), pos(01))
   greatereq_int(neg(01), neg(x0))
   greatereq_int(pos(x0), neg(x1))
   greatereq_int(pos(01), pos(s(x0)))
   greatereq_int(neg(x0), pos(s(x1)))
   greatereq_int(neg(s(x0)), pos(01))
   greatereq_int(neg(s(x0)), neg(01))
   greatereq_int(pos(s(x0)), pos(s(x1)))
   greatereq_int(neg(s(x0)), neg(s(x1)))
   minus_int(pos(x0), pos(x1))
   minus_int(neg(x0), neg(x1))
   minus_int(neg(x0), pos(x1))
   minus_int(pos(x0), neg(x1))
   plus_nat(01, x0)
   plus_nat(s(x0), x1)
   minus_nat(01, 01)
   minus_nat(01, s(x0))
   minus_nat(s(x0), 01)
   minus_nat(s(x0), s(x1))

We have to consider all minimal (P,Q,R)-chains.
----------------------------------------

(30) PisEmptyProof (EQUIVALENT)
The TRS P is empty. Hence, there is no (P,Q,R) chain.
----------------------------------------

(31)
YES

----------------------------------------

(32)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer, Boolean

The ITRS R consists of the following rules:
nats(x, y) -> Cond_nats(x > y, x, y)
nats(x, y) -> Cond_nats1(y >= x, x, y)
filter(x, nil) -> nil
filter(x, cons(y, zs)) -> if(isdiv(x, y), x, y, zs)
if(TRUE, x, y, zs) -> filter(x, zs)
isdiv(x, 0) -> Cond_isdiv(x > 0, x, 0)
isdiv(x, y) -> Cond_isdiv1(x > y && y > 0, x, y)
isdiv(x, y) -> Cond_isdiv2(y >= x && x > 0, x, y)
Cond_isdiv2(TRUE, x, y) -> isdiv(x, y - x)
Cond_nats1(TRUE, x, y) -> cons(x, nats(x + 1, y))
Cond_nats(TRUE, x, y) -> nil
if(FALSE, x, y, zs) -> cons(y, filter(x, zs))
Cond_isdiv(TRUE, x, 0) -> TRUE
Cond_isdiv1(TRUE, x, y) -> FALSE

The integer pair graph contains the following rules and edges:
(4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4])
(3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3])

   (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3])
   (3) -> (4), if (y[3] >= x[3]  & x[3] ->^* x[4] & y[3] ->^* y[4])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(33) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(34)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

R is empty.

The integer pair graph contains the following rules and edges:
(4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4])
(3): NATS(x[3], y[3]) -> COND_NATS1(y[3] >= x[3], x[3], y[3])

   (4) -> (3), if (x[4] + 1 ->^* x[3] & y[4] ->^* y[3])
   (3) -> (4), if (y[3] >= x[3]  & x[3] ->^* x[4] & y[3] ->^* y[4])

The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(35) IDPNonInfProof (SOUND)
Used the following options for this NonInfProof:

IDPGPoloSolver:
Range: [(-1,2)]
IsNat: false
Interpretation Shape Heuristic: aprove.DPFramework.IDPProblem.Processors.nonInf.poly.IdpDefaultShapeHeuristic@76f4898b
Constraint Generator: NonInfConstraintGenerator:
PathGenerator: MetricPathGenerator:
Max Left Steps: 1
Max Right Steps: 1



The constraints were generated the following way:

The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps:

Note that final constraints are written in bold face.



For Pair COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4]) the following chains were created:
*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:

(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])), >=))



We simplified constraint (1) using rules (III), (IV) which results in the following new constraint:

(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])), >=))



We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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)



We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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)



We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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)



We simplified constraint (5) using rule (IDP_SMT_SPLIT) which results in the following new constraint:

(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)



We simplified constraint (6) using rule (IDP_SMT_SPLIT) which results in the following new constraints:

(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)

(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)








For Pair NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3]) the following chains were created:
*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:

(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])), >=))



We simplified constraint (1) using rule (IV) which results in the following new constraint:

(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])), >=))



We simplified constraint (2) using rule (POLY_CONSTRAINTS) which results in the following new constraint:

(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)



We simplified constraint (3) using rule (IDP_POLY_SIMPLIFY) which results in the following new constraint:

(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)



We simplified constraint (4) using rule (POLY_REMOVE_MIN_MAX) which results in the following new constraint:

(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)



We simplified constraint (5) using rule (IDP_SMT_SPLIT) which results in the following new constraint:

(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)



We simplified constraint (6) using rule (IDP_SMT_SPLIT) which results in the following new constraints:

(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)

(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)








To summarize, we get the following constraints P__>=_ for the following pairs.

*COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4])

*(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)


*(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)




*NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3])

*(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)


*(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)








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. 

Using the following integer polynomial ordering the  resulting constraints can be solved 

Polynomial interpretation over integers[POLO]:

   POL(TRUE) = 0
   POL(FALSE) = 0
   POL(COND_NATS1(x_1, x_2, x_3)) = [-1] + x_3 + [-1]x_2
   POL(NATS(x_1, x_2)) = x_2 + [-1]x_1
   POL(+(x_1, x_2)) = x_1 + x_2
   POL(1) = [1]
   POL(>=(x_1, x_2)) = [-1]


The following pairs are in P_>:


   NATS(x[3], y[3]) -> COND_NATS1(>=(y[3], x[3]), x[3], y[3])


The following pairs are in P_bound:


   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])


The following pairs are in P_>=:


   COND_NATS1(TRUE, x[4], y[4]) -> NATS(+(x[4], 1), y[4])


There are no usable rules.
----------------------------------------

(36)
Obligation:
IDP problem:
The following function symbols are pre-defined:
<<<
 & 	~ 	Bwand: (Integer, Integer) -> Integer
 >= 	~ 	Ge: (Integer, Integer) -> Boolean
 | 	~ 	Bwor: (Integer, Integer) -> Integer
 / 	~ 	Div: (Integer, Integer) -> Integer
 != 	~ 	Neq: (Integer, Integer) -> Boolean
 && 	~ 	Land: (Boolean, Boolean) -> Boolean
 ! 	~ 	Lnot: (Boolean) -> Boolean
 = 	~ 	Eq: (Integer, Integer) -> Boolean
 <= 	~ 	Le: (Integer, Integer) -> Boolean
 ^ 	~ 	Bwxor: (Integer, Integer) -> Integer
 % 	~ 	Mod: (Integer, Integer) -> Integer
 > 	~ 	Gt: (Integer, Integer) -> Boolean
 + 	~ 	Add: (Integer, Integer) -> Integer
 -1 	~ 	UnaryMinus: (Integer) -> Integer
 < 	~ 	Lt: (Integer, Integer) -> Boolean
 || 	~ 	Lor: (Boolean, Boolean) -> Boolean
 - 	~ 	Sub: (Integer, Integer) -> Integer
 ~ 	~ 	Bwnot: (Integer) -> Integer
 * 	~ 	Mul: (Integer, Integer) -> Integer
>>>


The following domains are used:
   Integer

R is empty.

The integer pair graph contains the following rules and edges:
(4): COND_NATS1(TRUE, x[4], y[4]) -> NATS(x[4] + 1, y[4])


The set Q consists of the following terms:
primes(x0)
nats(x0, x1)
Cond_nats(TRUE, x0, x1)
Cond_nats1(TRUE, x0, x1)
sieve(nil)
sieve(cons(x0, x1))
filter(x0, nil)
filter(x0, cons(x1, x2))
if(TRUE, x0, x1, x2)
if(FALSE, x0, x1, x2)
Cond_isdiv(TRUE, x0, 0)
isdiv(x0, x1)
Cond_isdiv1(TRUE, x0, x1)
Cond_isdiv2(TRUE, x0, x1)

----------------------------------------

(37) IDependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
----------------------------------------

(38)
TRUE