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