/export/starexec/sandbox/solver/bin/starexec_run_rcdcRelativeAlsoLower /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^4), ?) proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^4, INF). (0) DCpxTrs (1) DerivationalComplexityToRuntimeComplexityProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxRelTRS (3) SInnermostTerminationProof [BOTH CONCRETE BOUNDS(ID, ID), 187 ms] (4) CpxRelTRS (5) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxRelTRS (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) typed CpxTrs (9) OrderProof [LOWER BOUND(ID), 8 ms] (10) typed CpxTrs (11) RewriteLemmaProof [LOWER BOUND(ID), 268 ms] (12) BEST (13) proven lower bound (14) LowerBoundPropagationProof [FINISHED, 0 ms] (15) BOUNDS(n^1, INF) (16) typed CpxTrs (17) RewriteLemmaProof [LOWER BOUND(ID), 50 ms] (18) BEST (19) proven lower bound (20) LowerBoundPropagationProof [FINISHED, 0 ms] (21) BOUNDS(n^2, INF) (22) typed CpxTrs (23) RewriteLemmaProof [LOWER BOUND(ID), 48 ms] (24) BEST (25) proven lower bound (26) LowerBoundPropagationProof [FINISHED, 0 ms] (27) BOUNDS(n^3, INF) (28) typed CpxTrs (29) RewriteLemmaProof [LOWER BOUND(ID), 1119 ms] (30) BEST (31) proven lower bound (32) LowerBoundPropagationProof [FINISHED, 0 ms] (33) BOUNDS(n^4, INF) (34) typed CpxTrs (35) RewriteLemmaProof [LOWER BOUND(ID), 33 ms] (36) BOUNDS(1, INF) ---------------------------------------- (0) Obligation: The Derivational Complexity (innermost) of the given DCpxTrs could be proven to be BOUNDS(n^4, INF). The TRS R consists of the following rules: plus(0, x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0, y) -> 0 times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0)) -> 0 p(s(s(x))) -> s(p(s(x))) fac(0, x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0)) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (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(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^4, INF). The TRS R consists of the following rules: plus(0, x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0, y) -> 0 times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0)) -> 0 p(s(s(x))) -> s(p(s(x))) fac(0, x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0)) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (3) SInnermostTerminationProof (BOTH CONCRETE BOUNDS(ID, ID)) proved innermost termination of relative rules ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^4, INF). The TRS R consists of the following rules: plus(0, x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0, y) -> 0 times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0)) -> 0 p(s(s(x))) -> s(p(s(x))) fac(0, x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0)) The (relative) TRS S consists of the following rules: encArg(0) -> 0 encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0 encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (5) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (6) Obligation: The Runtime Complexity (innermost) of the given CpxRelTRS could be proven to be BOUNDS(n^4, INF). The TRS R consists of the following rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) The (relative) TRS S consists of the following rules: encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial ---------------------------------------- (9) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: plus, p, times, fac, encArg They will be analysed ascendingly in the following order: p < plus plus < times plus < encArg p < times p < fac p < encArg times < fac times < encArg fac < encArg ---------------------------------------- (10) Obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: p, plus, times, fac, encArg They will be analysed ascendingly in the following order: p < plus plus < times plus < encArg p < times p < fac p < encArg times < fac times < encArg fac < encArg ---------------------------------------- (11) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) Induction Base: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, 0))) ->_R^Omega(1) 0' Induction Step: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, +(n4_3, 1)))) ->_R^Omega(1) s(p(s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3)))) ->_IH s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(c5_3)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (12) Complex Obligation (BEST) ---------------------------------------- (13) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: p, plus, times, fac, encArg They will be analysed ascendingly in the following order: p < plus plus < times plus < encArg p < times p < fac p < encArg times < fac times < encArg fac < encArg ---------------------------------------- (14) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (15) BOUNDS(n^1, INF) ---------------------------------------- (16) Obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: plus, times, fac, encArg They will be analysed ascendingly in the following order: plus < times plus < encArg times < fac times < encArg fac < encArg ---------------------------------------- (17) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, b)), rt in Omega(1 + n341_3 + n341_3^2) Induction Base: plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) ->_R^Omega(1) gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b) Induction Step: plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, 1)), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) ->_R^Omega(1) s(plus(p(s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3))), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b))) ->_L^Omega(1 + n341_3) s(plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b))) ->_IH s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(b, c342_3))) We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). ---------------------------------------- (18) Complex Obligation (BEST) ---------------------------------------- (19) Obligation: Proved the lower bound n^2 for the following obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: plus, times, fac, encArg They will be analysed ascendingly in the following order: plus < times plus < encArg times < fac times < encArg fac < encArg ---------------------------------------- (20) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (21) BOUNDS(n^2, INF) ---------------------------------------- (22) Obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, b)), rt in Omega(1 + n341_3 + n341_3^2) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: times, fac, encArg They will be analysed ascendingly in the following order: times < fac times < encArg fac < encArg ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n1199_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(*(n1199_3, b)), rt in Omega(1 + b*n1199_3 + b^2*n1199_3 + n1199_3 + n1199_3^2) Induction Base: times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) ->_R^Omega(1) 0' Induction Step: times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n1199_3, 1)), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) ->_R^Omega(1) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b), times(p(s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n1199_3))), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b))) ->_L^Omega(1 + n1199_3) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b), times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n1199_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b))) ->_IH plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(*(c1200_3, b))) ->_L^Omega(1 + b + b^2) gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(b, *(n1199_3, b))) We have rt in Omega(n^3) and sz in O(n). Thus, we have irc_R in Omega(n^3). ---------------------------------------- (24) Complex Obligation (BEST) ---------------------------------------- (25) Obligation: Proved the lower bound n^3 for the following obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, b)), rt in Omega(1 + n341_3 + n341_3^2) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: times, fac, encArg They will be analysed ascendingly in the following order: times < fac times < encArg fac < encArg ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^3, INF) ---------------------------------------- (28) Obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, b)), rt in Omega(1 + n341_3 + n341_3^2) times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n1199_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(*(n1199_3, b)), rt in Omega(1 + b*n1199_3 + b^2*n1199_3 + n1199_3 + n1199_3^2) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: fac, encArg They will be analysed ascendingly in the following order: fac < encArg ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: fac(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> *3_3, rt in Omega(b*n2397_3 + b*n2397_3^2 + b^2*n2397_3 + b^2*n2397_3^2 + n2397_3 + n2397_3^2 + n2397_3^3) Induction Base: fac(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) Induction Step: fac(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n2397_3, 1)), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) ->_R^Omega(1) fac(p(s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3))), times(s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3)), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b))) ->_L^Omega(1 + n2397_3) fac(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3), times(s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3)), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b))) ->_L^Omega(3 + b + b*n2397_3 + b^2 + b^2*n2397_3 + 3*n2397_3 + n2397_3^2) fac(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(*(+(n2397_3, 1), b))) ->_IH *3_3 We have rt in Omega(n^4) and sz in O(n). Thus, we have irc_R in Omega(n^4). ---------------------------------------- (30) Complex Obligation (BEST) ---------------------------------------- (31) Obligation: Proved the lower bound n^4 for the following obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, b)), rt in Omega(1 + n341_3 + n341_3^2) times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n1199_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(*(n1199_3, b)), rt in Omega(1 + b*n1199_3 + b^2*n1199_3 + n1199_3 + n1199_3^2) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: fac, encArg They will be analysed ascendingly in the following order: fac < encArg ---------------------------------------- (32) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (33) BOUNDS(n^4, INF) ---------------------------------------- (34) Obligation: Innermost TRS: Rules: plus(0', x) -> x plus(s(x), y) -> s(plus(p(s(x)), y)) times(0', y) -> 0' times(s(x), y) -> plus(y, times(p(s(x)), y)) p(s(0')) -> 0' p(s(s(x))) -> s(p(s(x))) fac(0', x) -> x fac(s(x), y) -> fac(p(s(x)), times(s(x), y)) factorial(x) -> fac(x, s(0')) encArg(0') -> 0' encArg(s(x_1)) -> s(encArg(x_1)) encArg(cons_plus(x_1, x_2)) -> plus(encArg(x_1), encArg(x_2)) encArg(cons_times(x_1, x_2)) -> times(encArg(x_1), encArg(x_2)) encArg(cons_p(x_1)) -> p(encArg(x_1)) encArg(cons_fac(x_1, x_2)) -> fac(encArg(x_1), encArg(x_2)) encArg(cons_factorial(x_1)) -> factorial(encArg(x_1)) encode_plus(x_1, x_2) -> plus(encArg(x_1), encArg(x_2)) encode_0 -> 0' encode_s(x_1) -> s(encArg(x_1)) encode_p(x_1) -> p(encArg(x_1)) encode_times(x_1, x_2) -> times(encArg(x_1), encArg(x_2)) encode_fac(x_1, x_2) -> fac(encArg(x_1), encArg(x_2)) encode_factorial(x_1) -> factorial(encArg(x_1)) Types: plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial 0' :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encArg :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial cons_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_plus :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_0 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_s :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_p :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_times :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_fac :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial encode_factorial :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial hole_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial1_3 :: 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3 :: Nat -> 0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial Lemmas: p(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(1, n4_3))) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n4_3), rt in Omega(1 + n4_3) plus(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n341_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n341_3, b)), rt in Omega(1 + n341_3 + n341_3^2) times(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n1199_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(*(n1199_3, b)), rt in Omega(1 + b*n1199_3 + b^2*n1199_3 + n1199_3 + n1199_3^2) fac(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n2397_3), gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(b)) -> *3_3, rt in Omega(b*n2397_3 + b*n2397_3^2 + b^2*n2397_3 + b^2*n2397_3^2 + n2397_3 + n2397_3^2 + n2397_3^3) Generator Equations: gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0) <=> 0' gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(x, 1)) <=> s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(x)) The following defined symbols remain to be analysed: encArg ---------------------------------------- (35) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: encArg(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n5249_3)) -> gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n5249_3), rt in Omega(0) Induction Base: encArg(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(0)) ->_R^Omega(0) 0' Induction Step: encArg(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(+(n5249_3, 1))) ->_R^Omega(0) s(encArg(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(n5249_3))) ->_IH s(gen_0':s:cons_plus:cons_times:cons_p:cons_fac:cons_factorial2_3(c5250_3)) We have rt in Omega(1) and sz in O(n). Thus, we have irc_R in Omega(n^0). ---------------------------------------- (36) BOUNDS(1, INF)