/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^1)) 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^1). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 162 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) NarrowingProof [BOTH BOUNDS(ID, ID), 19 ms] (18) CpxTypedWeightedCompleteTrs (19) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (20) CpxRNTS (21) InliningProof [UPPER BOUND(ID), 0 ms] (22) CpxRNTS (23) SimplificationProof [BOTH BOUNDS(ID, ID), 0 ms] (24) CpxRNTS (25) CpxRntsAnalysisOrderProof [BOTH BOUNDS(ID, ID), 0 ms] (26) CpxRNTS (27) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (28) CpxRNTS (29) IntTrsBoundProof [UPPER BOUND(ID), 77 ms] (30) CpxRNTS (31) IntTrsBoundProof [UPPER BOUND(ID), 24 ms] (32) CpxRNTS (33) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (34) CpxRNTS (35) IntTrsBoundProof [UPPER BOUND(ID), 509 ms] (36) CpxRNTS (37) IntTrsBoundProof [UPPER BOUND(ID), 85 ms] (38) CpxRNTS (39) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (40) CpxRNTS (41) IntTrsBoundProof [UPPER BOUND(ID), 354 ms] (42) CpxRNTS (43) IntTrsBoundProof [UPPER BOUND(ID), 84 ms] (44) CpxRNTS (45) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (46) CpxRNTS (47) IntTrsBoundProof [UPPER BOUND(ID), 386 ms] (48) CpxRNTS (49) IntTrsBoundProof [UPPER BOUND(ID), 84 ms] (50) CpxRNTS (51) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (52) CpxRNTS (53) IntTrsBoundProof [UPPER BOUND(ID), 221 ms] (54) CpxRNTS (55) IntTrsBoundProof [UPPER BOUND(ID), 74 ms] (56) CpxRNTS (57) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (58) CpxRNTS (59) IntTrsBoundProof [UPPER BOUND(ID), 170 ms] (60) CpxRNTS (61) IntTrsBoundProof [UPPER BOUND(ID), 73 ms] (62) CpxRNTS (63) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (64) CpxRNTS (65) IntTrsBoundProof [UPPER BOUND(ID), 159 ms] (66) CpxRNTS (67) IntTrsBoundProof [UPPER BOUND(ID), 63 ms] (68) CpxRNTS (69) ResultPropagationProof [UPPER BOUND(ID), 0 ms] (70) CpxRNTS (71) IntTrsBoundProof [UPPER BOUND(ID), 150 ms] (72) CpxRNTS (73) IntTrsBoundProof [UPPER BOUND(ID), 64 ms] (74) CpxRNTS (75) FinalProof [FINISHED, 0 ms] (76) BOUNDS(1, n^1) (77) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (78) CpxRelTRS (79) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (80) typed CpxTrs (81) OrderProof [LOWER BOUND(ID), 0 ms] (82) typed CpxTrs (83) RewriteLemmaProof [LOWER BOUND(ID), 243 ms] (84) proven lower bound (85) LowerBoundPropagationProof [FINISHED, 0 ms] (86) BOUNDS(n^1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (full) of the given DCpxTrs could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y 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(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y The (relative) TRS S consists of the following rules: encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) 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^1). The TRS R consists of the following rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y The (relative) TRS S consists of the following rules: encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) 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^1). The TRS R consists of the following rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, c_\(x, y)) -> y \(x, c_.(x, y)) -> y \(c_/(x, y), x) -> y .(c_/(y, x), x) -> y /(c_.(y, x), x) -> y /(x, c_\(y, x)) -> y The (relative) TRS S consists of the following rules: encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) \(x0, x1) -> c_\(x0, x1) /(x0, x1) -> c_/(x0, x1) .(x0, x1) -> c_.(x0, x1) 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^1). The TRS R consists of the following rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, c_\(x, y)) -> y \(x, c_.(x, y)) -> y \(c_/(x, y), x) -> y .(c_/(y, x), x) -> y /(c_.(y, x), x) -> y /(x, c_\(y, x)) -> y The (relative) TRS S consists of the following rules: encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) \(x0, x1) -> c_\(x0, x1) /(x0, x1) -> c_/(x0, x1) .(x0, x1) -> c_.(x0, x1) 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^1). The TRS R consists of the following rules: \(x, x) -> e [1] /(x, x) -> e [1] .(e, x) -> x [1] .(x, e) -> x [1] \(e, x) -> x [1] /(x, e) -> x [1] .(x, c_\(x, y)) -> y [1] \(x, c_.(x, y)) -> y [1] \(c_/(x, y), x) -> y [1] .(c_/(y, x), x) -> y [1] /(c_.(y, x), x) -> y [1] /(x, c_\(y, x)) -> y [1] encArg(e) -> e [0] encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) [0] encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) [0] encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) [0] encode_e -> e [0] encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] \(x0, x1) -> c_\(x0, x1) [0] /(x0, x1) -> c_/(x0, x1) [0] .(x0, x1) -> c_.(x0, x1) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxWeightedTrsRenamingProof (BOTH BOUNDS(ID, ID)) Renamed defined symbols to avoid conflicts with arithmetic symbols: / => div ---------------------------------------- (12) Obligation: The Runtime Complexity (innermost) of the given CpxWeightedTrs could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: \(x, x) -> e [1] div(x, x) -> e [1] .(e, x) -> x [1] .(x, e) -> x [1] \(e, x) -> x [1] div(x, e) -> x [1] .(x, c_\(x, y)) -> y [1] \(x, c_.(x, y)) -> y [1] \(c_/(x, y), x) -> y [1] .(c_/(y, x), x) -> y [1] div(c_.(y, x), x) -> y [1] div(x, c_\(y, x)) -> y [1] encArg(e) -> e [0] encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) [0] encArg(cons_/(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) [0] encode_e -> e [0] encode_/(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] \(x0, x1) -> c_\(x0, x1) [0] div(x0, x1) -> c_/(x0, x1) [0] .(x0, x1) -> c_.(x0, x1) [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: \(x, x) -> e [1] div(x, x) -> e [1] .(e, x) -> x [1] .(x, e) -> x [1] \(e, x) -> x [1] div(x, e) -> x [1] .(x, c_\(x, y)) -> y [1] \(x, c_.(x, y)) -> y [1] \(c_/(x, y), x) -> y [1] .(c_/(y, x), x) -> y [1] div(c_.(y, x), x) -> y [1] div(x, c_\(y, x)) -> y [1] encArg(e) -> e [0] encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) [0] encArg(cons_/(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) [0] encode_e -> e [0] encode_/(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] \(x0, x1) -> c_\(x0, x1) [0] div(x0, x1) -> c_/(x0, x1) [0] .(x0, x1) -> c_.(x0, x1) [0] The TRS has the following type information: \ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. e :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. div :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. . :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encArg :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_e :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. Rewrite Strategy: INNERMOST ---------------------------------------- (15) 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: none (c) The following functions are completely defined: encArg_1 encode_\_2 encode_e encode_/_2 encode_._2 \_2 div_2 ._2 Due to the following rules being added: encArg(v0) -> e [0] encode_\(v0, v1) -> e [0] encode_e -> e [0] encode_/(v0, v1) -> e [0] encode_.(v0, v1) -> e [0] \(v0, v1) -> e [0] div(v0, v1) -> e [0] .(v0, v1) -> e [0] And the following fresh constants: none ---------------------------------------- (16) 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: \(x, x) -> e [1] div(x, x) -> e [1] .(e, x) -> x [1] .(x, e) -> x [1] \(e, x) -> x [1] div(x, e) -> x [1] .(x, c_\(x, y)) -> y [1] \(x, c_.(x, y)) -> y [1] \(c_/(x, y), x) -> y [1] .(c_/(y, x), x) -> y [1] div(c_.(y, x), x) -> y [1] div(x, c_\(y, x)) -> y [1] encArg(e) -> e [0] encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) [0] encArg(cons_/(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) [0] encode_e -> e [0] encode_/(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] \(x0, x1) -> c_\(x0, x1) [0] div(x0, x1) -> c_/(x0, x1) [0] .(x0, x1) -> c_.(x0, x1) [0] encArg(v0) -> e [0] encode_\(v0, v1) -> e [0] encode_e -> e [0] encode_/(v0, v1) -> e [0] encode_.(v0, v1) -> e [0] \(v0, v1) -> e [0] div(v0, v1) -> e [0] .(v0, v1) -> e [0] The TRS has the following type information: \ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. e :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. div :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. . :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encArg :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_e :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. Rewrite Strategy: INNERMOST ---------------------------------------- (17) NarrowingProof (BOTH BOUNDS(ID, ID)) Narrowed the inner basic terms of all right-hand sides by a single narrowing step. ---------------------------------------- (18) 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: \(x, x) -> e [1] div(x, x) -> e [1] .(e, x) -> x [1] .(x, e) -> x [1] \(e, x) -> x [1] div(x, e) -> x [1] .(x, c_\(x, y)) -> y [1] \(x, c_.(x, y)) -> y [1] \(c_/(x, y), x) -> y [1] .(c_/(y, x), x) -> y [1] div(c_.(y, x), x) -> y [1] div(x, c_\(y, x)) -> y [1] encArg(e) -> e [0] encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) [0] encArg(cons_/(x_1, x_2)) -> div(encArg(x_1), encArg(x_2)) [0] encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) [0] encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) [0] encode_e -> e [0] encode_/(x_1, x_2) -> div(encArg(x_1), encArg(x_2)) [0] encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) [0] \(x0, x1) -> c_\(x0, x1) [0] div(x0, x1) -> c_/(x0, x1) [0] .(x0, x1) -> c_.(x0, x1) [0] encArg(v0) -> e [0] encode_\(v0, v1) -> e [0] encode_e -> e [0] encode_/(v0, v1) -> e [0] encode_.(v0, v1) -> e [0] \(v0, v1) -> e [0] div(v0, v1) -> e [0] .(v0, v1) -> e [0] The TRS has the following type information: \ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. e :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. div :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. . :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. c_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encArg :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. cons_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_\ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_e :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_/ :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. encode_. :: e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. -> e:c_\:c_.:c_/:cons_\:cons_/:cons_. Rewrite Strategy: INNERMOST ---------------------------------------- (19) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: e => 0 ---------------------------------------- (20) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 .(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 .(z, z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0, z = x .(z, z') -{ 1 }-> y :|: z' = x, z = 1 + y + x, y >= 0, x >= 0 .(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 .(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 \(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 \(z, z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0, z = x \(z, z') -{ 1 }-> y :|: z = 1 + x + y, z' = x, x >= 0, y >= 0 \(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = x \(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 \(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 div(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 div(z, z') -{ 1 }-> y :|: z' = x, z = 1 + y + x, y >= 0, x >= 0 div(z, z') -{ 1 }-> y :|: x >= 0, y >= 0, z' = 1 + y + x, z = x div(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = x div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 div(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_.(z, z') -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_/(z, z') -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_/(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_\(z, z') -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_\(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_e -{ 0 }-> 0 :|: ---------------------------------------- (21) InliningProof (UPPER BOUND(ID)) Inlined the following terminating rules on right-hand sides where appropriate: \(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 \(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 \(z, z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0, z = x \(z, z') -{ 1 }-> y :|: z = 1 + x + y, z' = x, x >= 0, y >= 0 \(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = x \(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 div(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 div(z, z') -{ 1 }-> y :|: z' = x, z = 1 + y + x, y >= 0, x >= 0 div(z, z') -{ 1 }-> y :|: x >= 0, y >= 0, z' = 1 + y + x, z = x div(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = x div(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 .(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 .(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 .(z, z') -{ 1 }-> y :|: z' = x, z = 1 + y + x, y >= 0, x >= 0 .(z, z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0, z = x .(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 .(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 ---------------------------------------- (22) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 .(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 .(z, z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0, z = x .(z, z') -{ 1 }-> y :|: z' = x, z = 1 + y + x, y >= 0, x >= 0 .(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 .(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 \(z, z') -{ 1 }-> x :|: z' = x, x >= 0, z = 0 \(z, z') -{ 1 }-> y :|: z' = 1 + x + y, x >= 0, y >= 0, z = x \(z, z') -{ 1 }-> y :|: z = 1 + x + y, z' = x, x >= 0, y >= 0 \(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = x \(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 \(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 div(z, z') -{ 1 }-> x :|: x >= 0, z = x, z' = 0 div(z, z') -{ 1 }-> y :|: z' = x, z = 1 + y + x, y >= 0, x >= 0 div(z, z') -{ 1 }-> y :|: x >= 0, y >= 0, z' = 1 + y + x, z = x div(z, z') -{ 1 }-> 0 :|: z' = x, x >= 0, z = x div(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 div(z, z') -{ 0 }-> 1 + x0 + x1 :|: z = x0, x0 >= 0, x1 >= 0, z' = x1 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_.(z, z') -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_/(z, z') -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_/(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_\(z, z') -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, x_2 >= 0, z = x_1, z' = x_2 encode_\(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 encode_e -{ 0 }-> 0 :|: ---------------------------------------- (23) SimplificationProof (BOTH BOUNDS(ID, ID)) Simplified the RNTS by moving equalities from the constraints into the right-hand sides. ---------------------------------------- (24) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: ---------------------------------------- (25) CpxRntsAnalysisOrderProof (BOTH BOUNDS(ID, ID)) Found the following analysis order by SCC decomposition: { encode_e } { . } { div } { \ } { encArg } { encode_. } { encode_/ } { encode_\ } ---------------------------------------- (26) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_e}, {.}, {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} ---------------------------------------- (27) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (28) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_e}, {.}, {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} ---------------------------------------- (29) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_e after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (30) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_e}, {.}, {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: ?, size: O(1) [0] ---------------------------------------- (31) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_e after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 0 ---------------------------------------- (32) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {.}, {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] ---------------------------------------- (33) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (34) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {.}, {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] ---------------------------------------- (35) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: . after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (36) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {.}, {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: ?, size: O(n^1) [1 + z + z'] ---------------------------------------- (37) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: . after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 1 ---------------------------------------- (38) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] ---------------------------------------- (39) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (40) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] ---------------------------------------- (41) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: div after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (42) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {div}, {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: ?, size: O(n^1) [1 + z + z'] ---------------------------------------- (43) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: div after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 1 ---------------------------------------- (44) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] ---------------------------------------- (45) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (46) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] ---------------------------------------- (47) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: \ after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (48) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {\}, {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: ?, size: O(n^1) [1 + z + z'] ---------------------------------------- (49) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: \ after applying outer abstraction to obtain an ITS, resulting in: O(1) with polynomial bound: 1 ---------------------------------------- (50) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] ---------------------------------------- (51) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (52) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] ---------------------------------------- (53) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: z ---------------------------------------- (54) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encArg}, {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: ?, size: O(n^1) [z] ---------------------------------------- (55) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encArg after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: z ---------------------------------------- (56) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 0 }-> div(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> \(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encArg(z) -{ 0 }-> .(encArg(x_1), encArg(x_2)) :|: x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> .(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> div(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> \(encArg(z), encArg(z')) :|: z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] ---------------------------------------- (57) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (58) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] ---------------------------------------- (59) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_. after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (60) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_.}, {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: ?, size: O(n^1) [1 + z + z'] ---------------------------------------- (61) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_. after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (62) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] ---------------------------------------- (63) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (64) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] ---------------------------------------- (65) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_/ after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (66) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_/}, {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_/: runtime: ?, size: O(n^1) [1 + z + z'] ---------------------------------------- (67) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_/ after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (68) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_/: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] ---------------------------------------- (69) ResultPropagationProof (UPPER BOUND(ID)) Applied inner abstraction using the recently inferred runtime/size bounds where possible. ---------------------------------------- (70) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_/: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] ---------------------------------------- (71) IntTrsBoundProof (UPPER BOUND(ID)) Computed SIZE bound using CoFloCo for: encode_\ after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (72) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: {encode_\} Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_/: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_\: runtime: ?, size: O(n^1) [1 + z + z'] ---------------------------------------- (73) IntTrsBoundProof (UPPER BOUND(ID)) Computed RUNTIME bound using CoFloCo for: encode_\ after applying outer abstraction to obtain an ITS, resulting in: O(n^1) with polynomial bound: 1 + z + z' ---------------------------------------- (74) Obligation: Complexity RNTS consisting of the following rules: .(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 .(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 .(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 .(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 .(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 .(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 \(z, z') -{ 1 }-> y :|: z' = 1 + z + y, z >= 0, y >= 0 \(z, z') -{ 1 }-> y :|: z = 1 + z' + y, z' >= 0, y >= 0 \(z, z') -{ 1 }-> z' :|: z' >= 0, z = 0 \(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' \(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 \(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z = 1 + y + z', y >= 0, z' >= 0 div(z, z') -{ 1 }-> y :|: z >= 0, y >= 0, z' = 1 + y + z div(z, z') -{ 1 }-> z :|: z >= 0, z' = 0 div(z, z') -{ 1 }-> 0 :|: z' >= 0, z = z' div(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 div(z, z') -{ 0 }-> 1 + z + z' :|: z >= 0, z' >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s'' :|: s >= 0, s <= x_1, s' >= 0, s' <= x_2, s'' >= 0, s'' <= s + s' + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s12 :|: s10 >= 0, s10 <= x_1, s11 >= 0, s11 <= x_2, s12 >= 0, s12 <= s10 + s11 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 1 + x_1 + x_2 }-> s6 :|: s4 >= 0, s4 <= x_1, s5 >= 0, s5 <= x_2, s6 >= 0, s6 <= s4 + s5 + 1, x_1 >= 0, z = 1 + x_1 + x_2, x_2 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 encArg(z) -{ 0 }-> 0 :|: z >= 0 encode_.(z, z') -{ 1 + z + z' }-> s15 :|: s13 >= 0, s13 <= z, s14 >= 0, s14 <= z', s15 >= 0, s15 <= s13 + s14 + 1, z >= 0, z' >= 0 encode_.(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_/(z, z') -{ 1 + z + z' }-> s9 :|: s7 >= 0, s7 <= z, s8 >= 0, s8 <= z', s9 >= 0, s9 <= s7 + s8 + 1, z >= 0, z' >= 0 encode_/(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_\(z, z') -{ 1 + z + z' }-> s3 :|: s1 >= 0, s1 <= z, s2 >= 0, s2 <= z', s3 >= 0, s3 <= s1 + s2 + 1, z >= 0, z' >= 0 encode_\(z, z') -{ 0 }-> 0 :|: z >= 0, z' >= 0 encode_e -{ 0 }-> 0 :|: Function symbols to be analyzed: Previous analysis results are: encode_e: runtime: O(1) [0], size: O(1) [0] .: runtime: O(1) [1], size: O(n^1) [1 + z + z'] div: runtime: O(1) [1], size: O(n^1) [1 + z + z'] \: runtime: O(1) [1], size: O(n^1) [1 + z + z'] encArg: runtime: O(n^1) [z], size: O(n^1) [z] encode_.: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_/: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] encode_\: runtime: O(n^1) [1 + z + z'], size: O(n^1) [1 + z + z'] ---------------------------------------- (75) FinalProof (FINISHED) Computed overall runtime complexity ---------------------------------------- (76) BOUNDS(1, n^1) ---------------------------------------- (77) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (78) Obligation: The Runtime Complexity (full) of the given CpxRelTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y The (relative) TRS S consists of the following rules: encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) Rewrite Strategy: FULL ---------------------------------------- (79) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (80) Obligation: TRS: Rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) Types: \ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. e :: e:cons_\:cons_/:cons_. / :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. . :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encArg :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_\ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_/ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_. :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_\ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_e :: e:cons_\:cons_/:cons_. encode_/ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_. :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. hole_e:cons_\:cons_/:cons_.1_0 :: e:cons_\:cons_/:cons_. gen_e:cons_\:cons_/:cons_.2_0 :: Nat -> e:cons_\:cons_/:cons_. ---------------------------------------- (81) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: encArg ---------------------------------------- (82) Obligation: TRS: Rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) Types: \ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. e :: e:cons_\:cons_/:cons_. / :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. . :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encArg :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_\ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_/ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_. :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_\ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_e :: e:cons_\:cons_/:cons_. encode_/ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_. :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. hole_e:cons_\:cons_/:cons_.1_0 :: e:cons_\:cons_/:cons_. gen_e:cons_\:cons_/:cons_.2_0 :: Nat -> e:cons_\:cons_/:cons_. Generator Equations: gen_e:cons_\:cons_/:cons_.2_0(0) <=> e gen_e:cons_\:cons_/:cons_.2_0(+(x, 1)) <=> cons_\(e, gen_e:cons_\:cons_/:cons_.2_0(x)) The following defined symbols remain to be analysed: encArg ---------------------------------------- (83) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_e:cons_\:cons_/:cons_.2_0(n4_0)) -> gen_e:cons_\:cons_/:cons_.2_0(0), rt in Omega(n4_0) Induction Base: encArg(gen_e:cons_\:cons_/:cons_.2_0(0)) ->_R^Omega(0) e Induction Step: encArg(gen_e:cons_\:cons_/:cons_.2_0(+(n4_0, 1))) ->_R^Omega(0) \(encArg(e), encArg(gen_e:cons_\:cons_/:cons_.2_0(n4_0))) ->_R^Omega(0) \(e, encArg(gen_e:cons_\:cons_/:cons_.2_0(n4_0))) ->_IH \(e, gen_e:cons_\:cons_/:cons_.2_0(0)) ->_R^Omega(1) e We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (84) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: \(x, x) -> e /(x, x) -> e .(e, x) -> x .(x, e) -> x \(e, x) -> x /(x, e) -> x .(x, \(x, y)) -> y .(/(y, x), x) -> y \(x, .(x, y)) -> y /(.(y, x), x) -> y /(x, \(y, x)) -> y \(/(x, y), x) -> y encArg(e) -> e encArg(cons_\(x_1, x_2)) -> \(encArg(x_1), encArg(x_2)) encArg(cons_/(x_1, x_2)) -> /(encArg(x_1), encArg(x_2)) encArg(cons_.(x_1, x_2)) -> .(encArg(x_1), encArg(x_2)) encode_\(x_1, x_2) -> \(encArg(x_1), encArg(x_2)) encode_e -> e encode_/(x_1, x_2) -> /(encArg(x_1), encArg(x_2)) encode_.(x_1, x_2) -> .(encArg(x_1), encArg(x_2)) Types: \ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. e :: e:cons_\:cons_/:cons_. / :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. . :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encArg :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_\ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_/ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. cons_. :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_\ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_e :: e:cons_\:cons_/:cons_. encode_/ :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. encode_. :: e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. -> e:cons_\:cons_/:cons_. hole_e:cons_\:cons_/:cons_.1_0 :: e:cons_\:cons_/:cons_. gen_e:cons_\:cons_/:cons_.2_0 :: Nat -> e:cons_\:cons_/:cons_. Generator Equations: gen_e:cons_\:cons_/:cons_.2_0(0) <=> e gen_e:cons_\:cons_/:cons_.2_0(+(x, 1)) <=> cons_\(e, gen_e:cons_\:cons_/:cons_.2_0(x)) The following defined symbols remain to be analysed: encArg ---------------------------------------- (85) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (86) BOUNDS(n^1, INF)