1119.61/291.54 WORST_CASE(Omega(n^1), ?) 1124.53/292.76 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1124.53/292.76 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1124.53/292.76 1124.53/292.76 1124.53/292.76 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.53/292.76 1124.53/292.76 (0) CpxTRS 1124.53/292.76 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.53/292.76 (2) CpxTRS 1124.53/292.76 (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 1124.53/292.76 (4) typed CpxTrs 1124.53/292.76 (5) OrderProof [LOWER BOUND(ID), 0 ms] 1124.53/292.76 (6) typed CpxTrs 1124.53/292.76 (7) RewriteLemmaProof [LOWER BOUND(ID), 2566 ms] 1124.53/292.76 (8) BEST 1124.53/292.76 (9) proven lower bound 1124.53/292.76 (10) LowerBoundPropagationProof [FINISHED, 0 ms] 1124.53/292.76 (11) BOUNDS(n^1, INF) 1124.53/292.76 (12) typed CpxTrs 1124.53/292.76 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (0) 1124.53/292.76 Obligation: 1124.53/292.76 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.53/292.76 1124.53/292.76 1124.53/292.76 The TRS R consists of the following rules: 1124.53/292.76 1124.53/292.76 a__primes -> a__sieve(a__from(s(s(0)))) 1124.53/292.76 a__from(X) -> cons(mark(X), from(s(X))) 1124.53/292.76 a__head(cons(X, Y)) -> mark(X) 1124.53/292.76 a__tail(cons(X, Y)) -> mark(Y) 1124.53/292.76 a__if(true, X, Y) -> mark(X) 1124.53/292.76 a__if(false, X, Y) -> mark(Y) 1124.53/292.76 a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) 1124.53/292.76 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 1124.53/292.76 mark(primes) -> a__primes 1124.53/292.76 mark(sieve(X)) -> a__sieve(mark(X)) 1124.53/292.76 mark(from(X)) -> a__from(mark(X)) 1124.53/292.76 mark(head(X)) -> a__head(mark(X)) 1124.53/292.76 mark(tail(X)) -> a__tail(mark(X)) 1124.53/292.76 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1124.53/292.76 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 1124.53/292.76 mark(s(X)) -> s(mark(X)) 1124.53/292.76 mark(0) -> 0 1124.53/292.76 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1124.53/292.76 mark(true) -> true 1124.53/292.76 mark(false) -> false 1124.53/292.76 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 1124.53/292.76 a__primes -> primes 1124.53/292.76 a__sieve(X) -> sieve(X) 1124.53/292.76 a__from(X) -> from(X) 1124.53/292.76 a__head(X) -> head(X) 1124.53/292.76 a__tail(X) -> tail(X) 1124.53/292.76 a__if(X1, X2, X3) -> if(X1, X2, X3) 1124.53/292.76 a__filter(X1, X2) -> filter(X1, X2) 1124.53/292.76 1124.53/292.76 S is empty. 1124.53/292.76 Rewrite Strategy: INNERMOST 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 1124.53/292.76 Renamed function symbols to avoid clashes with predefined symbol. 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (2) 1124.53/292.76 Obligation: 1124.53/292.76 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 1124.53/292.76 1124.53/292.76 1124.53/292.76 The TRS R consists of the following rules: 1124.53/292.76 1124.53/292.76 a__primes -> a__sieve(a__from(s(s(0')))) 1124.53/292.76 a__from(X) -> cons(mark(X), from(s(X))) 1124.53/292.76 a__head(cons(X, Y)) -> mark(X) 1124.53/292.76 a__tail(cons(X, Y)) -> mark(Y) 1124.53/292.76 a__if(true, X, Y) -> mark(X) 1124.53/292.76 a__if(false, X, Y) -> mark(Y) 1124.53/292.76 a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) 1124.53/292.76 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 1124.53/292.76 mark(primes) -> a__primes 1124.53/292.76 mark(sieve(X)) -> a__sieve(mark(X)) 1124.53/292.76 mark(from(X)) -> a__from(mark(X)) 1124.53/292.76 mark(head(X)) -> a__head(mark(X)) 1124.53/292.76 mark(tail(X)) -> a__tail(mark(X)) 1124.53/292.76 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1124.53/292.76 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 1124.53/292.76 mark(s(X)) -> s(mark(X)) 1124.53/292.76 mark(0') -> 0' 1124.53/292.76 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1124.53/292.76 mark(true) -> true 1124.53/292.76 mark(false) -> false 1124.53/292.76 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 1124.53/292.76 a__primes -> primes 1124.53/292.76 a__sieve(X) -> sieve(X) 1124.53/292.76 a__from(X) -> from(X) 1124.53/292.76 a__head(X) -> head(X) 1124.53/292.76 a__tail(X) -> tail(X) 1124.53/292.76 a__if(X1, X2, X3) -> if(X1, X2, X3) 1124.53/292.76 a__filter(X1, X2) -> filter(X1, X2) 1124.53/292.76 1124.53/292.76 S is empty. 1124.53/292.76 Rewrite Strategy: INNERMOST 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 1124.53/292.76 Infered types. 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (4) 1124.53/292.76 Obligation: 1124.53/292.76 Innermost TRS: 1124.53/292.76 Rules: 1124.53/292.76 a__primes -> a__sieve(a__from(s(s(0')))) 1124.53/292.76 a__from(X) -> cons(mark(X), from(s(X))) 1124.53/292.76 a__head(cons(X, Y)) -> mark(X) 1124.53/292.76 a__tail(cons(X, Y)) -> mark(Y) 1124.53/292.76 a__if(true, X, Y) -> mark(X) 1124.53/292.76 a__if(false, X, Y) -> mark(Y) 1124.53/292.76 a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) 1124.53/292.76 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 1124.53/292.76 mark(primes) -> a__primes 1124.53/292.76 mark(sieve(X)) -> a__sieve(mark(X)) 1124.53/292.76 mark(from(X)) -> a__from(mark(X)) 1124.53/292.76 mark(head(X)) -> a__head(mark(X)) 1124.53/292.76 mark(tail(X)) -> a__tail(mark(X)) 1124.53/292.76 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1124.53/292.76 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 1124.53/292.76 mark(s(X)) -> s(mark(X)) 1124.53/292.76 mark(0') -> 0' 1124.53/292.76 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1124.53/292.76 mark(true) -> true 1124.53/292.76 mark(false) -> false 1124.53/292.76 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 1124.53/292.76 a__primes -> primes 1124.53/292.76 a__sieve(X) -> sieve(X) 1124.53/292.76 a__from(X) -> from(X) 1124.53/292.76 a__head(X) -> head(X) 1124.53/292.76 a__tail(X) -> tail(X) 1124.53/292.76 a__if(X1, X2, X3) -> if(X1, X2, X3) 1124.53/292.76 a__filter(X1, X2) -> filter(X1, X2) 1124.53/292.76 1124.53/292.76 Types: 1124.53/292.76 a__primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 s :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 0' :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 cons :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 mark :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 true :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 false :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 divides :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 hole_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if1_0 :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0 :: Nat -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (5) OrderProof (LOWER BOUND(ID)) 1124.53/292.76 Heuristically decided to analyse the following defined symbols: 1124.53/292.76 a__primes, a__sieve, a__from, mark, a__head, a__tail, a__if 1124.53/292.76 1124.53/292.76 They will be analysed ascendingly in the following order: 1124.53/292.76 a__primes = a__sieve 1124.53/292.76 a__primes = a__from 1124.53/292.76 a__primes = mark 1124.53/292.76 a__primes = a__head 1124.53/292.76 a__primes = a__tail 1124.53/292.76 a__primes = a__if 1124.53/292.76 a__sieve = a__from 1124.53/292.76 a__sieve = mark 1124.53/292.76 a__sieve = a__head 1124.53/292.76 a__sieve = a__tail 1124.53/292.76 a__sieve = a__if 1124.53/292.76 a__from = mark 1124.53/292.76 a__from = a__head 1124.53/292.76 a__from = a__tail 1124.53/292.76 a__from = a__if 1124.53/292.76 mark = a__head 1124.53/292.76 mark = a__tail 1124.53/292.76 mark = a__if 1124.53/292.76 a__head = a__tail 1124.53/292.76 a__head = a__if 1124.53/292.76 a__tail = a__if 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (6) 1124.53/292.76 Obligation: 1124.53/292.76 Innermost TRS: 1124.53/292.76 Rules: 1124.53/292.76 a__primes -> a__sieve(a__from(s(s(0')))) 1124.53/292.76 a__from(X) -> cons(mark(X), from(s(X))) 1124.53/292.76 a__head(cons(X, Y)) -> mark(X) 1124.53/292.76 a__tail(cons(X, Y)) -> mark(Y) 1124.53/292.76 a__if(true, X, Y) -> mark(X) 1124.53/292.76 a__if(false, X, Y) -> mark(Y) 1124.53/292.76 a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) 1124.53/292.76 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 1124.53/292.76 mark(primes) -> a__primes 1124.53/292.76 mark(sieve(X)) -> a__sieve(mark(X)) 1124.53/292.76 mark(from(X)) -> a__from(mark(X)) 1124.53/292.76 mark(head(X)) -> a__head(mark(X)) 1124.53/292.76 mark(tail(X)) -> a__tail(mark(X)) 1124.53/292.76 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1124.53/292.76 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 1124.53/292.76 mark(s(X)) -> s(mark(X)) 1124.53/292.76 mark(0') -> 0' 1124.53/292.76 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1124.53/292.76 mark(true) -> true 1124.53/292.76 mark(false) -> false 1124.53/292.76 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 1124.53/292.76 a__primes -> primes 1124.53/292.76 a__sieve(X) -> sieve(X) 1124.53/292.76 a__from(X) -> from(X) 1124.53/292.76 a__head(X) -> head(X) 1124.53/292.76 a__tail(X) -> tail(X) 1124.53/292.76 a__if(X1, X2, X3) -> if(X1, X2, X3) 1124.53/292.76 a__filter(X1, X2) -> filter(X1, X2) 1124.53/292.76 1124.53/292.76 Types: 1124.53/292.76 a__primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 s :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 0' :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 cons :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 mark :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 true :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 false :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 divides :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 hole_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if1_0 :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0 :: Nat -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 1124.53/292.76 1124.53/292.76 Generator Equations: 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(0) <=> 0' 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(+(x, 1)) <=> s(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(x)) 1124.53/292.76 1124.53/292.76 1124.53/292.76 The following defined symbols remain to be analysed: 1124.53/292.76 a__sieve, a__primes, a__from, mark, a__head, a__tail, a__if 1124.53/292.76 1124.53/292.76 They will be analysed ascendingly in the following order: 1124.53/292.76 a__primes = a__sieve 1124.53/292.76 a__primes = a__from 1124.53/292.76 a__primes = mark 1124.53/292.76 a__primes = a__head 1124.53/292.76 a__primes = a__tail 1124.53/292.76 a__primes = a__if 1124.53/292.76 a__sieve = a__from 1124.53/292.76 a__sieve = mark 1124.53/292.76 a__sieve = a__head 1124.53/292.76 a__sieve = a__tail 1124.53/292.76 a__sieve = a__if 1124.53/292.76 a__from = mark 1124.53/292.76 a__from = a__head 1124.53/292.76 a__from = a__tail 1124.53/292.76 a__from = a__if 1124.53/292.76 mark = a__head 1124.53/292.76 mark = a__tail 1124.53/292.76 mark = a__if 1124.53/292.76 a__head = a__tail 1124.53/292.76 a__head = a__if 1124.53/292.76 a__tail = a__if 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (7) RewriteLemmaProof (LOWER BOUND(ID)) 1124.53/292.76 Proved the following rewrite lemma: 1124.53/292.76 mark(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(n11_0)) -> gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(n11_0), rt in Omega(1 + n11_0) 1124.53/292.76 1124.53/292.76 Induction Base: 1124.53/292.76 mark(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(0)) ->_R^Omega(1) 1124.53/292.76 0' 1124.53/292.76 1124.53/292.76 Induction Step: 1124.53/292.76 mark(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(+(n11_0, 1))) ->_R^Omega(1) 1124.53/292.76 s(mark(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(n11_0))) ->_IH 1124.53/292.76 s(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(c12_0)) 1124.53/292.76 1124.53/292.76 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (8) 1124.53/292.76 Complex Obligation (BEST) 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (9) 1124.53/292.76 Obligation: 1124.53/292.76 Proved the lower bound n^1 for the following obligation: 1124.53/292.76 1124.53/292.76 Innermost TRS: 1124.53/292.76 Rules: 1124.53/292.76 a__primes -> a__sieve(a__from(s(s(0')))) 1124.53/292.76 a__from(X) -> cons(mark(X), from(s(X))) 1124.53/292.76 a__head(cons(X, Y)) -> mark(X) 1124.53/292.76 a__tail(cons(X, Y)) -> mark(Y) 1124.53/292.76 a__if(true, X, Y) -> mark(X) 1124.53/292.76 a__if(false, X, Y) -> mark(Y) 1124.53/292.76 a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) 1124.53/292.76 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 1124.53/292.76 mark(primes) -> a__primes 1124.53/292.76 mark(sieve(X)) -> a__sieve(mark(X)) 1124.53/292.76 mark(from(X)) -> a__from(mark(X)) 1124.53/292.76 mark(head(X)) -> a__head(mark(X)) 1124.53/292.76 mark(tail(X)) -> a__tail(mark(X)) 1124.53/292.76 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1124.53/292.76 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 1124.53/292.76 mark(s(X)) -> s(mark(X)) 1124.53/292.76 mark(0') -> 0' 1124.53/292.76 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1124.53/292.76 mark(true) -> true 1124.53/292.76 mark(false) -> false 1124.53/292.76 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 1124.53/292.76 a__primes -> primes 1124.53/292.76 a__sieve(X) -> sieve(X) 1124.53/292.76 a__from(X) -> from(X) 1124.53/292.76 a__head(X) -> head(X) 1124.53/292.76 a__tail(X) -> tail(X) 1124.53/292.76 a__if(X1, X2, X3) -> if(X1, X2, X3) 1124.53/292.76 a__filter(X1, X2) -> filter(X1, X2) 1124.53/292.76 1124.53/292.76 Types: 1124.53/292.76 a__primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 s :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 0' :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 cons :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 mark :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 true :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 false :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 divides :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 hole_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if1_0 :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0 :: Nat -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 1124.53/292.76 1124.53/292.76 Generator Equations: 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(0) <=> 0' 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(+(x, 1)) <=> s(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(x)) 1124.53/292.76 1124.53/292.76 1124.53/292.76 The following defined symbols remain to be analysed: 1124.53/292.76 mark, a__primes, a__from, a__head, a__tail, a__if 1124.53/292.76 1124.53/292.76 They will be analysed ascendingly in the following order: 1124.53/292.76 a__primes = a__sieve 1124.53/292.76 a__primes = a__from 1124.53/292.76 a__primes = mark 1124.53/292.76 a__primes = a__head 1124.53/292.76 a__primes = a__tail 1124.53/292.76 a__primes = a__if 1124.53/292.76 a__sieve = a__from 1124.53/292.76 a__sieve = mark 1124.53/292.76 a__sieve = a__head 1124.53/292.76 a__sieve = a__tail 1124.53/292.76 a__sieve = a__if 1124.53/292.76 a__from = mark 1124.53/292.76 a__from = a__head 1124.53/292.76 a__from = a__tail 1124.53/292.76 a__from = a__if 1124.53/292.76 mark = a__head 1124.53/292.76 mark = a__tail 1124.53/292.76 mark = a__if 1124.53/292.76 a__head = a__tail 1124.53/292.76 a__head = a__if 1124.53/292.76 a__tail = a__if 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (10) LowerBoundPropagationProof (FINISHED) 1124.53/292.76 Propagated lower bound. 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (11) 1124.53/292.76 BOUNDS(n^1, INF) 1124.53/292.76 1124.53/292.76 ---------------------------------------- 1124.53/292.76 1124.53/292.76 (12) 1124.53/292.76 Obligation: 1124.53/292.76 Innermost TRS: 1124.53/292.76 Rules: 1124.53/292.76 a__primes -> a__sieve(a__from(s(s(0')))) 1124.53/292.76 a__from(X) -> cons(mark(X), from(s(X))) 1124.53/292.76 a__head(cons(X, Y)) -> mark(X) 1124.53/292.76 a__tail(cons(X, Y)) -> mark(Y) 1124.53/292.76 a__if(true, X, Y) -> mark(X) 1124.53/292.76 a__if(false, X, Y) -> mark(Y) 1124.53/292.76 a__filter(s(s(X)), cons(Y, Z)) -> a__if(divides(s(s(mark(X))), mark(Y)), filter(s(s(X)), Z), cons(Y, filter(X, sieve(Y)))) 1124.53/292.76 a__sieve(cons(X, Y)) -> cons(mark(X), filter(X, sieve(Y))) 1124.53/292.76 mark(primes) -> a__primes 1124.53/292.76 mark(sieve(X)) -> a__sieve(mark(X)) 1124.53/292.76 mark(from(X)) -> a__from(mark(X)) 1124.53/292.76 mark(head(X)) -> a__head(mark(X)) 1124.53/292.76 mark(tail(X)) -> a__tail(mark(X)) 1124.53/292.76 mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3) 1124.53/292.76 mark(filter(X1, X2)) -> a__filter(mark(X1), mark(X2)) 1124.53/292.76 mark(s(X)) -> s(mark(X)) 1124.53/292.76 mark(0') -> 0' 1124.53/292.76 mark(cons(X1, X2)) -> cons(mark(X1), X2) 1124.53/292.76 mark(true) -> true 1124.53/292.76 mark(false) -> false 1124.53/292.76 mark(divides(X1, X2)) -> divides(mark(X1), mark(X2)) 1124.53/292.76 a__primes -> primes 1124.53/292.76 a__sieve(X) -> sieve(X) 1124.53/292.76 a__from(X) -> from(X) 1124.53/292.76 a__head(X) -> head(X) 1124.53/292.76 a__tail(X) -> tail(X) 1124.53/292.76 a__if(X1, X2, X3) -> if(X1, X2, X3) 1124.53/292.76 a__filter(X1, X2) -> filter(X1, X2) 1124.53/292.76 1124.53/292.76 Types: 1124.53/292.76 a__primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 s :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 0' :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 cons :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 mark :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 from :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 true :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 false :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 a__filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 divides :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 filter :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 sieve :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 primes :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 head :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 tail :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 if :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 hole_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if1_0 :: 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0 :: Nat -> 0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if 1124.53/292.76 1124.53/292.76 1124.53/292.76 Lemmas: 1124.53/292.76 mark(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(n11_0)) -> gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(n11_0), rt in Omega(1 + n11_0) 1124.53/292.76 1124.53/292.76 1124.53/292.76 Generator Equations: 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(0) <=> 0' 1124.53/292.76 gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(+(x, 1)) <=> s(gen_0':s:from:cons:true:false:divides:filter:sieve:primes:head:tail:if2_0(x)) 1124.53/292.76 1124.53/292.76 1124.53/292.76 The following defined symbols remain to be analysed: 1124.53/292.76 a__primes, a__sieve, a__from, a__head, a__tail, a__if 1124.53/292.76 1124.53/292.76 They will be analysed ascendingly in the following order: 1124.53/292.76 a__primes = a__sieve 1124.53/292.76 a__primes = a__from 1124.53/292.76 a__primes = mark 1124.53/292.76 a__primes = a__head 1124.53/292.76 a__primes = a__tail 1124.53/292.76 a__primes = a__if 1124.53/292.76 a__sieve = a__from 1124.53/292.76 a__sieve = mark 1124.53/292.76 a__sieve = a__head 1124.53/292.76 a__sieve = a__tail 1124.53/292.76 a__sieve = a__if 1124.53/292.76 a__from = mark 1124.53/292.76 a__from = a__head 1124.53/292.76 a__from = a__tail 1124.53/292.76 a__from = a__if 1124.53/292.76 mark = a__head 1124.53/292.76 mark = a__tail 1124.53/292.76 mark = a__if 1124.53/292.76 a__head = a__tail 1124.53/292.76 a__head = a__if 1124.53/292.76 a__tail = a__if 1124.77/292.83 EOF