311.15/291.54 KILLED 311.15/291.55 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 311.15/291.55 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 311.15/291.55 311.15/291.55 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 (0) CpxTRS 311.15/291.55 (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 311.15/291.55 (2) CpxTRS 311.15/291.55 (3) SlicingProof [LOWER BOUND(ID), 0 ms] 311.15/291.55 (4) CpxTRS 311.15/291.55 (5) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 311.15/291.55 (6) typed CpxTrs 311.15/291.55 (7) OrderProof [LOWER BOUND(ID), 0 ms] 311.15/291.55 (8) typed CpxTrs 311.15/291.55 (9) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 311.15/291.55 (10) TRS for Loop Detection 311.15/291.55 (11) DependencyGraphProof [UPPER BOUND(ID), 36 ms] 311.15/291.55 (12) CpxTRS 311.15/291.55 (13) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 311.15/291.55 (14) CpxTRS 311.15/291.55 (15) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 311.15/291.55 (16) CpxTRS 311.15/291.55 (17) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms] 311.15/291.55 (18) CpxRelTRS 311.15/291.55 (19) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] 311.15/291.55 (20) CpxWeightedTrs 311.15/291.55 (21) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 311.15/291.55 (22) CpxTypedWeightedTrs 311.15/291.55 (23) CompletionProof [UPPER BOUND(ID), 0 ms] 311.15/291.55 (24) CpxTypedWeightedCompleteTrs 311.15/291.55 (25) NarrowingProof [BOTH BOUNDS(ID, ID), 0 ms] 311.15/291.55 (26) CpxTypedWeightedCompleteTrs 311.15/291.55 (27) CompletionProof [UPPER BOUND(ID), 0 ms] 311.15/291.55 (28) CpxTypedWeightedCompleteTrs 311.15/291.55 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (0) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (1) RenamingProof (BOTH BOUNDS(ID, ID)) 311.15/291.55 Renamed function symbols to avoid clashes with predefined symbol. 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (2) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0')))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (3) SlicingProof (LOWER BOUND(ID)) 311.15/291.55 Sliced the following arguments: 311.15/291.55 divides/0 311.15/291.55 divides/1 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (4) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0')))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides, n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (5) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 311.15/291.55 Infered types. 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (6) 311.15/291.55 Obligation: 311.15/291.55 TRS: 311.15/291.55 Rules: 311.15/291.55 primes -> sieve(from(s(s(0')))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides, n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 Types: 311.15/291.55 primes :: 0':s:n__from:n__filter:n__cons 311.15/291.55 sieve :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 from :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 s :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 0' :: 0':s:n__from:n__filter:n__cons 311.15/291.55 cons :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 n__from :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 head :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 tail :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 activate :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 if :: true:false:divides -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 true :: true:false:divides 311.15/291.55 false :: true:false:divides 311.15/291.55 filter :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 divides :: true:false:divides 311.15/291.55 n__filter :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 n__cons :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 hole_0':s:n__from:n__filter:n__cons1_0 :: 0':s:n__from:n__filter:n__cons 311.15/291.55 hole_true:false:divides2_0 :: true:false:divides 311.15/291.55 gen_0':s:n__from:n__filter:n__cons3_0 :: Nat -> 0':s:n__from:n__filter:n__cons 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (7) OrderProof (LOWER BOUND(ID)) 311.15/291.55 Heuristically decided to analyse the following defined symbols: 311.15/291.55 sieve, activate 311.15/291.55 311.15/291.55 They will be analysed ascendingly in the following order: 311.15/291.55 sieve = activate 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (8) 311.15/291.55 Obligation: 311.15/291.55 TRS: 311.15/291.55 Rules: 311.15/291.55 primes -> sieve(from(s(s(0')))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides, n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 Types: 311.15/291.55 primes :: 0':s:n__from:n__filter:n__cons 311.15/291.55 sieve :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 from :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 s :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 0' :: 0':s:n__from:n__filter:n__cons 311.15/291.55 cons :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 n__from :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 head :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 tail :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 activate :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 if :: true:false:divides -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 true :: true:false:divides 311.15/291.55 false :: true:false:divides 311.15/291.55 filter :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 divides :: true:false:divides 311.15/291.55 n__filter :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 n__cons :: 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons -> 0':s:n__from:n__filter:n__cons 311.15/291.55 hole_0':s:n__from:n__filter:n__cons1_0 :: 0':s:n__from:n__filter:n__cons 311.15/291.55 hole_true:false:divides2_0 :: true:false:divides 311.15/291.55 gen_0':s:n__from:n__filter:n__cons3_0 :: Nat -> 0':s:n__from:n__filter:n__cons 311.15/291.55 311.15/291.55 311.15/291.55 Generator Equations: 311.15/291.55 gen_0':s:n__from:n__filter:n__cons3_0(0) <=> 0' 311.15/291.55 gen_0':s:n__from:n__filter:n__cons3_0(+(x, 1)) <=> n__filter(0', gen_0':s:n__from:n__filter:n__cons3_0(x)) 311.15/291.55 311.15/291.55 311.15/291.55 The following defined symbols remain to be analysed: 311.15/291.55 activate, sieve 311.15/291.55 311.15/291.55 They will be analysed ascendingly in the following order: 311.15/291.55 sieve = activate 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (9) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 311.15/291.55 Transformed a relative TRS into a decreasing-loop problem. 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (10) 311.15/291.55 Obligation: 311.15/291.55 Analyzing the following TRS for decreasing loops: 311.15/291.55 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (11) DependencyGraphProof (UPPER BOUND(ID)) 311.15/291.55 The following rules are not reachable from basic terms in the dependency graph and can be removed: 311.15/291.55 311.15/291.55 head(cons(X, Y)) -> X 311.15/291.55 tail(cons(X, Y)) -> activate(Y) 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (12) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (13) NestedDefinedSymbolProof (UPPER BOUND(ID)) 311.15/291.55 The following defined symbols can occur below the 0th argument of cons: filter, sieve, cons, from, activate 311.15/291.55 The following defined symbols can occur below the 1th argument of cons: filter, sieve, cons, from, activate 311.15/291.55 The following defined symbols can occur below the 0th argument of activate: filter, sieve, cons, from, activate 311.15/291.55 The following defined symbols can occur below the 0th argument of sieve: filter, sieve, cons, from, activate 311.15/291.55 311.15/291.55 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 311.15/291.55 filter(s(s(X)), cons(Y, Z)) -> if(divides(s(s(X)), Y), n__filter(s(s(X)), activate(Z)), n__cons(Y, n__filter(X, sieve(Y)))) 311.15/291.55 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (14) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (15) RelTrsToTrsProof (UPPER BOUND(ID)) 311.15/291.55 transformed relative TRS to TRS 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (16) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 sieve(cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 311.15/291.55 S is empty. 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (17) NonCtorToCtorProof (UPPER BOUND(ID)) 311.15/291.55 transformed non-ctor to ctor-system 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (18) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) 311.15/291.55 from(X) -> cons(X, n__from(s(X))) 311.15/291.55 if(true, X, Y) -> activate(X) 311.15/291.55 if(false, X, Y) -> activate(Y) 311.15/291.55 from(X) -> n__from(X) 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) 311.15/291.55 activate(n__from(X)) -> from(X) 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) 311.15/291.55 activate(X) -> X 311.15/291.55 sieve(c_cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) 311.15/291.55 311.15/291.55 The (relative) TRS S consists of the following rules: 311.15/291.55 311.15/291.55 cons(x0, x1) -> c_cons(x0, x1) 311.15/291.55 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (19) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) 311.15/291.55 Transformed relative TRS to weighted TRS 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (20) 311.15/291.55 Obligation: 311.15/291.55 The Runtime Complexity (full) of the given CpxWeightedTrs could be proven to be BOUNDS(1, INF). 311.15/291.55 311.15/291.55 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) [1] 311.15/291.55 from(X) -> cons(X, n__from(s(X))) [1] 311.15/291.55 if(true, X, Y) -> activate(X) [1] 311.15/291.55 if(false, X, Y) -> activate(Y) [1] 311.15/291.55 from(X) -> n__from(X) [1] 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) [1] 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) [1] 311.15/291.55 activate(n__from(X)) -> from(X) [1] 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) [1] 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) [1] 311.15/291.55 activate(X) -> X [1] 311.15/291.55 sieve(c_cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) [1] 311.15/291.55 cons(x0, x1) -> c_cons(x0, x1) [0] 311.15/291.55 311.15/291.55 Rewrite Strategy: FULL 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (21) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 311.15/291.55 Infered types. 311.15/291.55 ---------------------------------------- 311.15/291.55 311.15/291.55 (22) 311.15/291.55 Obligation: 311.15/291.55 Runtime Complexity Weighted TRS with Types. 311.15/291.55 The TRS R consists of the following rules: 311.15/291.55 311.15/291.55 primes -> sieve(from(s(s(0)))) [1] 311.15/291.55 from(X) -> cons(X, n__from(s(X))) [1] 311.15/291.55 if(true, X, Y) -> activate(X) [1] 311.15/291.55 if(false, X, Y) -> activate(Y) [1] 311.15/291.55 from(X) -> n__from(X) [1] 311.15/291.55 filter(X1, X2) -> n__filter(X1, X2) [1] 311.15/291.55 cons(X1, X2) -> n__cons(X1, X2) [1] 311.15/291.55 activate(n__from(X)) -> from(X) [1] 311.15/291.55 activate(n__filter(X1, X2)) -> filter(X1, X2) [1] 311.15/291.55 activate(n__cons(X1, X2)) -> cons(X1, X2) [1] 311.15/291.55 activate(X) -> X [1] 311.15/291.55 sieve(c_cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) [1] 311.15/291.55 cons(x0, x1) -> c_cons(x0, x1) [0] 311.15/291.55 311.15/291.55 The TRS has the following type information: 311.15/291.55 primes :: n__from:n__filter:n__cons:c_cons 311.15/291.55 sieve :: n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.55 from :: 0:s -> n__from:n__filter:n__cons:c_cons 311.15/291.55 s :: 0:s -> 0:s 311.15/291.55 0 :: 0:s 311.15/291.55 cons :: 0:s -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.55 n__from :: 0:s -> n__from:n__filter:n__cons:c_cons 311.15/291.56 if :: true:false -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.56 true :: true:false 311.15/291.56 activate :: n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.56 false :: true:false 311.15/291.56 filter :: 0:s -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.56 n__filter :: 0:s -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.56 n__cons :: 0:s -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.56 c_cons :: 0:s -> n__from:n__filter:n__cons:c_cons -> n__from:n__filter:n__cons:c_cons 311.15/291.56 311.15/291.56 Rewrite Strategy: FULL 311.15/291.56 ---------------------------------------- 311.15/291.56 311.15/291.56 (23) CompletionProof (UPPER BOUND(ID)) 311.15/291.56 The transformation into a RNTS is sound, since: 311.15/291.56 311.15/291.56 (a) The obligation is a constructor system where every type has a constant constructor, 311.15/291.56 311.15/291.56 (b) The following defined symbols do not have to be completely defined, as they can never occur inside other defined symbols: 311.15/291.56 311.15/291.56 primes 311.15/291.56 if_3 311.15/291.56 311.15/291.56 (c) The following functions are completely defined: 311.15/291.56 311.15/291.56 from_1 311.15/291.56 sieve_1 311.15/291.56 activate_1 311.15/291.56 filter_2 311.15/291.56 cons_2 311.15/291.56 311.15/291.56 Due to the following rules being added: 311.15/291.56 311.15/291.56 cons(v0, v1) -> const [0] 311.15/291.56 sieve(v0) -> const [0] 311.15/291.56 311.15/291.56 And the following fresh constants: const 311.15/291.56 311.15/291.56 ---------------------------------------- 311.15/291.56 311.15/291.56 (24) 311.15/291.56 Obligation: 311.15/291.56 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 311.15/291.56 311.15/291.56 Runtime Complexity Weighted TRS with Types. 311.15/291.56 The TRS R consists of the following rules: 311.15/291.56 311.15/291.56 primes -> sieve(from(s(s(0)))) [1] 311.15/291.56 from(X) -> cons(X, n__from(s(X))) [1] 311.15/291.56 if(true, X, Y) -> activate(X) [1] 311.15/291.56 if(false, X, Y) -> activate(Y) [1] 311.15/291.56 from(X) -> n__from(X) [1] 311.15/291.56 filter(X1, X2) -> n__filter(X1, X2) [1] 311.15/291.56 cons(X1, X2) -> n__cons(X1, X2) [1] 311.15/291.56 activate(n__from(X)) -> from(X) [1] 311.15/291.56 activate(n__filter(X1, X2)) -> filter(X1, X2) [1] 311.15/291.56 activate(n__cons(X1, X2)) -> cons(X1, X2) [1] 311.15/291.56 activate(X) -> X [1] 311.15/291.56 sieve(c_cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) [1] 311.15/291.56 cons(x0, x1) -> c_cons(x0, x1) [0] 311.15/291.56 cons(v0, v1) -> const [0] 311.15/291.56 sieve(v0) -> const [0] 311.15/291.56 311.15/291.56 The TRS has the following type information: 311.15/291.56 primes :: n__from:n__filter:n__cons:c_cons:const 311.15/291.56 sieve :: n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 from :: 0:s -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 s :: 0:s -> 0:s 311.15/291.56 0 :: 0:s 311.15/291.56 cons :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 n__from :: 0:s -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 if :: true:false -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 true :: true:false 311.15/291.56 activate :: n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 false :: true:false 311.15/291.56 filter :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 n__filter :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 n__cons :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 c_cons :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 const :: n__from:n__filter:n__cons:c_cons:const 311.15/291.56 311.15/291.56 Rewrite Strategy: FULL 311.15/291.56 ---------------------------------------- 311.15/291.56 311.15/291.56 (25) NarrowingProof (BOTH BOUNDS(ID, ID)) 311.15/291.56 Narrowed the inner basic terms of all right-hand sides by a single narrowing step. 311.15/291.56 ---------------------------------------- 311.15/291.56 311.15/291.56 (26) 311.15/291.56 Obligation: 311.15/291.56 Runtime Complexity Weighted TRS where critical functions are completely defined. The underlying TRS is: 311.15/291.56 311.15/291.56 Runtime Complexity Weighted TRS with Types. 311.15/291.56 The TRS R consists of the following rules: 311.15/291.56 311.15/291.56 primes -> sieve(cons(s(s(0)), n__from(s(s(s(0)))))) [2] 311.15/291.56 primes -> sieve(n__from(s(s(0)))) [2] 311.15/291.56 from(X) -> cons(X, n__from(s(X))) [1] 311.15/291.56 if(true, X, Y) -> activate(X) [1] 311.15/291.56 if(false, X, Y) -> activate(Y) [1] 311.15/291.56 from(X) -> n__from(X) [1] 311.15/291.56 filter(X1, X2) -> n__filter(X1, X2) [1] 311.15/291.56 cons(X1, X2) -> n__cons(X1, X2) [1] 311.15/291.56 activate(n__from(X)) -> from(X) [1] 311.15/291.56 activate(n__filter(X1, X2)) -> filter(X1, X2) [1] 311.15/291.56 activate(n__cons(X1, X2)) -> cons(X1, X2) [1] 311.15/291.56 activate(X) -> X [1] 311.15/291.56 sieve(c_cons(X, n__from(X'))) -> cons(X, n__filter(X, sieve(from(X')))) [2] 311.15/291.56 sieve(c_cons(X, n__filter(X1', X2'))) -> cons(X, n__filter(X, sieve(filter(X1', X2')))) [2] 311.15/291.56 sieve(c_cons(X, n__cons(X1'', X2''))) -> cons(X, n__filter(X, sieve(cons(X1'', X2'')))) [2] 311.15/291.56 sieve(c_cons(X, Y)) -> cons(X, n__filter(X, sieve(Y))) [2] 311.15/291.56 cons(x0, x1) -> c_cons(x0, x1) [0] 311.15/291.56 cons(v0, v1) -> const [0] 311.15/291.56 sieve(v0) -> const [0] 311.15/291.56 311.15/291.56 The TRS has the following type information: 311.15/291.56 primes :: n__from:n__filter:n__cons:c_cons:const 311.15/291.56 sieve :: n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 from :: 0:s -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 s :: 0:s -> 0:s 311.15/291.56 0 :: 0:s 311.15/291.56 cons :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 n__from :: 0:s -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 if :: true:false -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 true :: true:false 311.15/291.56 activate :: n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 false :: true:false 311.15/291.56 filter :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 n__filter :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 n__cons :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 c_cons :: 0:s -> n__from:n__filter:n__cons:c_cons:const -> n__from:n__filter:n__cons:c_cons:const 311.15/291.56 const :: n__from:n__filter:n__cons:c_cons:const 311.15/291.56 311.15/291.56 Rewrite Strategy: FULL 311.15/291.56 ---------------------------------------- 311.15/291.56 311.15/291.56 (27) CompletionProof (UPPER BOUND(ID)) 311.15/291.56 The TRS is a completely defined constructor system, as every type has a constant constructor and the following rules were added: 311.15/291.56 311.15/291.56 cons(v0, v1) -> null_cons [0] 311.15/291.56 sieve(v0) -> null_sieve [0] 311.15/291.56 311.15/291.56 And the following fresh constants: null_cons, null_sieve 311.15/291.56 311.15/291.56 ---------------------------------------- 311.15/291.56 311.15/291.56 (28) 311.15/291.56 Obligation: 311.15/291.56 Runtime Complexity Weighted TRS where all functions are completely defined. The underlying TRS is: 311.15/291.56 311.15/291.56 Runtime Complexity Weighted TRS with Types. 311.15/291.56 The TRS R consists of the following rules: 311.15/291.56 311.15/291.56 primes -> sieve(from(s(s(0)))) [1] 311.15/291.56 from(X) -> cons(X, n__from(s(X))) [1] 311.15/291.56 if(true, X, Y) -> activate(X) [1] 311.15/291.56 if(false, X, Y) -> activate(Y) [1] 311.15/291.56 from(X) -> n__from(X) [1] 311.15/291.56 filter(X1, X2) -> n__filter(X1, X2) [1] 311.15/291.56 cons(X1, X2) -> n__cons(X1, X2) [1] 311.15/291.56 activate(n__from(X)) -> from(X) [1] 311.15/291.56 activate(n__filter(X1, X2)) -> filter(X1, X2) [1] 311.15/291.56 activate(n__cons(X1, X2)) -> cons(X1, X2) [1] 311.15/291.56 activate(X) -> X [1] 311.15/291.56 sieve(c_cons(X, Y)) -> cons(X, n__filter(X, sieve(activate(Y)))) [1] 311.15/291.56 cons(x0, x1) -> c_cons(x0, x1) [0] 311.15/291.56 cons(v0, v1) -> null_cons [0] 311.15/291.56 sieve(v0) -> null_sieve [0] 311.15/291.56 311.15/291.56 The TRS has the following type information: 311.15/291.56 primes :: n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 sieve :: n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 from :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 s :: 0:s -> 0:s 311.15/291.56 0 :: 0:s 311.15/291.56 cons :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 n__from :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 if :: true:false -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 true :: true:false 311.15/291.56 activate :: n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 false :: true:false 311.15/291.56 filter :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 n__filter :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 n__cons :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 c_cons :: 0:s -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve -> n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 null_cons :: n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 null_sieve :: n__from:n__filter:n__cons:c_cons:null_cons:null_sieve 311.15/291.56 311.15/291.56 Rewrite Strategy: FULL 311.27/291.59 EOF