/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^2)) proof of /export/starexec/sandbox/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), 194 ms] (4) CpxRelTRS (5) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxWeightedTrs (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CpxTypedWeightedTrs (11) CompletionProof [UPPER BOUND(ID), 0 ms] (12) CpxTypedWeightedCompleteTrs (13) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (14) CpxRNTS (15) CompleteCoflocoProof [FINISHED, 521 ms] (16) BOUNDS(1, n^2) (17) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (18) CpxRelTRS (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (20) typed CpxTrs (21) OrderProof [LOWER BOUND(ID), 0 ms] (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 289 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^1, INF) (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 225 ms] (30) BOUNDS(1, INF) ---------------------------------------- (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: a__f(0) -> cons(0, f(s(0))) a__f(s(0)) -> a__f(a__p(s(0))) a__p(s(0)) -> 0 mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(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(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(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: a__f(0) -> cons(0, f(s(0))) a__f(s(0)) -> a__f(a__p(s(0))) a__p(s(0)) -> 0 mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(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: a__f(0) -> cons(0, f(s(0))) a__f(s(0)) -> a__f(a__p(s(0))) a__p(s(0)) -> 0 mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (5) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, we have rc = irc. ---------------------------------------- (6) 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: a__f(0) -> cons(0, f(s(0))) a__f(s(0)) -> a__f(a__p(s(0))) a__p(s(0)) -> 0 mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0) -> 0 mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0 encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (7) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (8) 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: a__f(0) -> cons(0, f(s(0))) [1] a__f(s(0)) -> a__f(a__p(s(0))) [1] a__p(s(0)) -> 0 [1] mark(f(X)) -> a__f(mark(X)) [1] mark(p(X)) -> a__p(mark(X)) [1] mark(0) -> 0 [1] mark(cons(X1, X2)) -> cons(mark(X1), X2) [1] mark(s(X)) -> s(mark(X)) [1] a__f(X) -> f(X) [1] a__p(X) -> p(X) [1] encArg(0) -> 0 [0] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(f(x_1)) -> f(encArg(x_1)) [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) [0] encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) [0] encArg(cons_mark(x_1)) -> mark(encArg(x_1)) [0] encode_a__f(x_1) -> a__f(encArg(x_1)) [0] encode_0 -> 0 [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_a__p(x_1) -> a__p(encArg(x_1)) [0] encode_mark(x_1) -> mark(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] Rewrite Strategy: INNERMOST ---------------------------------------- (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (10) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: a__f(0) -> cons(0, f(s(0))) [1] a__f(s(0)) -> a__f(a__p(s(0))) [1] a__p(s(0)) -> 0 [1] mark(f(X)) -> a__f(mark(X)) [1] mark(p(X)) -> a__p(mark(X)) [1] mark(0) -> 0 [1] mark(cons(X1, X2)) -> cons(mark(X1), X2) [1] mark(s(X)) -> s(mark(X)) [1] a__f(X) -> f(X) [1] a__p(X) -> p(X) [1] encArg(0) -> 0 [0] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(f(x_1)) -> f(encArg(x_1)) [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) [0] encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) [0] encArg(cons_mark(x_1)) -> mark(encArg(x_1)) [0] encode_a__f(x_1) -> a__f(encArg(x_1)) [0] encode_0 -> 0 [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_a__p(x_1) -> a__p(encArg(x_1)) [0] encode_mark(x_1) -> mark(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] The TRS has the following type information: a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark 0 :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark s :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encArg :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_0 :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_cons :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_s :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark Rewrite Strategy: INNERMOST ---------------------------------------- (11) 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_a__f(v0) -> null_encode_a__f [0] encode_0 -> null_encode_0 [0] encode_cons(v0, v1) -> null_encode_cons [0] encode_f(v0) -> null_encode_f [0] encode_s(v0) -> null_encode_s [0] encode_a__p(v0) -> null_encode_a__p [0] encode_mark(v0) -> null_encode_mark [0] encode_p(v0) -> null_encode_p [0] mark(v0) -> null_mark [0] And the following fresh constants: null_encArg, null_encode_a__f, null_encode_0, null_encode_cons, null_encode_f, null_encode_s, null_encode_a__p, null_encode_mark, null_encode_p, null_mark ---------------------------------------- (12) 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: a__f(0) -> cons(0, f(s(0))) [1] a__f(s(0)) -> a__f(a__p(s(0))) [1] a__p(s(0)) -> 0 [1] mark(f(X)) -> a__f(mark(X)) [1] mark(p(X)) -> a__p(mark(X)) [1] mark(0) -> 0 [1] mark(cons(X1, X2)) -> cons(mark(X1), X2) [1] mark(s(X)) -> s(mark(X)) [1] a__f(X) -> f(X) [1] a__p(X) -> p(X) [1] encArg(0) -> 0 [0] encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) [0] encArg(f(x_1)) -> f(encArg(x_1)) [0] encArg(s(x_1)) -> s(encArg(x_1)) [0] encArg(p(x_1)) -> p(encArg(x_1)) [0] encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) [0] encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) [0] encArg(cons_mark(x_1)) -> mark(encArg(x_1)) [0] encode_a__f(x_1) -> a__f(encArg(x_1)) [0] encode_0 -> 0 [0] encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) [0] encode_f(x_1) -> f(encArg(x_1)) [0] encode_s(x_1) -> s(encArg(x_1)) [0] encode_a__p(x_1) -> a__p(encArg(x_1)) [0] encode_mark(x_1) -> mark(encArg(x_1)) [0] encode_p(x_1) -> p(encArg(x_1)) [0] encArg(v0) -> null_encArg [0] encode_a__f(v0) -> null_encode_a__f [0] encode_0 -> null_encode_0 [0] encode_cons(v0, v1) -> null_encode_cons [0] encode_f(v0) -> null_encode_f [0] encode_s(v0) -> null_encode_s [0] encode_a__p(v0) -> null_encode_a__p [0] encode_mark(v0) -> null_encode_mark [0] encode_p(v0) -> null_encode_p [0] mark(v0) -> null_mark [0] The TRS has the following type information: a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark 0 :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark cons :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark s :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encArg :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark cons_a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark cons_a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark cons_mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_0 :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_cons :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_s :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark encode_p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark -> 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encArg :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_a__f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_0 :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_cons :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_f :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_s :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_a__p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_encode_p :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark null_mark :: 0:s:f:cons:p:cons_a__f:cons_a__p:cons_mark:null_encArg:null_encode_a__f:null_encode_0:null_encode_cons:null_encode_f:null_encode_s:null_encode_a__p:null_encode_mark:null_encode_p:null_mark Rewrite Strategy: INNERMOST ---------------------------------------- (13) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: 0 => 0 null_encArg => 0 null_encode_a__f => 0 null_encode_0 => 0 null_encode_cons => 0 null_encode_f => 0 null_encode_s => 0 null_encode_a__p => 0 null_encode_mark => 0 null_encode_p => 0 null_mark => 0 ---------------------------------------- (14) Obligation: Complexity RNTS consisting of the following rules: a__f(z) -{ 1 }-> a__f(a__p(1 + 0)) :|: z = 1 + 0 a__f(z) -{ 1 }-> 1 + X :|: X >= 0, z = X a__f(z) -{ 1 }-> 1 + 0 + (1 + (1 + 0)) :|: z = 0 a__p(z) -{ 1 }-> 0 :|: z = 1 + 0 a__p(z) -{ 1 }-> 1 + X :|: X >= 0, z = X encArg(z) -{ 0 }-> mark(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> a__p(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> a__f(encArg(x_1)) :|: z = 1 + x_1, x_1 >= 0 encArg(z) -{ 0 }-> 0 :|: z = 0 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_a__f(z) -{ 0 }-> a__f(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_a__f(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_a__p(z) -{ 0 }-> a__p(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_a__p(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 }-> 0 :|: v0 >= 0, z = v0 encode_f(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_mark(z) -{ 0 }-> mark(encArg(x_1)) :|: x_1 >= 0, z = x_1 encode_mark(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_p(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_p(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 encode_s(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 encode_s(z) -{ 0 }-> 1 + encArg(x_1) :|: x_1 >= 0, z = x_1 mark(z) -{ 1 }-> a__p(mark(X)) :|: z = 1 + X, X >= 0 mark(z) -{ 1 }-> a__f(mark(X)) :|: z = 1 + X, X >= 0 mark(z) -{ 1 }-> 0 :|: z = 0 mark(z) -{ 0 }-> 0 :|: v0 >= 0, z = v0 mark(z) -{ 1 }-> 1 + mark(X) :|: z = 1 + X, X >= 0 mark(z) -{ 1 }-> 1 + mark(X1) + X2 :|: X1 >= 0, X2 >= 0, z = 1 + X1 + X2 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (15) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V, V8),0,[fun(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun1(V, Out)],[V >= 0]). eq(start(V, V8),0,[mark(V, Out)],[V >= 0]). eq(start(V, V8),0,[encArg(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun2(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun3(Out)],[]). eq(start(V, V8),0,[fun4(V, V8, Out)],[V >= 0,V8 >= 0]). eq(start(V, V8),0,[fun5(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun6(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun7(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun8(V, Out)],[V >= 0]). eq(start(V, V8),0,[fun9(V, Out)],[V >= 0]). eq(fun(V, Out),1,[],[Out = 3,V = 0]). eq(fun(V, Out),1,[fun1(1 + 0, Ret0),fun(Ret0, Ret)],[Out = Ret,V = 1]). eq(fun1(V, Out),1,[],[Out = 0,V = 1]). eq(mark(V, Out),1,[mark(X3, Ret01),fun(Ret01, Ret1)],[Out = Ret1,V = 1 + X3,X3 >= 0]). eq(mark(V, Out),1,[mark(X4, Ret02),fun1(Ret02, Ret2)],[Out = Ret2,V = 1 + X4,X4 >= 0]). eq(mark(V, Out),1,[],[Out = 0,V = 0]). eq(mark(V, Out),1,[mark(X11, Ret011)],[Out = 1 + Ret011 + X21,X11 >= 0,X21 >= 0,V = 1 + X11 + X21]). eq(mark(V, Out),1,[mark(X5, Ret11)],[Out = 1 + Ret11,V = 1 + X5,X5 >= 0]). eq(fun(V, Out),1,[],[Out = 1 + X6,X6 >= 0,V = X6]). eq(fun1(V, Out),1,[],[Out = 1 + X7,X7 >= 0,V = X7]). eq(encArg(V, Out),0,[],[Out = 0,V = 0]). eq(encArg(V, Out),0,[encArg(V2, Ret012),encArg(V1, Ret12)],[Out = 1 + Ret012 + Ret12,V2 >= 0,V = 1 + V1 + V2,V1 >= 0]). eq(encArg(V, Out),0,[encArg(V3, Ret13)],[Out = 1 + Ret13,V = 1 + V3,V3 >= 0]). eq(encArg(V, Out),0,[encArg(V4, Ret03),fun(Ret03, Ret3)],[Out = Ret3,V = 1 + V4,V4 >= 0]). eq(encArg(V, Out),0,[encArg(V5, Ret04),fun1(Ret04, Ret4)],[Out = Ret4,V = 1 + V5,V5 >= 0]). eq(encArg(V, Out),0,[encArg(V6, Ret05),mark(Ret05, Ret5)],[Out = Ret5,V = 1 + V6,V6 >= 0]). eq(fun2(V, Out),0,[encArg(V7, Ret06),fun(Ret06, Ret6)],[Out = Ret6,V7 >= 0,V = V7]). eq(fun3(Out),0,[],[Out = 0]). eq(fun4(V, V8, Out),0,[encArg(V10, Ret013),encArg(V9, Ret14)],[Out = 1 + Ret013 + Ret14,V10 >= 0,V9 >= 0,V = V10,V8 = V9]). eq(fun5(V, Out),0,[encArg(V11, Ret15)],[Out = 1 + Ret15,V11 >= 0,V = V11]). eq(fun6(V, Out),0,[encArg(V12, Ret16)],[Out = 1 + Ret16,V12 >= 0,V = V12]). eq(fun7(V, Out),0,[encArg(V13, Ret07),fun1(Ret07, Ret7)],[Out = Ret7,V13 >= 0,V = V13]). eq(fun8(V, Out),0,[encArg(V14, Ret08),mark(Ret08, Ret8)],[Out = Ret8,V14 >= 0,V = V14]). eq(fun9(V, Out),0,[encArg(V15, Ret17)],[Out = 1 + Ret17,V15 >= 0,V = V15]). eq(encArg(V, Out),0,[],[Out = 0,V16 >= 0,V = V16]). eq(fun2(V, Out),0,[],[Out = 0,V17 >= 0,V = V17]). eq(fun4(V, V8, Out),0,[],[Out = 0,V19 >= 0,V18 >= 0,V = V19,V8 = V18]). eq(fun5(V, Out),0,[],[Out = 0,V20 >= 0,V = V20]). eq(fun6(V, Out),0,[],[Out = 0,V21 >= 0,V = V21]). eq(fun7(V, Out),0,[],[Out = 0,V22 >= 0,V = V22]). eq(fun8(V, Out),0,[],[Out = 0,V23 >= 0,V = V23]). eq(fun9(V, Out),0,[],[Out = 0,V24 >= 0,V = V24]). eq(mark(V, Out),0,[],[Out = 0,V25 >= 0,V = V25]). input_output_vars(fun(V,Out),[V],[Out]). input_output_vars(fun1(V,Out),[V],[Out]). input_output_vars(mark(V,Out),[V],[Out]). input_output_vars(encArg(V,Out),[V],[Out]). input_output_vars(fun2(V,Out),[V],[Out]). input_output_vars(fun3(Out),[],[Out]). input_output_vars(fun4(V,V8,Out),[V,V8],[Out]). input_output_vars(fun5(V,Out),[V],[Out]). input_output_vars(fun6(V,Out),[V],[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 : [fun1/2] 1. recursive : [fun/2] 2. recursive [non_tail] : [mark/2] 3. recursive [non_tail,multiple] : [encArg/2] 4. non_recursive : [fun2/2] 5. non_recursive : [fun3/1] 6. non_recursive : [fun4/3] 7. non_recursive : [fun5/2] 8. non_recursive : [fun6/2] 9. non_recursive : [fun7/2] 10. non_recursive : [fun8/2] 11. non_recursive : [fun9/2] 12. non_recursive : [start/2] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun1/2 1. SCC is partially evaluated into fun/2 2. SCC is partially evaluated into mark/2 3. SCC is partially evaluated into encArg/2 4. SCC is partially evaluated into fun2/2 5. SCC is completely evaluated into other SCCs 6. SCC is partially evaluated into fun4/3 7. SCC is partially evaluated into fun5/2 8. SCC is partially evaluated into fun6/2 9. SCC is partially evaluated into fun7/2 10. SCC is partially evaluated into fun8/2 11. SCC is partially evaluated into fun9/2 12. SCC is partially evaluated into start/2 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun1/2 * CE 17 is refined into CE [43] * CE 16 is refined into CE [44] ### Cost equations --> "Loop" of fun1/2 * CEs [43] --> Loop 20 * CEs [44] --> Loop 21 ### Ranking functions of CR fun1(V,Out) #### Partial ranking functions of CR fun1(V,Out) ### Specialization of cost equations fun/2 * CE 15 is refined into CE [45] * CE 13 is refined into CE [46] * CE 14 is refined into CE [47,48] ### Cost equations --> "Loop" of fun/2 * CEs [48] --> Loop 22 * CEs [47] --> Loop 23 * CEs [45] --> Loop 24 * CEs [46] --> Loop 25 ### Ranking functions of CR fun(V,Out) #### Partial ranking functions of CR fun(V,Out) ### Specialization of cost equations mark/2 * CE 20 is refined into CE [49] * CE 22 is refined into CE [50] * CE 21 is refined into CE [51] * CE 18 is refined into CE [52,53,54,55] * CE 19 is refined into CE [56,57] ### Cost equations --> "Loop" of mark/2 * CEs [51,55,57] --> Loop 26 * CEs [54] --> Loop 27 * CEs [52] --> Loop 28 * CEs [53] --> Loop 29 * CEs [56] --> Loop 30 * CEs [49,50] --> Loop 31 ### Ranking functions of CR mark(V,Out) * RF of phase [26,27,28,29,30]: [V] #### Partial ranking functions of CR mark(V,Out) * Partial RF of phase [26,27,28,29,30]: - RF of loop [26:1,27:1,28:1,29:1,30:1]: V ### Specialization of cost equations encArg/2 * CE 23 is refined into CE [58] * CE 25 is refined into CE [59] * CE 26 is refined into CE [60,61,62,63] * CE 27 is refined into CE [64,65] * CE 28 is refined into CE [66,67] * CE 24 is refined into CE [68] ### Cost equations --> "Loop" of encArg/2 * CEs [68] --> Loop 32 * CEs [59,63,65] --> Loop 33 * CEs [62] --> Loop 34 * CEs [60] --> Loop 35 * CEs [61,67] --> Loop 36 * CEs [64,66] --> Loop 37 * CEs [58] --> Loop 38 ### Ranking functions of CR encArg(V,Out) * RF of phase [32,33,34,35,36,37]: [V] #### Partial ranking functions of CR encArg(V,Out) * Partial RF of phase [32,33,34,35,36,37]: - RF of loop [32:1,32:2,33:1,34:1,35:1,36:1,37:1]: V ### Specialization of cost equations fun2/2 * CE 29 is refined into CE [69,70,71,72,73,74] * CE 30 is refined into CE [75] ### Cost equations --> "Loop" of fun2/2 * CEs [74] --> Loop 39 * CEs [69,71,73] --> Loop 40 * CEs [70,72] --> Loop 41 * CEs [75] --> Loop 42 ### Ranking functions of CR fun2(V,Out) #### Partial ranking functions of CR fun2(V,Out) ### Specialization of cost equations fun4/3 * CE 31 is refined into CE [76,77,78,79] * CE 32 is refined into CE [80] ### Cost equations --> "Loop" of fun4/3 * CEs [79] --> Loop 43 * CEs [78] --> Loop 44 * CEs [77] --> Loop 45 * CEs [76] --> Loop 46 * CEs [80] --> Loop 47 ### Ranking functions of CR fun4(V,V8,Out) #### Partial ranking functions of CR fun4(V,V8,Out) ### Specialization of cost equations fun5/2 * CE 33 is refined into CE [81,82] * CE 34 is refined into CE [83] ### Cost equations --> "Loop" of fun5/2 * CEs [82] --> Loop 48 * CEs [81] --> Loop 49 * CEs [83] --> Loop 50 ### Ranking functions of CR fun5(V,Out) #### Partial ranking functions of CR fun5(V,Out) ### Specialization of cost equations fun6/2 * CE 35 is refined into CE [84,85] * CE 36 is refined into CE [86] ### Cost equations --> "Loop" of fun6/2 * CEs [85] --> Loop 51 * CEs [84] --> Loop 52 * CEs [86] --> Loop 53 ### Ranking functions of CR fun6(V,Out) #### Partial ranking functions of CR fun6(V,Out) ### Specialization of cost equations fun7/2 * CE 37 is refined into CE [87,88,89] * CE 38 is refined into CE [90] ### Cost equations --> "Loop" of fun7/2 * CEs [89] --> Loop 54 * CEs [87] --> Loop 55 * CEs [88,90] --> Loop 56 ### Ranking functions of CR fun7(V,Out) #### Partial ranking functions of CR fun7(V,Out) ### Specialization of cost equations fun8/2 * CE 39 is refined into CE [91,92,93] * CE 40 is refined into CE [94] ### Cost equations --> "Loop" of fun8/2 * CEs [93] --> Loop 57 * CEs [91,92,94] --> Loop 58 ### Ranking functions of CR fun8(V,Out) #### Partial ranking functions of CR fun8(V,Out) ### Specialization of cost equations fun9/2 * CE 41 is refined into CE [95,96] * CE 42 is refined into CE [97] ### Cost equations --> "Loop" of fun9/2 * CEs [96] --> Loop 59 * CEs [95] --> Loop 60 * CEs [97] --> Loop 61 ### 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 [98,99,100,101] * CE 2 is refined into CE [102,103] * CE 3 is refined into CE [104,105] * CE 4 is refined into CE [106,107] * CE 5 is refined into CE [108,109,110,111] * CE 6 is refined into CE [112] * CE 7 is refined into CE [113,114,115,116,117] * CE 8 is refined into CE [118,119,120] * CE 9 is refined into CE [121,122,123] * CE 10 is refined into CE [124,125,126] * CE 11 is refined into CE [127,128] * CE 12 is refined into CE [129,130,131] ### Cost equations --> "Loop" of start/2 * CEs [98,99,100,101,102,103,104,105,106,107,108,109,110,111,112,113,114,115,116,117,118,119,120,121,122,123,124,125,126,127,128,129,130,131] --> Loop 62 ### Ranking functions of CR start(V,V8) #### Partial ranking functions of CR start(V,V8) Computing Bounds ===================================== #### Cost of chains of fun1(V,Out): * Chain [21]: 1 with precondition: [V=1,Out=0] * Chain [20]: 1 with precondition: [V+1=Out,V>=0] #### Cost of chains of fun(V,Out): * Chain [25]: 1 with precondition: [V=0,Out=3] * Chain [24]: 1 with precondition: [V+1=Out,V>=0] * Chain [23,25]: 3 with precondition: [V=1,Out=3] * Chain [23,24]: 3 with precondition: [V=1,Out=1] * Chain [22,24]: 3 with precondition: [V=1,Out=3] #### Cost of chains of mark(V,Out): * Chain [[26,27,28,29,30],31]: 14*it(26)+1 Such that:aux(3) =< V it(26) =< aux(3) with precondition: [V>=1,Out>=0,V+2>=Out,Out+V>=2] * Chain [31]: 1 with precondition: [Out=0,V>=0] #### Cost of chains of encArg(V,Out): * Chain [38]: 0 with precondition: [Out=0,V>=0] * Chain [multiple([32,33,34,35,36,37],[[38]])]: 9*it(33)+14*s(5)+0 Such that:aux(4) =< 3*V aux(5) =< V it(33) =< aux(5) s(6) =< it(33)*aux(4) s(5) =< s(6) with precondition: [V>=1,Out>=0,3*V>=Out] #### Cost of chains of fun2(V,Out): * Chain [42]: 0 with precondition: [Out=0,V>=0] * Chain [41]: 9*s(9)+14*s(11)+3 Such that:s(8) =< V s(7) =< 3*V s(9) =< s(8) s(10) =< s(9)*s(7) s(11) =< s(10) with precondition: [Out=1,V>=0] * Chain [40]: 18*s(14)+28*s(16)+3 Such that:aux(6) =< V aux(7) =< 3*V s(14) =< aux(6) s(15) =< s(14)*aux(7) s(16) =< s(15) with precondition: [Out=3,V>=0] * Chain [39]: 9*s(24)+14*s(26)+1 Such that:s(23) =< V s(22) =< 3*V s(24) =< s(23) s(25) =< s(24)*s(22) s(26) =< s(25) with precondition: [V>=1,Out>=1,3*V+1>=Out] #### Cost of chains of fun4(V,V8,Out): * Chain [47]: 0 with precondition: [Out=0,V>=0,V8>=0] * Chain [46]: 0 with precondition: [Out=1,V>=0,V8>=0] * Chain [45]: 9*s(29)+14*s(31)+0 Such that:s(28) =< V8 s(27) =< 3*V8 s(29) =< s(28) s(30) =< s(29)*s(27) s(31) =< s(30) with precondition: [V>=0,V8>=1,Out>=1,3*V8+1>=Out] * Chain [44]: 9*s(34)+14*s(36)+0 Such that:s(33) =< V s(32) =< 3*V s(34) =< s(33) s(35) =< s(34)*s(32) s(36) =< s(35) with precondition: [V>=1,V8>=0,Out>=1,3*V+1>=Out] * Chain [43]: 9*s(39)+14*s(41)+9*s(44)+14*s(46)+0 Such that:s(38) =< V s(37) =< 3*V s(43) =< V8 s(42) =< 3*V8 s(44) =< s(43) s(45) =< s(44)*s(42) s(46) =< s(45) s(39) =< s(38) s(40) =< s(39)*s(37) s(41) =< s(40) with precondition: [V>=1,V8>=1,Out>=1,3*V+3*V8+1>=Out] #### Cost of chains of fun5(V,Out): * Chain [50]: 0 with precondition: [Out=0,V>=0] * Chain [49]: 0 with precondition: [Out=1,V>=0] * Chain [48]: 9*s(49)+14*s(51)+0 Such that:s(48) =< V s(47) =< 3*V s(49) =< s(48) s(50) =< s(49)*s(47) s(51) =< s(50) with precondition: [V>=1,Out>=1,3*V+1>=Out] #### Cost of chains of fun6(V,Out): * Chain [53]: 0 with precondition: [Out=0,V>=0] * Chain [52]: 0 with precondition: [Out=1,V>=0] * Chain [51]: 9*s(54)+14*s(56)+0 Such that:s(53) =< V s(52) =< 3*V s(54) =< s(53) s(55) =< s(54)*s(52) s(56) =< s(55) with precondition: [V>=1,Out>=1,3*V+1>=Out] #### Cost of chains of fun7(V,Out): * Chain [56]: 9*s(59)+14*s(61)+1 Such that:s(58) =< V s(57) =< 3*V s(59) =< s(58) s(60) =< s(59)*s(57) s(61) =< s(60) with precondition: [Out=0,V>=0] * Chain [55]: 1 with precondition: [Out=1,V>=0] * Chain [54]: 9*s(64)+14*s(66)+1 Such that:s(63) =< V s(62) =< 3*V s(64) =< s(63) s(65) =< s(64)*s(62) s(66) =< s(65) with precondition: [V>=1,Out>=1,3*V+1>=Out] #### Cost of chains of fun8(V,Out): * Chain [58]: 9*s(69)+14*s(71)+1 Such that:s(68) =< V s(67) =< 3*V s(69) =< s(68) s(70) =< s(69)*s(67) s(71) =< s(70) with precondition: [Out=0,V>=0] * Chain [57]: 9*s(74)+14*s(76)+14*s(78)+1 Such that:s(73) =< V aux(8) =< 3*V s(78) =< aux(8) s(74) =< s(73) s(75) =< s(74)*aux(8) s(76) =< s(75) with precondition: [V>=1,Out>=0,3*V+2>=Out] #### Cost of chains of fun9(V,Out): * Chain [61]: 0 with precondition: [Out=0,V>=0] * Chain [60]: 0 with precondition: [Out=1,V>=0] * Chain [59]: 9*s(81)+14*s(83)+0 Such that:s(80) =< V s(79) =< 3*V s(81) =< s(80) s(82) =< s(81)*s(79) s(83) =< s(82) with precondition: [V>=1,Out>=1,3*V+1>=Out] #### Cost of chains of start(V,V8): * Chain [62]: 140*s(85)+196*s(90)+18*s(108)+28*s(110)+14*s(153)+3 Such that:aux(9) =< V aux(10) =< 3*V aux(11) =< V8 aux(12) =< 3*V8 s(85) =< aux(9) s(89) =< s(85)*aux(10) s(90) =< s(89) s(108) =< aux(11) s(109) =< s(108)*aux(12) s(110) =< s(109) s(153) =< aux(10) with precondition: [] Closed-form bounds of start(V,V8): ------------------------------------- * Chain [62] with precondition: [] - Upper bound: nat(V)*140+3+nat(V)*196*nat(3*V)+nat(V8)*18+nat(V8)*28*nat(3*V8)+nat(3*V)*14 - Complexity: n^2 ### Maximum cost of start(V,V8): nat(V)*140+3+nat(V)*196*nat(3*V)+nat(V8)*18+nat(V8)*28*nat(3*V8)+nat(3*V)*14 Asymptotic class: n^2 * Total analysis performed in 430 ms. ---------------------------------------- (16) BOUNDS(1, n^2) ---------------------------------------- (17) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (18) 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: a__f(0') -> cons(0', f(s(0'))) a__f(s(0')) -> a__f(a__p(s(0'))) a__p(s(0')) -> 0' mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0') -> 0' mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) The (relative) TRS S consists of the following rules: encArg(0') -> 0' encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0' encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Rewrite Strategy: FULL ---------------------------------------- (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (20) Obligation: TRS: Rules: a__f(0') -> cons(0', f(s(0'))) a__f(s(0')) -> a__f(a__p(s(0'))) a__p(s(0')) -> 0' mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0') -> 0' mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) encArg(0') -> 0' encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0' encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Types: a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark 0' :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encArg :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_0 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark hole_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark1_3 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3 :: Nat -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark ---------------------------------------- (21) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: a__f, mark, encArg They will be analysed ascendingly in the following order: a__f < mark a__f < encArg mark < encArg ---------------------------------------- (22) Obligation: TRS: Rules: a__f(0') -> cons(0', f(s(0'))) a__f(s(0')) -> a__f(a__p(s(0'))) a__p(s(0')) -> 0' mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0') -> 0' mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) encArg(0') -> 0' encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0' encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Types: a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark 0' :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encArg :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_0 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark hole_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark1_3 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3 :: Nat -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark Generator Equations: gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(0) <=> 0' gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(+(x, 1)) <=> cons(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(x), 0') The following defined symbols remain to be analysed: a__f, mark, encArg They will be analysed ascendingly in the following order: a__f < mark a__f < encArg mark < encArg ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n11_3)) -> gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n11_3), rt in Omega(1 + n11_3) Induction Base: mark(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(0)) ->_R^Omega(1) 0' Induction Step: mark(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(+(n11_3, 1))) ->_R^Omega(1) cons(mark(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n11_3)), 0') ->_IH cons(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(c12_3), 0') We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^1 for the following obligation: TRS: Rules: a__f(0') -> cons(0', f(s(0'))) a__f(s(0')) -> a__f(a__p(s(0'))) a__p(s(0')) -> 0' mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0') -> 0' mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) encArg(0') -> 0' encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0' encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Types: a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark 0' :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encArg :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_0 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark hole_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark1_3 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3 :: Nat -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark Generator Equations: gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(0) <=> 0' gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(+(x, 1)) <=> cons(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(x), 0') The following defined symbols remain to be analysed: mark, encArg They will be analysed ascendingly in the following order: mark < encArg ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) Obligation: TRS: Rules: a__f(0') -> cons(0', f(s(0'))) a__f(s(0')) -> a__f(a__p(s(0'))) a__p(s(0')) -> 0' mark(f(X)) -> a__f(mark(X)) mark(p(X)) -> a__p(mark(X)) mark(0') -> 0' mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(s(X)) -> s(mark(X)) a__f(X) -> f(X) a__p(X) -> p(X) encArg(0') -> 0' encArg(cons(x_1, x_2)) -> cons(encArg(x_1), encArg(x_2)) encArg(f(x_1)) -> f(encArg(x_1)) encArg(s(x_1)) -> s(encArg(x_1)) encArg(p(x_1)) -> p(encArg(x_1)) encArg(cons_a__f(x_1)) -> a__f(encArg(x_1)) encArg(cons_a__p(x_1)) -> a__p(encArg(x_1)) encArg(cons_mark(x_1)) -> mark(encArg(x_1)) encode_a__f(x_1) -> a__f(encArg(x_1)) encode_0 -> 0' encode_cons(x_1, x_2) -> cons(encArg(x_1), encArg(x_2)) encode_f(x_1) -> f(encArg(x_1)) encode_s(x_1) -> s(encArg(x_1)) encode_a__p(x_1) -> a__p(encArg(x_1)) encode_mark(x_1) -> mark(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) Types: a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark 0' :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encArg :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark cons_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_0 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_cons :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_f :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_s :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_a__p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_mark :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark encode_p :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark hole_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark1_3 :: 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3 :: Nat -> 0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark Lemmas: mark(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n11_3)) -> gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n11_3), rt in Omega(1 + n11_3) Generator Equations: gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(0) <=> 0' gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(+(x, 1)) <=> cons(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(x), 0') The following defined symbols remain to be analysed: encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n837_3)) -> gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n837_3), rt in Omega(0) Induction Base: encArg(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(+(n837_3, 1))) ->_R^Omega(0) cons(encArg(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n837_3)), encArg(0')) ->_IH cons(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(c838_3), encArg(0')) ->_R^Omega(0) cons(gen_0':s:f:cons:p:cons_a__f:cons_a__p:cons_mark2_3(n837_3), 0') We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (30) BOUNDS(1, INF)