3.26/1.49 YES 3.26/1.50 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 3.26/1.50 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 3.26/1.50 3.26/1.50 3.26/1.50 Termination of the given CSR could be proven: 3.26/1.50 3.26/1.50 (0) CSR 3.26/1.50 (1) CSRRRRProof [EQUIVALENT, 22 ms] 3.26/1.50 (2) CSR 3.26/1.50 (3) CSRRRRProof [EQUIVALENT, 5 ms] 3.26/1.50 (4) CSR 3.26/1.50 (5) CSRRRRProof [EQUIVALENT, 0 ms] 3.26/1.50 (6) CSR 3.26/1.50 (7) CSRRRRProof [EQUIVALENT, 0 ms] 3.26/1.50 (8) CSR 3.26/1.50 (9) RisEmptyProof [EQUIVALENT, 0 ms] 3.26/1.50 (10) YES 3.26/1.50 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (0) 3.26/1.50 Obligation: 3.26/1.50 Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 filter(cons(X, Y), 0, M) -> cons(0, filter(Y, M, M)) 3.26/1.50 filter(cons(X, Y), s(N), M) -> cons(X, filter(Y, N, M)) 3.26/1.50 sieve(cons(0, Y)) -> cons(0, sieve(Y)) 3.26/1.50 sieve(cons(s(N), Y)) -> cons(s(N), sieve(filter(Y, N, N))) 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 filter: {1, 2, 3} 3.26/1.50 cons: {1} 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (1) CSRRRRProof (EQUIVALENT) 3.26/1.50 The following CSR is given: Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 filter(cons(X, Y), 0, M) -> cons(0, filter(Y, M, M)) 3.26/1.50 filter(cons(X, Y), s(N), M) -> cons(X, filter(Y, N, M)) 3.26/1.50 sieve(cons(0, Y)) -> cons(0, sieve(Y)) 3.26/1.50 sieve(cons(s(N), Y)) -> cons(s(N), sieve(filter(Y, N, N))) 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 filter: {1, 2, 3} 3.26/1.50 cons: {1} 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 Used ordering: 3.26/1.50 Polynomial interpretation [POLO]: 3.26/1.50 3.26/1.50 POL(0) = 0 3.26/1.50 POL(cons(x_1, x_2)) = x_1 3.26/1.50 POL(filter(x_1, x_2, x_3)) = x_1 + x_2 + x_3 3.26/1.50 POL(nats(x_1)) = x_1 3.26/1.50 POL(s(x_1)) = x_1 3.26/1.50 POL(sieve(x_1)) = 1 + x_1 3.26/1.50 POL(zprimes) = 1 3.26/1.50 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.50 3.26/1.50 sieve(cons(0, Y)) -> cons(0, sieve(Y)) 3.26/1.50 sieve(cons(s(N), Y)) -> cons(s(N), sieve(filter(Y, N, N))) 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (2) 3.26/1.50 Obligation: 3.26/1.50 Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 filter(cons(X, Y), 0, M) -> cons(0, filter(Y, M, M)) 3.26/1.50 filter(cons(X, Y), s(N), M) -> cons(X, filter(Y, N, M)) 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 filter: {1, 2, 3} 3.26/1.50 cons: {1} 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (3) CSRRRRProof (EQUIVALENT) 3.26/1.50 The following CSR is given: Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 filter(cons(X, Y), 0, M) -> cons(0, filter(Y, M, M)) 3.26/1.50 filter(cons(X, Y), s(N), M) -> cons(X, filter(Y, N, M)) 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 filter: {1, 2, 3} 3.26/1.50 cons: {1} 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 Used ordering: 3.26/1.50 Polynomial interpretation [POLO]: 3.26/1.50 3.26/1.50 POL(0) = 0 3.26/1.50 POL(cons(x_1, x_2)) = 1 + x_1 3.26/1.50 POL(filter(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 3.26/1.50 POL(nats(x_1)) = 1 + x_1 3.26/1.50 POL(s(x_1)) = x_1 3.26/1.50 POL(sieve(x_1)) = x_1 3.26/1.50 POL(zprimes) = 1 3.26/1.50 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.50 3.26/1.50 filter(cons(X, Y), 0, M) -> cons(0, filter(Y, M, M)) 3.26/1.50 filter(cons(X, Y), s(N), M) -> cons(X, filter(Y, N, M)) 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (4) 3.26/1.50 Obligation: 3.26/1.50 Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 cons: {1} 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (5) CSRRRRProof (EQUIVALENT) 3.26/1.50 The following CSR is given: Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 cons: {1} 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 Used ordering: 3.26/1.50 Polynomial interpretation [POLO]: 3.26/1.50 3.26/1.50 POL(0) = 0 3.26/1.50 POL(cons(x_1, x_2)) = x_1 3.26/1.50 POL(nats(x_1)) = 1 + x_1 3.26/1.50 POL(s(x_1)) = x_1 3.26/1.50 POL(sieve(x_1)) = x_1 3.26/1.50 POL(zprimes) = 1 3.26/1.50 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.50 3.26/1.50 nats(N) -> cons(N, nats(s(N))) 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (6) 3.26/1.50 Obligation: 3.26/1.50 Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (7) CSRRRRProof (EQUIVALENT) 3.26/1.50 The following CSR is given: Context-sensitive rewrite system: 3.26/1.50 The TRS R consists of the following rules: 3.26/1.50 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 The replacement map contains the following entries: 3.26/1.50 3.26/1.50 0: empty set 3.26/1.50 s: {1} 3.26/1.50 sieve: {1} 3.26/1.50 nats: {1} 3.26/1.50 zprimes: empty set 3.26/1.50 Used ordering: 3.26/1.50 Polynomial interpretation [POLO]: 3.26/1.50 3.26/1.50 POL(0) = 0 3.26/1.50 POL(nats(x_1)) = x_1 3.26/1.50 POL(s(x_1)) = x_1 3.26/1.50 POL(sieve(x_1)) = x_1 3.26/1.50 POL(zprimes) = 1 3.26/1.50 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 3.26/1.50 3.26/1.50 zprimes -> sieve(nats(s(s(0)))) 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (8) 3.26/1.50 Obligation: 3.26/1.50 Context-sensitive rewrite system: 3.26/1.50 R is empty. 3.26/1.50 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (9) RisEmptyProof (EQUIVALENT) 3.26/1.50 The CSR R is empty. Hence, termination is trivially proven. 3.26/1.50 ---------------------------------------- 3.26/1.50 3.26/1.50 (10) 3.26/1.50 YES 3.48/1.52 EOF