Integ TRS Inner 43557 pair #381740575

details

property	value
status	complete
benchmark	eratosthenes_small.itrs
ran by	Akihisa Yamada
cpu timeout	1200 seconds
wallclock timeout	300 seconds
memory limit	137438953472 bytes
execution host	n029.star.cs.uiowa.edu
space	Mixed_ITRS_2014

run statistics

property	value
solver	AProVE
configuration	standard
runtime (wallclock)	26.0975999832 seconds
cpu usage	80.632530704
max memory	5.101346816E9

stage attributes

key	value
output-size	96515
starexec-result	YES

output

/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: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty


Termination of the given ITRS could be proven:

(0) ITRS
(1) ITRStoIDPProof [EQUIVALENT, 0 ms]
(2) IDP
(3) UsableRulesProof [EQUIVALENT, 0 ms]
(4) IDP
(5) IDependencyGraphProof [EQUIVALENT, 4 ms]
(6) AND
    (7) IDP
        (8) UsableRulesProof [EQUIVALENT, 0 ms]
        (9) IDP
        (10) IDPNonInfProof [SOUND, 178 ms]
        (11) IDP
        (12) IDependencyGraphProof [EQUIVALENT, 0 ms]
        (13) TRUE
    (14) IDP
        (15) UsableRulesProof [EQUIVALENT, 0 ms]
        (16) IDP
        (17) IDPNonInfProof [SOUND, 301 ms]
        (18) IDP
        (19) IDependencyGraphProof [EQUIVALENT, 0 ms]
        (20) TRUE
    (21) IDP
        (22) UsableRulesProof [EQUIVALENT, 0 ms]
        (23) IDP
        (24) IDPtoQDPProof [SOUND, 51 ms]
        (25) QDP
        (26) QReductionProof [EQUIVALENT, 0 ms]
        (27) QDP
        (28) QDPOrderProof [EQUIVALENT, 39 ms]
        (29) QDP
        (30) PisEmptyProof [EQUIVALENT, 0 ms]
        (31) YES
    (32) IDP
        (33) UsableRulesProof [EQUIVALENT, 0 ms]
        (34) IDP
        (35) IDPNonInfProof [SOUND, 37 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)

popout

output may be truncated. 'popout' for the full output.

job log

popout

actions all output return to Integ TRS Inner 43557