/export/starexec/sandbox2/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 237 ms] (4) CpxRelTRS (5) NonCtorToCtorProof [UPPER BOUND(ID), 0 ms] (6) CpxRelTRS (7) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxRelTRS (9) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxWeightedTrs (11) CpxWeightedTrsRenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CpxWeightedTrs (13) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (14) CpxTypedWeightedTrs (15) CompletionProof [UPPER BOUND(ID), 0 ms] (16) CpxTypedWeightedCompleteTrs (17) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 5 ms] (18) CpxRNTS (19) CompleteCoflocoProof [FINISHED, 785 ms] (20) BOUNDS(1, n^2) (21) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (22) TRS for Loop Detection (23) DecreasingLoopProof [LOWER BOUND(ID), 5 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^1, INF) (28) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: f(0) -> cons(0, n__f(n__s(n__0))) f(s(0)) -> f(p(s(0))) p(s(0)) -> 0 f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) DerivationalComplexityToRuntimeComplexityProof (BOTH BOUNDS(ID, ID)) The following rules have been added to S to convert the given derivational complexity problem to a runtime complexity problem: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: f(0) -> cons(0, n__f(n__s(n__0))) f(s(0)) -> f(p(s(0))) p(s(0)) -> 0 f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: f(0) -> cons(0, n__f(n__s(n__0))) f(s(0)) -> f(p(s(0))) p(s(0)) -> 0 f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (5) NonCtorToCtorProof (UPPER BOUND(ID)) transformed non-ctor to ctor-system ---------------------------------------- (6) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X f(c_0) -> cons(0, n__f(n__s(n__0))) f(c_s(c_0)) -> f(p(s(0))) p(c_s(c_0)) -> 0 The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) s(x0) -> c_s(x0) 0 -> c_0 Rewrite Strategy: FULL ---------------------------------------- (7) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, we have rc = irc. ---------------------------------------- (8) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X f(c_0) -> cons(0, n__f(n__s(n__0))) f(c_s(c_0)) -> f(p(s(0))) p(c_s(c_0)) -> 0 The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) s(x0) -> c_s(x0) 0 -> c_0 Rewrite Strategy: INNERMOST ---------------------------------------- (9) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (10) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: f(X) -> n__f(X) [1] s(X) -> n__s(X) [1] 0 -> n__0 [1] activate(n__f(X)) -> f(activate(X)) [1] activate(n__s(X)) -> s(activate(X)) [1] activate(n__0) -> 0 [1] activate(X) -> X [1] f(c_0) -> cons(0, n__f(n__s(n__0))) [1] f(c_s(c_0)) -> f(p(s(0))) [1] p(c_s(c_0)) -> 0 [1] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0] encArg(n__s(x_1)) -> n__s(encArg(x_1)) [0] encArg(n__0) -> n__0 [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_0) -> 0 [0] encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0 [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_n__f(x_1) -> n__f(encArg(x_1)) [0] encode_n__s(x_1) -> n__s(encArg(x_1)) [0] encode_n__0 -> n__0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_activate(x_1) -> activate(encArg(x_1)) [0] s(x0) -> c_s(x0) [0] 0 -> c_0 [0] Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) Renamed defined symbols to avoid conflicts with arithmetic symbols: 0 => 0' ---------------------------------------- (12) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: f(X) -> n__f(X) [1] s(X) -> n__s(X) [1] 0' -> n__0 [1] activate(n__f(X)) -> f(activate(X)) [1] activate(n__s(X)) -> s(activate(X)) [1] activate(n__0) -> 0' [1] activate(X) -> X [1] f(c_0) -> cons(0', n__f(n__s(n__0))) [1] f(c_s(c_0)) -> f(p(s(0'))) [1] p(c_s(c_0)) -> 0' [1] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0] encArg(n__s(x_1)) -> n__s(encArg(x_1)) [0] encArg(n__0) -> n__0 [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_0) -> 0' [0] encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0' [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_n__f(x_1) -> n__f(encArg(x_1)) [0] encode_n__s(x_1) -> n__s(encArg(x_1)) [0] encode_n__0 -> n__0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_activate(x_1) -> activate(encArg(x_1)) [0] s(x0) -> c_s(x0) [0] 0' -> c_0 [0] Rewrite Strategy: INNERMOST ---------------------------------------- (13) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (14) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: f(X) -> n__f(X) [1] s(X) -> n__s(X) [1] 0' -> n__0 [1] activate(n__f(X)) -> f(activate(X)) [1] activate(n__s(X)) -> s(activate(X)) [1] activate(n__0) -> 0' [1] activate(X) -> X [1] f(c_0) -> cons(0', n__f(n__s(n__0))) [1] f(c_s(c_0)) -> f(p(s(0'))) [1] p(c_s(c_0)) -> 0' [1] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0] encArg(n__s(x_1)) -> n__s(encArg(x_1)) [0] encArg(n__0) -> n__0 [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_0) -> 0' [0] encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0' [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_n__f(x_1) -> n__f(encArg(x_1)) [0] encode_n__s(x_1) -> n__s(encArg(x_1)) [0] encode_n__0 -> n__0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_activate(x_1) -> activate(encArg(x_1)) [0] s(x0) -> c_s(x0) [0] 0' -> c_0 [0] The TRS has the following type information: f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate n__f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate n__s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate 0' :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate n__0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate c_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate cons :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate c_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encArg :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate cons_f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate cons_p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate cons_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate cons_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate cons_activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_cons :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_n__f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_n__s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_n__0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate encode_activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate Rewrite Strategy: INNERMOST ---------------------------------------- (15) 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: encArg(v0) -> null_encArg [0] encode_f(v0) -> null_encode_f [0] encode_0 -> null_encode_0 [0] encode_cons(v0, v1) -> null_encode_cons [0] encode_n__f(v0) -> null_encode_n__f [0] encode_n__s(v0) -> null_encode_n__s [0] encode_n__0 -> null_encode_n__0 [0] encode_s(v0) -> null_encode_s [0] encode_p(v0) -> null_encode_p [0] encode_activate(v0) -> null_encode_activate [0] s(v0) -> null_s [0] 0' -> null_0' [0] p(v0) -> null_p [0] And the following fresh constants: null_encArg, null_encode_f, null_encode_0, null_encode_cons, null_encode_n__f, null_encode_n__s, null_encode_n__0, null_encode_s, null_encode_p, null_encode_activate, null_s, null_0', null_p ---------------------------------------- (16) 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: f(X) -> n__f(X) [1] s(X) -> n__s(X) [1] 0' -> n__0 [1] activate(n__f(X)) -> f(activate(X)) [1] activate(n__s(X)) -> s(activate(X)) [1] activate(n__0) -> 0' [1] activate(X) -> X [1] f(c_0) -> cons(0', n__f(n__s(n__0))) [1] f(c_s(c_0)) -> f(p(s(0'))) [1] p(c_s(c_0)) -> 0' [1] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(n__f(x_1)) -> n__f(encArg(x_1)) [0] encArg(n__s(x_1)) -> n__s(encArg(x_1)) [0] encArg(n__0) -> n__0 [0] encArg(cons_f(x_1)) -> f(encArg(x_1)) [0] encArg(cons_p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_s(x_1)) -> s(encArg(x_1)) [0] encArg(cons_0) -> 0' [0] encArg(cons_activate(x_1)) -> activate(encArg(x_1)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_0 -> 0' [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_n__f(x_1) -> n__f(encArg(x_1)) [0] encode_n__s(x_1) -> n__s(encArg(x_1)) [0] encode_n__0 -> n__0 [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encode_activate(x_1) -> activate(encArg(x_1)) [0] s(x0) -> c_s(x0) [0] 0' -> c_0 [0] encArg(v0) -> null_encArg [0] encode_f(v0) -> null_encode_f [0] encode_0 -> null_encode_0 [0] encode_cons(v0, v1) -> null_encode_cons [0] encode_n__f(v0) -> null_encode_n__f [0] encode_n__s(v0) -> null_encode_n__s [0] encode_n__0 -> null_encode_n__0 [0] encode_s(v0) -> null_encode_s [0] encode_p(v0) -> null_encode_p [0] encode_activate(v0) -> null_encode_activate [0] s(v0) -> null_s [0] 0' -> null_0' [0] p(v0) -> null_p [0] The TRS has the following type information: f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p n__f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p n__s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p 0' :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p n__0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p c_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p cons :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p c_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encArg :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p cons_f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p cons_p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p cons_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p cons_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p cons_activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_cons :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_n__f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_n__s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_n__0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p encode_activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p -> n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encArg :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_cons :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_n__f :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_n__s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_n__0 :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_encode_activate :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_s :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_0' :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p null_p :: n__f:n__s:n__0:c_0:cons:c_s:cons_f:cons_p:cons_s:cons_0:cons_activate:null_encArg:null_encode_f:null_encode_0:null_encode_cons:null_encode_n__f:null_encode_n__s:null_encode_n__0:null_encode_s:null_encode_p:null_encode_activate:null_s:null_0':null_p Rewrite Strategy: INNERMOST ---------------------------------------- (17) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: n__0 => 2 c_0 => 0 cons_0 => 1 null_encArg => 0 null_encode_f => 0 null_encode_0 => 0 null_encode_cons => 0 null_encode_n__f => 0 null_encode_n__s => 0 null_encode_n__0 => 0 null_encode_s => 0 null_encode_p => 0 null_encode_activate => 0 null_s => 0 null_0' => 0 null_p => 0 ---------------------------------------- (18) Obligation: Complexity RNTS consisting of the following rules: 0' -{ 1 }-> 2 :|: 0' -{ 0 }-> 0 :|: activate(z) -{ 1 }-> X :|: X >= 0, z = X activate(z) -{ 1 }-> s(activate(X)) :|: z = 1 + X, X >= 0 activate(z) -{ 1 }-> f(activate(X)) :|: z = 1 + X, X >= 0 activate(z) -{ 1 }-> 0' :|: z = 2 encArg(z) -{ 0 }-> s(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> p(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> f(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> activate(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> 2 :|: z = 2 encArg(z) -{ 0 }-> 0' :|: z = 1 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> 1 + encArg(x_1) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_0 -{ 0 }-> 0' :|: encode_0 -{ 0 }-> 0 :|: encode_activate(z) -{ 0 }-> activate(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_activate(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_cons(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_cons(z, z') -{ 0 }-> 1 + encArg(x_1) + encArg(x_2) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_f(z) -{ 0 }-> f(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_n__0 -{ 0 }-> 2 :|: encode_n__0 -{ 0 }-> 0 :|: encode_n__f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_n__f(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_n__s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_n__s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_p(z) -{ 0 }-> p(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> s(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 f(z) -{ 1 }-> f(p(s(0'))) :|: z = 1 + 0 f(z) -{ 1 }-> 1 + X :|: X >= 0, z = X f(z) -{ 1 }-> 1 + 0' + (1 + (1 + 2)) :|: z = 0 p(z) -{ 1 }-> 0' :|: z = 1 + 0 p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 s(z) -{ 1 }-> 1 + X :|: X >= 0, z = X s(z) -{ 0 }-> 1 + x0 :|: z = x0, x0 >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (19) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V, V9),0,[f(V, Out)],[V >= 0]). eq(start(V, V9),0,[s(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun(Out)],[]). eq(start(V, V9),0,[activate(V, Out)],[V >= 0]). eq(start(V, V9),0,[p(V, Out)],[V >= 0]). eq(start(V, V9),0,[encArg(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun1(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun2(Out)],[]). eq(start(V, V9),0,[fun3(V, V9, Out)],[V >= 0,V9 >= 0]). eq(start(V, V9),0,[fun4(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun5(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun6(Out)],[]). eq(start(V, V9),0,[fun7(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun8(V, Out)],[V >= 0]). eq(start(V, V9),0,[fun9(V, Out)],[V >= 0]). eq(f(V, Out),1,[],[Out = 1 + X1,X1 >= 0,V = X1]). eq(s(V, Out),1,[],[Out = 1 + X2,X2 >= 0,V = X2]). eq(fun(Out),1,[],[Out = 2]). eq(activate(V, Out),1,[activate(X3, Ret0),f(Ret0, Ret)],[Out = Ret,V = 1 + X3,X3 >= 0]). eq(activate(V, Out),1,[activate(X4, Ret01),s(Ret01, Ret1)],[Out = Ret1,V = 1 + X4,X4 >= 0]). eq(activate(V, Out),1,[fun(Ret2)],[Out = Ret2,V = 2]). eq(activate(V, Out),1,[],[Out = X5,X5 >= 0,V = X5]). eq(f(V, Out),1,[fun(Ret011)],[Out = 5 + Ret011,V = 0]). eq(f(V, Out),1,[fun(Ret000),s(Ret000, Ret00),p(Ret00, Ret02),f(Ret02, Ret3)],[Out = Ret3,V = 1]). eq(p(V, Out),1,[fun(Ret4)],[Out = Ret4,V = 1]). eq(encArg(V, Out),0,[encArg(V2, Ret012),encArg(V1, Ret11)],[Out = 1 + Ret012 + Ret11,V2 >= 0,V = 1 + V1 + V2,V1 >= 0]). eq(encArg(V, Out),0,[encArg(V3, Ret12)],[Out = 1 + Ret12,V = 1 + V3,V3 >= 0]). eq(encArg(V, Out),0,[],[Out = 2,V = 2]). eq(encArg(V, Out),0,[encArg(V4, Ret03),f(Ret03, Ret5)],[Out = Ret5,V = 1 + V4,V4 >= 0]). eq(encArg(V, Out),0,[encArg(V5, Ret04),p(Ret04, Ret6)],[Out = Ret6,V = 1 + V5,V5 >= 0]). eq(encArg(V, Out),0,[encArg(V6, Ret05),s(Ret05, Ret7)],[Out = Ret7,V = 1 + V6,V6 >= 0]). eq(encArg(V, Out),0,[fun(Ret8)],[Out = Ret8,V = 1]). eq(encArg(V, Out),0,[encArg(V7, Ret06),activate(Ret06, Ret9)],[Out = Ret9,V = 1 + V7,V7 >= 0]). eq(fun1(V, Out),0,[encArg(V8, Ret07),f(Ret07, Ret10)],[Out = Ret10,V8 >= 0,V = V8]). eq(fun2(Out),0,[fun(Ret13)],[Out = Ret13]). eq(fun3(V, V9, Out),0,[encArg(V11, Ret013),encArg(V10, Ret14)],[Out = 1 + Ret013 + Ret14,V11 >= 0,V10 >= 0,V = V11,V9 = V10]). eq(fun4(V, Out),0,[encArg(V12, Ret15)],[Out = 1 + Ret15,V12 >= 0,V = V12]). eq(fun5(V, Out),0,[encArg(V13, Ret16)],[Out = 1 + Ret16,V13 >= 0,V = V13]). eq(fun6(Out),0,[],[Out = 2]). eq(fun7(V, Out),0,[encArg(V14, Ret08),s(Ret08, Ret17)],[Out = Ret17,V14 >= 0,V = V14]). eq(fun8(V, Out),0,[encArg(V15, Ret09),p(Ret09, Ret18)],[Out = Ret18,V15 >= 0,V = V15]). eq(fun9(V, Out),0,[encArg(V16, Ret010),activate(Ret010, Ret19)],[Out = Ret19,V16 >= 0,V = V16]). eq(s(V, Out),0,[],[Out = 1 + V17,V = V17,V17 >= 0]). eq(fun(Out),0,[],[Out = 0]). eq(encArg(V, Out),0,[],[Out = 0,V18 >= 0,V = V18]). eq(fun1(V, Out),0,[],[Out = 0,V19 >= 0,V = V19]). eq(fun2(Out),0,[],[Out = 0]). eq(fun3(V, V9, Out),0,[],[Out = 0,V21 >= 0,V20 >= 0,V = V21,V9 = V20]). eq(fun4(V, Out),0,[],[Out = 0,V22 >= 0,V = V22]). eq(fun5(V, Out),0,[],[Out = 0,V23 >= 0,V = V23]). eq(fun6(Out),0,[],[Out = 0]). eq(fun7(V, Out),0,[],[Out = 0,V24 >= 0,V = V24]). eq(fun8(V, Out),0,[],[Out = 0,V25 >= 0,V = V25]). eq(fun9(V, Out),0,[],[Out = 0,V26 >= 0,V = V26]). eq(s(V, Out),0,[],[Out = 0,V27 >= 0,V = V27]). eq(p(V, Out),0,[],[Out = 0,V28 >= 0,V = V28]). input_output_vars(f(V,Out),[V],[Out]). input_output_vars(s(V,Out),[V],[Out]). input_output_vars(fun(Out),[],[Out]). input_output_vars(activate(V,Out),[V],[Out]). input_output_vars(p(V,Out),[V],[Out]). input_output_vars(encArg(V,Out),[V],[Out]). input_output_vars(fun1(V,Out),[V],[Out]). input_output_vars(fun2(Out),[],[Out]). input_output_vars(fun3(V,V9,Out),[V,V9],[Out]). input_output_vars(fun4(V,Out),[V],[Out]). input_output_vars(fun5(V,Out),[V],[Out]). input_output_vars(fun6(Out),[],[Out]). input_output_vars(fun7(V,Out),[V],[Out]). input_output_vars(fun8(V,Out),[V],[Out]). input_output_vars(fun9(V,Out),[V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. non_recursive : [fun/1] 1. non_recursive : [p/2] 2. non_recursive : [s/2] 3. recursive : [f/2] 4. recursive [non_tail] : [activate/2] 5. recursive [non_tail,multiple] : [encArg/2] 6. non_recursive : [fun1/2] 7. non_recursive : [fun2/1] 8. non_recursive : [fun3/3] 9. non_recursive : [fun4/2] 10. non_recursive : [fun5/2] 11. non_recursive : [fun6/1] 12. non_recursive : [fun7/2] 13. non_recursive : [fun8/2] 14. non_recursive : [fun9/2] 15. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun/1 1. SCC is partially evaluated into p/2 2. SCC is partially evaluated into s/2 3. SCC is partially evaluated into f/2 4. SCC is partially evaluated into activate/2 5. SCC is partially evaluated into encArg/2 6. SCC is partially evaluated into fun1/2 7. SCC is partially evaluated into fun2/1 8. SCC is partially evaluated into fun3/3 9. SCC is partially evaluated into fun4/2 10. SCC is partially evaluated into fun5/2 11. SCC is partially evaluated into fun6/1 12. SCC is partially evaluated into fun7/2 13. SCC is partially evaluated into fun8/2 14. SCC is partially evaluated into fun9/2 15. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun/1 * CE 22 is refined into CE [57] * CE 23 is refined into CE [58] ### Cost equations --> "Loop" of fun/1 * CEs [57] --> Loop 29 * CEs [58] --> Loop 30 ### Ranking functions of CR fun(Out) #### Partial ranking functions of CR fun(Out) ### Specialization of cost equations p/2 * CE 29 is refined into CE [59] * CE 28 is refined into CE [60,61] ### Cost equations --> "Loop" of p/2 * CEs [61] --> Loop 31 * CEs [59,60] --> Loop 32 ### Ranking functions of CR p(V,Out) #### Partial ranking functions of CR p(V,Out) ### Specialization of cost equations s/2 * CE 19 is refined into CE [62] * CE 20 is refined into CE [63] * CE 21 is refined into CE [64] ### Cost equations --> "Loop" of s/2 * CEs [62,63] --> Loop 33 * CEs [64] --> Loop 34 ### Ranking functions of CR s(V,Out) #### Partial ranking functions of CR s(V,Out) ### Specialization of cost equations f/2 * CE 18 is refined into CE [65,66,67,68,69] * CE 16 is refined into CE [70] * CE 17 is refined into CE [71,72] ### Cost equations --> "Loop" of f/2 * CEs [70] --> Loop 35 * CEs [72] --> Loop 36 * CEs [71] --> Loop 37 * CEs [66] --> Loop 38 * CEs [65,67,68,69] --> Loop 39 ### Ranking functions of CR f(V,Out) #### Partial ranking functions of CR f(V,Out) ### Specialization of cost equations activate/2 * CE 27 is refined into CE [73] * CE 26 is refined into CE [74,75] * CE 24 is refined into CE [76,77,78,79,80,81,82] * CE 25 is refined into CE [83,84] ### Cost equations --> "Loop" of activate/2 * CEs [82,84] --> Loop 40 * CEs [81] --> Loop 41 * CEs [77] --> Loop 42 * CEs [80] --> Loop 43 * CEs [76] --> Loop 44 * CEs [79] --> Loop 45 * CEs [78] --> Loop 46 * CEs [83] --> Loop 47 * CEs [73,75] --> Loop 48 * CEs [74] --> Loop 49 ### Ranking functions of CR activate(V,Out) * RF of phase [40,41,42,43,44,45,46,47]: [V] #### Partial ranking functions of CR activate(V,Out) * Partial RF of phase [40,41,42,43,44,45,46,47]: - RF of loop [40:1,41:1,42:1,43:1,44:1,45:1,46:1,47:1]: V ### Specialization of cost equations encArg/2 * CE 38 is refined into CE [85] * CE 32 is refined into CE [86] * CE 36 is refined into CE [87,88] * CE 31 is refined into CE [89] * CE 33 is refined into CE [90,91,92,93,94,95,96] * CE 34 is refined into CE [97,98] * CE 35 is refined into CE [99,100] * CE 37 is refined into CE [101,102] * CE 30 is refined into CE [103] ### Cost equations --> "Loop" of encArg/2 * CEs [103] --> Loop 50 * CEs [95] --> Loop 51 * CEs [91] --> Loop 52 * CEs [94] --> Loop 53 * CEs [90] --> Loop 54 * CEs [93,101] --> Loop 55 * CEs [89,96,97,100] --> Loop 56 * CEs [92,102] --> Loop 57 * CEs [98,99] --> Loop 58 * CEs [86] --> Loop 59 * CEs [88] --> Loop 60 * CEs [85,87] --> Loop 61 ### Ranking functions of CR encArg(V,Out) * RF of phase [50,51,52,53,54,55,56,57,58]: [V] #### Partial ranking functions of CR encArg(V,Out) * Partial RF of phase [50,51,52,53,54,55,56,57,58]: - RF of loop [50:1,50:2,51:1,52:1,53:1,54:1,55:1,56:1,57:1,58:1]: V ### Specialization of cost equations fun1/2 * CE 39 is refined into CE [104,105,106,107,108,109,110,111,112,113,114] * CE 40 is refined into CE [115] ### Cost equations --> "Loop" of fun1/2 * CEs [105,109,113] --> Loop 62 * CEs [104,108,112] --> Loop 63 * CEs [106,114] --> Loop 64 * CEs [115] --> Loop 65 * CEs [107,110,111] --> Loop 66 ### Ranking functions of CR fun1(V,Out) #### Partial ranking functions of CR fun1(V,Out) ### Specialization of cost equations fun2/1 * CE 41 is refined into CE [116,117] * CE 42 is refined into CE [118] ### Cost equations --> "Loop" of fun2/1 * CEs [117] --> Loop 67 * CEs [116,118] --> Loop 68 ### Ranking functions of CR fun2(Out) #### Partial ranking functions of CR fun2(Out) ### Specialization of cost equations fun3/3 * CE 43 is refined into CE [119,120,121,122,123,124,125,126,127] * CE 44 is refined into CE [128] ### Cost equations --> "Loop" of fun3/3 * CEs [127] --> Loop 69 * CEs [128] --> Loop 70 * CEs [120] --> Loop 71 * CEs [125,126] --> Loop 72 * CEs [121,124] --> Loop 73 * CEs [119,122,123] --> Loop 74 ### Ranking functions of CR fun3(V,V9,Out) #### Partial ranking functions of CR fun3(V,V9,Out) ### Specialization of cost equations fun4/2 * CE 45 is refined into CE [129,130,131] * CE 46 is refined into CE [132] ### Cost equations --> "Loop" of fun4/2 * CEs [131] --> Loop 75 * CEs [132] --> Loop 76 * CEs [129,130] --> Loop 77 ### Ranking functions of CR fun4(V,Out) #### Partial ranking functions of CR fun4(V,Out) ### Specialization of cost equations fun5/2 * CE 47 is refined into CE [133,134,135] * CE 48 is refined into CE [136] ### Cost equations --> "Loop" of fun5/2 * CEs [135] --> Loop 78 * CEs [136] --> Loop 79 * CEs [133,134] --> Loop 80 ### Ranking functions of CR fun5(V,Out) #### Partial ranking functions of CR fun5(V,Out) ### Specialization of cost equations fun6/1 * CE 49 is refined into CE [137] * CE 50 is refined into CE [138] ### Cost equations --> "Loop" of fun6/1 * CEs [137] --> Loop 81 * CEs [138] --> Loop 82 ### Ranking functions of CR fun6(Out) #### Partial ranking functions of CR fun6(Out) ### Specialization of cost equations fun7/2 * CE 51 is refined into CE [139,140,141,142,143,144] * CE 52 is refined into CE [145] ### Cost equations --> "Loop" of fun7/2 * CEs [144] --> Loop 83 * CEs [140,142] --> Loop 84 * CEs [139,141,143,145] --> Loop 85 ### Ranking functions of CR fun7(V,Out) #### Partial ranking functions of CR fun7(V,Out) ### Specialization of cost equations fun8/2 * CE 53 is refined into CE [146,147,148,149] * CE 54 is refined into CE [150] ### Cost equations --> "Loop" of fun8/2 * CEs [146] --> Loop 86 * CEs [147,148,149,150] --> Loop 87 ### Ranking functions of CR fun8(V,Out) #### Partial ranking functions of CR fun8(V,Out) ### Specialization of cost equations fun9/2 * CE 55 is refined into CE [151,152,153,154,155] * CE 56 is refined into CE [156] ### Cost equations --> "Loop" of fun9/2 * CEs [155,156] --> Loop 88 * CEs [151,152,153,154] --> Loop 89 ### Ranking functions of CR fun9(V,Out) #### Partial ranking functions of CR fun9(V,Out) ### Specialization of cost equations start/2 * CE 1 is refined into CE [157,158,159,160,161,162,163] * CE 2 is refined into CE [164,165] * CE 3 is refined into CE [166,167] * CE 4 is refined into CE [168,169] * CE 5 is refined into CE [170,171] * CE 6 is refined into CE [172,173,174] * CE 7 is refined into CE [175,176,177,178,179] * CE 8 is refined into CE [180,181] * CE 9 is refined into CE [182,183,184,185,186] * CE 10 is refined into CE [187,188,189] * CE 11 is refined into CE [190,191,192] * CE 12 is refined into CE [193,194] * CE 13 is refined into CE [195,196,197] * CE 14 is refined into CE [198,199] * CE 15 is refined into CE [200,201] ### Cost equations --> "Loop" of start/2 * CEs [157,158,159,160,161,162,163,164,165,166,167,168,169,170,171,172,173,174,175,176,177,178,179,180,181,182,183,184,185,186,187,188,189,190,191,192,193,194,195,196,197,198,199,200,201] --> Loop 90 ### Ranking functions of CR start(V,V9) #### Partial ranking functions of CR start(V,V9) Computing Bounds ===================================== #### Cost of chains of fun(Out): * Chain [30]: 0 with precondition: [Out=0] * Chain [29]: 1 with precondition: [Out=2] #### Cost of chains of p(V,Out): * Chain [32]: 1 with precondition: [Out=0,V>=0] * Chain [31]: 2 with precondition: [V=1,Out=2] #### Cost of chains of s(V,Out): * Chain [34]: 0 with precondition: [Out=0,V>=0] * Chain [33]: 1 with precondition: [V+1=Out,V>=0] #### Cost of chains of f(V,Out): * Chain [39,37]: 5 with precondition: [V=1,Out=5] * Chain [39,36]: 6 with precondition: [V=1,Out=7] * Chain [39,35]: 5 with precondition: [V=1,Out=1] * Chain [38,35]: 5 with precondition: [V=1,Out=3] * Chain [37]: 1 with precondition: [V=0,Out=5] * Chain [36]: 2 with precondition: [V=0,Out=7] * Chain [35]: 1 with precondition: [V+1=Out,V>=0] #### Cost of chains of activate(V,Out): * Chain [[40,41,42,43,44,45,46,47],49]: 33*it(40)+1 Such that:aux(3) =< V it(40) =< aux(3) with precondition: [V>=3,Out>=0,V+4>=Out] * Chain [[40,41,42,43,44,45,46,47],48]: 33*it(40)+2 Such that:aux(4) =< V it(40) =< aux(4) with precondition: [V>=1,Out>=0,V+6>=Out] * Chain [49]: 1 with precondition: [V=2,Out=0] * Chain [48]: 2 with precondition: [V=Out,V>=0] #### Cost of chains of encArg(V,Out): * Chain [61]: 0 with precondition: [Out=0,V>=0] * Chain [60]: 1 with precondition: [V=1,Out=2] * Chain [59]: 0 with precondition: [V=2,Out=2] * Chain [multiple([50,51,52,53,54,55,56,57,58],[[61],[60],[59]])]: 27*it(51)+1*it([60])+66*s(9)+0 Such that:aux(6) =< 7*V it([60]) =< V/2+1/2 aux(7) =< V it(51) =< aux(7) it([60]) =< aux(7) s(10) =< it(51)*aux(6) s(9) =< s(10) with precondition: [V>=1,Out>=0,7*V>=Out] #### Cost of chains of fun1(V,Out): * Chain [66]: 2*s(19)+54*s(20)+132*s(22)+6 Such that:aux(8) =< V aux(9) =< 7*V aux(10) =< V/2+1/2 s(19) =< aux(10) s(20) =< aux(8) s(19) =< aux(8) s(21) =< s(20)*aux(9) s(22) =< s(21) with precondition: [V>=1,Out>=1,7*V+1>=Out] * Chain [65]: 0 with precondition: [Out=0,V>=0] * Chain [64]: 1*s(31)+27*s(32)+66*s(34)+6 Such that:s(29) =< V s(30) =< 7*V s(31) =< V/2+1/2 s(32) =< s(29) s(31) =< s(29) s(33) =< s(32)*s(30) s(34) =< s(33) with precondition: [Out=1,V>=0] * Chain [63]: 2*s(37)+54*s(38)+132*s(40)+6 Such that:aux(11) =< V aux(12) =< 7*V aux(13) =< V/2+1/2 s(37) =< aux(13) s(38) =< aux(11) s(37) =< aux(11) s(39) =< s(38)*aux(12) s(40) =< s(39) with precondition: [Out=5,V>=0] * Chain [62]: 2*s(49)+54*s(50)+132*s(52)+7 Such that:aux(14) =< V aux(15) =< 7*V aux(16) =< V/2+1/2 s(49) =< aux(16) s(50) =< aux(14) s(49) =< aux(14) s(51) =< s(50)*aux(15) s(52) =< s(51) with precondition: [Out=7,V>=0] #### Cost of chains of fun2(Out): * Chain [68]: 0 with precondition: [Out=0] * Chain [67]: 1 with precondition: [Out=2] #### Cost of chains of fun3(V,V9,Out): * Chain [74]: 1*s(61)+27*s(62)+66*s(64)+2*s(67)+54*s(68)+132*s(70)+2 Such that:s(59) =< V s(60) =< 7*V s(61) =< V/2+1/2 aux(17) =< V9 aux(18) =< 7*V9 aux(19) =< V9/2+1/2 s(67) =< aux(19) s(68) =< aux(17) s(67) =< aux(17) s(69) =< s(68)*aux(18) s(70) =< s(69) s(62) =< s(59) s(61) =< s(59) s(63) =< s(62)*s(60) s(64) =< s(63) with precondition: [V>=1,V9>=1,Out>=1,7*V+7*V9+1>=Out] * Chain [73]: 1*s(79)+27*s(80)+66*s(82)+1 Such that:s(77) =< V s(78) =< 7*V s(79) =< V/2+1/2 s(80) =< s(77) s(79) =< s(77) s(81) =< s(80)*s(78) s(82) =< s(81) with precondition: [V>=1,V9>=0,Out>=1,7*V+1>=Out] * Chain [72]: 1*s(85)+27*s(86)+66*s(88)+1 Such that:s(83) =< V9 s(84) =< 7*V9 s(85) =< V9/2+1/2 s(86) =< s(83) s(85) =< s(83) s(87) =< s(86)*s(84) s(88) =< s(87) with precondition: [V>=0,V9>=1,Out>=1,7*V9+1>=Out] * Chain [71]: 1*s(91)+27*s(92)+66*s(94)+1 Such that:s(89) =< V s(90) =< 7*V s(91) =< V/2+1/2 s(92) =< s(89) s(91) =< s(89) s(93) =< s(92)*s(90) s(94) =< s(93) with precondition: [V9=2,V>=1,Out>=3,7*V+3>=Out] * Chain [70]: 0 with precondition: [Out=0,V>=0,V9>=0] * Chain [69]: 0 with precondition: [Out=1,V>=0,V9>=0] #### Cost of chains of fun4(V,Out): * Chain [77]: 1*s(116)+27*s(117)+66*s(119)+1 Such that:s(114) =< V s(115) =< 7*V s(116) =< V/2+1/2 s(117) =< s(114) s(116) =< s(114) s(118) =< s(117)*s(115) s(119) =< s(118) with precondition: [V>=1,Out>=1,7*V+1>=Out] * Chain [76]: 0 with precondition: [Out=0,V>=0] * Chain [75]: 0 with precondition: [Out=1,V>=0] #### Cost of chains of fun5(V,Out): * Chain [80]: 1*s(122)+27*s(123)+66*s(125)+1 Such that:s(120) =< V s(121) =< 7*V s(122) =< V/2+1/2 s(123) =< s(120) s(122) =< s(120) s(124) =< s(123)*s(121) s(125) =< s(124) with precondition: [V>=1,Out>=1,7*V+1>=Out] * Chain [79]: 0 with precondition: [Out=0,V>=0] * Chain [78]: 0 with precondition: [Out=1,V>=0] #### Cost of chains of fun6(Out): * Chain [82]: 0 with precondition: [Out=0] * Chain [81]: 0 with precondition: [Out=2] #### Cost of chains of fun7(V,Out): * Chain [85]: 1*s(128)+27*s(129)+66*s(131)+1 Such that:s(126) =< V s(127) =< 7*V s(128) =< V/2+1/2 s(129) =< s(126) s(128) =< s(126) s(130) =< s(129)*s(127) s(131) =< s(130) with precondition: [Out=0,V>=0] * Chain [84]: 1*s(134)+27*s(135)+66*s(137)+2 Such that:s(132) =< V s(133) =< 7*V s(134) =< V/2+1/2 s(135) =< s(132) s(134) =< s(132) s(136) =< s(135)*s(133) s(137) =< s(136) with precondition: [V>=1,Out>=1,7*V+1>=Out] * Chain [83]: 1 with precondition: [Out=1,V>=0] #### Cost of chains of fun8(V,Out): * Chain [87]: 1*s(140)+27*s(141)+66*s(143)+2 Such that:s(138) =< V s(139) =< 7*V s(140) =< V/2+1/2 s(141) =< s(138) s(140) =< s(138) s(142) =< s(141)*s(139) s(143) =< s(142) with precondition: [Out=0,V>=0] * Chain [86]: 1*s(146)+27*s(147)+66*s(149)+3 Such that:s(144) =< V s(145) =< 7*V s(146) =< V/2+1/2 s(147) =< s(144) s(146) =< s(144) s(148) =< s(147)*s(145) s(149) =< s(148) with precondition: [Out=2,V>=1] #### Cost of chains of fun9(V,Out): * Chain [89]: 2*s(152)+54*s(153)+132*s(155)+66*s(157)+66*s(165)+3 Such that:s(164) =< 2 aux(24) =< V aux(25) =< 7*V aux(26) =< V/2+1/2 s(152) =< aux(26) s(165) =< s(164) s(157) =< aux(25) s(153) =< aux(24) s(152) =< aux(24) s(154) =< s(153)*aux(25) s(155) =< s(154) with precondition: [V>=1,Out>=0,7*V+6>=Out] * Chain [88]: 2 with precondition: [Out=0,V>=0] #### Cost of chains of start(V,V9): * Chain [90]: 579*s(167)+19*s(170)+1254*s(173)+3*s(211)+81*s(212)+198*s(214)+66*s(268)+66*s(269)+7 Such that:s(263) =< 2 aux(27) =< V aux(28) =< 7*V aux(29) =< V/2+1/2 aux(30) =< V9 aux(31) =< 7*V9 aux(32) =< V9/2+1/2 s(170) =< aux(29) s(211) =< aux(32) s(268) =< s(263) s(269) =< aux(28) s(167) =< aux(27) s(170) =< aux(27) s(172) =< s(167)*aux(28) s(173) =< s(172) s(212) =< aux(30) s(211) =< aux(30) s(213) =< s(212)*aux(31) s(214) =< s(213) with precondition: [] Closed-form bounds of start(V,V9): ------------------------------------- * Chain [90] with precondition: [] - Upper bound: nat(V)*579+139+nat(V)*1254*nat(7*V)+nat(V9)*81+nat(V9)*198*nat(7*V9)+nat(7*V)*66+nat(V/2+1/2)*19+nat(V9/2+1/2)*3 - Complexity: n^2 ### Maximum cost of start(V,V9): nat(V)*579+139+nat(V)*1254*nat(7*V)+nat(V9)*81+nat(V9)*198*nat(7*V9)+nat(7*V)*66+nat(V/2+1/2)*19+nat(V9/2+1/2)*3 Asymptotic class: n^2 * Total analysis performed in 674 ms. ---------------------------------------- (20) BOUNDS(1, n^2) ---------------------------------------- (21) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (22) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: f(0) -> cons(0, n__f(n__s(n__0))) f(s(0)) -> f(p(s(0))) p(s(0)) -> 0 f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (23) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence activate(n__f(X)) ->^+ f(activate(X)) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [X / n__f(X)]. The result substitution is [ ]. ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: f(0) -> cons(0, n__f(n__s(n__0))) f(s(0)) -> f(p(s(0))) p(s(0)) -> 0 f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^2). The TRS R consists of the following rules: f(0) -> cons(0, n__f(n__s(n__0))) f(s(0)) -> f(p(s(0))) p(s(0)) -> 0 f(X) -> n__f(X) s(X) -> n__s(X) 0 -> n__0 activate(n__f(X)) -> f(activate(X)) activate(n__s(X)) -> s(activate(X)) activate(n__0) -> 0 activate(X) -> X The (relative) TRS S consists of the following rules: encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(n__f(x_1)) -> n__f(encArg(x_1)) encArg(n__s(x_1)) -> n__s(encArg(x_1)) encArg(n__0) -> n__0 encArg(cons_f(x_1)) -> f(encArg(x_1)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_s(x_1)) -> s(encArg(x_1)) encArg(cons_0) -> 0 encArg(cons_activate(x_1)) -> activate(encArg(x_1)) encode_f(x_1) -> f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_n__f(x_1) -> n__f(encArg(x_1)) encode_n__s(x_1) -> n__s(encArg(x_1)) encode_n__0 -> n__0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_activate(x_1) -> activate(encArg(x_1)) Rewrite Strategy: FULL