/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^2), O(n^2)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). (0) CpxTRS (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] (2) CpxTRS (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxTRS (5) RelTrsToWeightedTrsProof [BOTH BOUNDS(ID, ID), 0 ms] (6) CpxWeightedTrs (7) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CpxTypedWeightedTrs (9) CompletionProof [UPPER BOUND(ID), 0 ms] (10) CpxTypedWeightedCompleteTrs (11) CpxTypedWeightedTrsToRntsProof [UPPER BOUND(ID), 0 ms] (12) CpxRNTS (13) CompleteCoflocoProof [FINISHED, 1157 ms] (14) BOUNDS(1, n^2) (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (16) CpxTRS (17) SlicingProof [LOWER BOUND(ID), 0 ms] (18) CpxTRS (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), 219 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), 774 ms] (30) typed CpxTrs (31) RewriteLemmaProof [LOWER BOUND(ID), 640 ms] (32) typed CpxTrs (33) RewriteLemmaProof [LOWER BOUND(ID), 27 ms] (34) proven lower bound (35) LowerBoundPropagationProof [FINISHED, 0 ms] (36) BOUNDS(n^2, INF) ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, n^2). The TRS R consists of the following rules: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var(x), Id) -> Term_var(x) Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(xi, Id) -> Sum_term_var(xi) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) Concat(Id, s) -> s S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) The following defined symbols can occur below the 1th argument of Frozen: Sum_sub Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var(x), Id) -> Term_var(x) Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) Sum_sub(xi, Id) -> Sum_term_var(xi) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) Concat(Id, s) -> s S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. The duplicating contexts are: Term_sub(Case(m, xi, n), []) Frozen(m, Sum_term_var(xi), n, []) Term_sub(Term_app(m, n), []) Term_sub(Term_pair(m, n), []) Concat(Cons_usual(x, m, s), []) The defined contexts are: Frozen(x0, [], x2, x3) [] just represents basic- or constructor-terms in the following defined contexts: Frozen(x0, [], x2, x3) As the TRS is an overlay system and the defined contexts and the duplicating contexts don't overlap, we have rc = irc. ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^2). The TRS R consists of the following rules: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var(x), Id) -> Term_var(x) Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) Sum_sub(xi, Id) -> Sum_term_var(xi) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) Concat(Id, s) -> s S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (5) RelTrsToWeightedTrsProof (BOTH BOUNDS(ID, ID)) Transformed relative TRS to weighted TRS ---------------------------------------- (6) 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: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) [1] Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) [1] Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) [1] Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) [1] Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) [1] Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) [1] Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) [1] Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) [1] Term_sub(Term_var(x), Id) -> Term_var(x) [1] Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m [1] Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) [1] Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) [1] Sum_sub(xi, Id) -> Sum_term_var(xi) [1] Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) [1] Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) [1] Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) [1] Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) [1] Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) [1] Concat(Id, s) -> s [1] Rewrite Strategy: INNERMOST ---------------------------------------- (7) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (8) Obligation: Runtime Complexity Weighted TRS with Types. The TRS R consists of the following rules: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) [1] Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) [1] Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) [1] Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) [1] Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) [1] Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) [1] Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) [1] Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) [1] Term_sub(Term_var(x), Id) -> Term_var(x) [1] Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m [1] Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) [1] Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) [1] Sum_sub(xi, Id) -> Sum_term_var(xi) [1] Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) [1] Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) [1] Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) [1] Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) [1] Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) [1] Concat(Id, s) -> s [1] The TRS has the following type information: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> a -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: a -> Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: a -> Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: b -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: c -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: d -> Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Rewrite Strategy: INNERMOST ---------------------------------------- (9) 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: Term_sub(v0, v1) -> null_Term_sub [0] Frozen(v0, v1, v2, v3) -> null_Frozen [0] And the following fresh constants: null_Term_sub, null_Frozen, const, const1, const2, const3, const4 ---------------------------------------- (10) 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: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) [1] Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) [1] Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) [1] Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) [1] Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) [1] Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) [1] Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) [1] Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) [1] Term_sub(Term_var(x), Id) -> Term_var(x) [1] Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m [1] Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) [1] Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) [1] Sum_sub(xi, Id) -> Sum_term_var(xi) [1] Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) [1] Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) [1] Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) [1] Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) [1] Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) [1] Concat(Id, s) -> s [1] Term_sub(v0, v1) -> null_Term_sub [0] Frozen(v0, v1, v2, v3) -> null_Frozen [0] The TRS has the following type information: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> a -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Sum_sub :: a -> Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: a -> Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Term_var :: b -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen Id :: Id:Cons_usual:Cons_sum Cons_usual :: c -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: d -> Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum null_Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen null_Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var:null_Term_sub:null_Frozen const :: a const1 :: Sum_constant:Sum_term_var const2 :: b const3 :: c const4 :: d Rewrite Strategy: INNERMOST ---------------------------------------- (11) CpxTypedWeightedTrsToRntsProof (UPPER BOUND(ID)) Transformed the TRS into an over-approximating RNTS by (improved) Size Abstraction. The constant constructors are abstracted as follows: Left => 0 Right => 1 Id => 0 null_Term_sub => 0 null_Frozen => 0 const => 0 const1 => 0 const2 => 0 const3 => 0 const4 => 0 ---------------------------------------- (12) Obligation: Complexity RNTS consisting of the following rules: Concat(z, z') -{ 1 }-> s :|: s >= 0, z = 0, z' = s Concat(z, z') -{ 1 }-> 1 + x + Term_sub(m, t) + Concat(s, t) :|: z' = t, x >= 0, t >= 0, s >= 0, z = 1 + x + m + s, m >= 0 Concat(z, z') -{ 1 }-> 1 + xi + k + Concat(s, t) :|: z' = t, t >= 0, k >= 0, s >= 0, z = 1 + xi + k + s, xi >= 0 Frozen(z, z', z'', z1) -{ 1 }-> Term_sub(m, s) :|: z = m, n >= 0, z'' = n, z1 = s, z' = 1 + 0, s >= 0, m >= 0 Frozen(z, z', z'', z1) -{ 1 }-> Term_sub(n, s) :|: z = m, z' = 1 + 1, n >= 0, z'' = n, z1 = s, s >= 0, m >= 0 Frozen(z, z', z'', z1) -{ 0 }-> 0 :|: z1 = v3, v0 >= 0, z'' = v2, v1 >= 0, z = v0, z' = v1, v2 >= 0, v3 >= 0 Frozen(z, z', z'', z1) -{ 1 }-> 1 + Term_sub(m, s) + xi + Term_sub(n, s) :|: z = m, n >= 0, z'' = n, z1 = s, z' = 1 + xi, s >= 0, xi >= 0, m >= 0 Sum_sub(z, z') -{ 1 }-> Sum_sub(xi, s) :|: z' = 1 + psi + k + s, z = xi, psi >= 0, k >= 0, s >= 0, xi >= 0 Sum_sub(z, z') -{ 1 }-> Sum_sub(xi, s) :|: y >= 0, z = xi, z' = 1 + y + m + s, s >= 0, xi >= 0, m >= 0 Sum_sub(z, z') -{ 1 }-> 1 + k :|: z' = 1 + psi + k + s, z = xi, psi >= 0, k >= 0, s >= 0, xi >= 0 Sum_sub(z, z') -{ 1 }-> 1 + xi :|: z = xi, xi >= 0, z' = 0 Term_sub(z, z') -{ 1 }-> m :|: x >= 0, y >= 0, z = 1 + x, z' = 1 + y + m + s, s >= 0, m >= 0 Term_sub(z, z') -{ 1 }-> Term_sub(1 + x, s) :|: x >= 0, y >= 0, z = 1 + x, z' = 1 + y + m + s, s >= 0, m >= 0 Term_sub(z, z') -{ 1 }-> Term_sub(1 + x, s) :|: z' = 1 + xi + k + s, x >= 0, z = 1 + x, k >= 0, s >= 0, xi >= 0 Term_sub(z, z') -{ 1 }-> Frozen(m, Sum_sub(xi, s), n, s) :|: z = 1 + m + xi + n, n >= 0, s >= 0, z' = s, xi >= 0, m >= 0 Term_sub(z, z') -{ 0 }-> 0 :|: v0 >= 0, v1 >= 0, z = v0, z' = v1 Term_sub(z, z') -{ 1 }-> 1 + x :|: x >= 0, z = 1 + x, z' = 0 Term_sub(z, z') -{ 1 }-> 1 + Term_sub(m, s) :|: s >= 0, z' = s, z = 1 + m, m >= 0 Term_sub(z, z') -{ 1 }-> 1 + Term_sub(m, s) + Term_sub(n, s) :|: n >= 0, z = 1 + m + n, s >= 0, z' = s, m >= 0 Only complete derivations are relevant for the runtime complexity. ---------------------------------------- (13) CompleteCoflocoProof (FINISHED) Transformed the RNTS (where only complete derivations are relevant) into cost relations for CoFloCo: eq(start(V1, V, V6, V10),0,[fun(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V6, V10),0,[fun1(V1, V, V6, V10, Out)],[V1 >= 0,V >= 0,V6 >= 0,V10 >= 0]). eq(start(V1, V, V6, V10),0,[fun2(V1, V, Out)],[V1 >= 0,V >= 0]). eq(start(V1, V, V6, V10),0,[fun3(V1, V, Out)],[V1 >= 0,V >= 0]). eq(fun(V1, V, Out),1,[fun2(V2, V3, Ret1),fun1(V4, Ret1, V5, V3, Ret)],[Out = Ret,V1 = 1 + V2 + V4 + V5,V5 >= 0,V3 >= 0,V = V3,V2 >= 0,V4 >= 0]). eq(fun1(V1, V, V6, V10, Out),1,[fun(V9, V7, Ret2)],[Out = Ret2,V1 = V9,V8 >= 0,V6 = V8,V10 = V7,V = 1,V7 >= 0,V9 >= 0]). eq(fun1(V1, V, V6, V10, Out),1,[fun(V12, V11, Ret3)],[Out = Ret3,V1 = V13,V = 2,V12 >= 0,V6 = V12,V10 = V11,V11 >= 0,V13 >= 0]). eq(fun1(V1, V, V6, V10, Out),1,[fun(V17, V15, Ret001),fun(V16, V15, Ret11)],[Out = 1 + Ret001 + Ret11 + V14,V1 = V17,V16 >= 0,V6 = V16,V10 = V15,V = 1 + V14,V15 >= 0,V14 >= 0,V17 >= 0]). eq(fun(V1, V, Out),1,[fun(V19, V18, Ret01),fun(V20, V18, Ret12)],[Out = 1 + Ret01 + Ret12,V20 >= 0,V1 = 1 + V19 + V20,V18 >= 0,V = V18,V19 >= 0]). eq(fun(V1, V, Out),1,[fun(V22, V21, Ret13)],[Out = 1 + Ret13,V21 >= 0,V = V21,V1 = 1 + V22,V22 >= 0]). eq(fun(V1, V, Out),1,[],[Out = 1 + V23,V23 >= 0,V1 = 1 + V23,V = 0]). eq(fun(V1, V, Out),1,[],[Out = V24,V25 >= 0,V27 >= 0,V1 = 1 + V25,V = 1 + V24 + V26 + V27,V26 >= 0,V24 >= 0]). eq(fun(V1, V, Out),1,[fun(1 + V28, V30, Ret4)],[Out = Ret4,V28 >= 0,V31 >= 0,V1 = 1 + V28,V = 1 + V29 + V30 + V31,V30 >= 0,V29 >= 0]). eq(fun(V1, V, Out),1,[fun(1 + V32, V34, Ret5)],[Out = Ret5,V = 1 + V33 + V34 + V35,V32 >= 0,V1 = 1 + V32,V35 >= 0,V34 >= 0,V33 >= 0]). eq(fun2(V1, V, Out),1,[],[Out = 1 + V36,V1 = V36,V36 >= 0,V = 0]). eq(fun2(V1, V, Out),1,[],[Out = 1 + V40,V = 1 + V37 + V38 + V40,V1 = V39,V37 >= 0,V40 >= 0,V38 >= 0,V39 >= 0]). eq(fun2(V1, V, Out),1,[fun2(V44, V43, Ret6)],[Out = Ret6,V = 1 + V41 + V42 + V43,V1 = V44,V41 >= 0,V42 >= 0,V43 >= 0,V44 >= 0]). eq(fun2(V1, V, Out),1,[fun2(V47, V48, Ret7)],[Out = Ret7,V46 >= 0,V1 = V47,V = 1 + V45 + V46 + V48,V48 >= 0,V47 >= 0,V45 >= 0]). eq(fun3(V1, V, Out),1,[fun(V51, V50, Ret011),fun3(V52, V50, Ret14)],[Out = 1 + Ret011 + Ret14 + V49,V = V50,V49 >= 0,V50 >= 0,V52 >= 0,V1 = 1 + V49 + V51 + V52,V51 >= 0]). eq(fun3(V1, V, Out),1,[fun3(V54, V53, Ret15)],[Out = 1 + Ret15 + V55 + V56,V = V53,V53 >= 0,V56 >= 0,V54 >= 0,V1 = 1 + V54 + V55 + V56,V55 >= 0]). eq(fun3(V1, V, Out),1,[],[Out = V57,V57 >= 0,V1 = 0,V = V57]). eq(fun(V1, V, Out),0,[],[Out = 0,V59 >= 0,V58 >= 0,V1 = V59,V = V58]). eq(fun1(V1, V, V6, V10, Out),0,[],[Out = 0,V10 = V62,V61 >= 0,V6 = V63,V60 >= 0,V1 = V61,V = V60,V63 >= 0,V62 >= 0]). input_output_vars(fun(V1,V,Out),[V1,V],[Out]). input_output_vars(fun1(V1,V,V6,V10,Out),[V1,V,V6,V10],[Out]). input_output_vars(fun2(V1,V,Out),[V1,V],[Out]). input_output_vars(fun3(V1,V,Out),[V1,V],[Out]). CoFloCo proof output: Preprocessing Cost Relations ===================================== #### Computed strongly connected components 0. recursive : [fun2/3] 1. recursive [multiple] : [fun/3,fun1/5] 2. recursive : [fun3/3] 3. non_recursive : [start/4] #### Obtained direct recursion through partial evaluation 0. SCC is partially evaluated into fun2/3 1. SCC is partially evaluated into fun/3 2. SCC is partially evaluated into fun3/3 3. SCC is partially evaluated into start/4 Control-Flow Refinement of Cost Relations ===================================== ### Specialization of cost equations fun2/3 * CE 20 is refined into CE [24] * CE 19 is refined into CE [25] * CE 18 is refined into CE [26] ### Cost equations --> "Loop" of fun2/3 * CEs [25] --> Loop 15 * CEs [26] --> Loop 16 * CEs [24] --> Loop 17 ### Ranking functions of CR fun2(V1,V,Out) * RF of phase [17]: [V] #### Partial ranking functions of CR fun2(V1,V,Out) * Partial RF of phase [17]: - RF of loop [17:1]: V ### Specialization of cost equations fun/3 * CE 15 is refined into CE [27] * CE 8 is refined into CE [28,29,30] * CE 17 is refined into CE [31] * CE 14 is refined into CE [32] * CE 10 is refined into CE [33,34,35] * CE 11 is refined into CE [36,37,38] * CE 16 is refined into CE [39] * CE 13 is refined into CE [40] * CE 9 is refined into CE [41,42,43] * CE 12 is refined into CE [44] ### Cost equations --> "Loop" of fun/3 * CEs [43] --> Loop 18 * CEs [42] --> Loop 19 * CEs [44] --> Loop 20 * CEs [41] --> Loop 21 * CEs [34,35,37,38] --> Loop 22 * CEs [39] --> Loop 23 * CEs [40] --> Loop 24 * CEs [33,36] --> Loop 25 * CEs [27] --> Loop 26 * CEs [32] --> Loop 27 * CEs [28,29,30,31] --> Loop 28 ### Ranking functions of CR fun(V1,V,Out) * RF of phase [18,19,20,21,22,23,24,25]: [V1+V] #### Partial ranking functions of CR fun(V1,V,Out) * Partial RF of phase [18,19,20,21,22,23,24,25]: - RF of loop [18:1,18:2,19:1,19:2,20:1,20:2,21:1,21:2,22:1,24:1,25:1]: V1 - RF of loop [23:1]: V ### Specialization of cost equations fun3/3 * CE 23 is refined into CE [45] * CE 21 is refined into CE [46,47] * CE 22 is refined into CE [48] ### Cost equations --> "Loop" of fun3/3 * CEs [46] --> Loop 29 * CEs [47,48] --> Loop 30 * CEs [45] --> Loop 31 ### Ranking functions of CR fun3(V1,V,Out) * RF of phase [29,30]: [V1] #### Partial ranking functions of CR fun3(V1,V,Out) * Partial RF of phase [29,30]: - RF of loop [29:1]: V1-1 - RF of loop [30:1]: V1 ### Specialization of cost equations start/4 * CE 3 is refined into CE [49,50] * CE 1 is refined into CE [51] * CE 2 is refined into CE [52,53,54,55] * CE 4 is refined into CE [56,57] * CE 5 is refined into CE [58,59] * CE 6 is refined into CE [60,61,62] * CE 7 is refined into CE [63,64] ### Cost equations --> "Loop" of start/4 * CEs [49,50] --> Loop 32 * CEs [56,57] --> Loop 33 * CEs [60] --> Loop 34 * CEs [51,52,53,54,55,58,59,61,62,63,64] --> Loop 35 ### Ranking functions of CR start(V1,V,V6,V10) #### Partial ranking functions of CR start(V1,V,V6,V10) Computing Bounds ===================================== #### Cost of chains of fun2(V1,V,Out): * Chain [[17],16]: 1*it(17)+1 Such that:it(17) =< V with precondition: [V1+1=Out,V1>=0,V>=1] * Chain [[17],15]: 1*it(17)+1 Such that:it(17) =< V-Out with precondition: [V1>=0,Out>=1,V>=Out+1] * Chain [16]: 1 with precondition: [V=0,V1+1=Out,V1>=0] * Chain [15]: 1 with precondition: [V1>=0,Out>=1,V>=Out] #### Cost of chains of fun(V1,V,Out): * Chain [28]: 2*s(2)+2 Such that:aux(1) =< V s(2) =< aux(1) with precondition: [Out=0,V1>=0,V>=0] * Chain [27]: 1 with precondition: [V=0,V1=Out,V1>=1] * Chain [26]: 1 with precondition: [V1>=1,Out>=0,V>=Out+1] * Chain [multiple([18,19,20,21,22,23,24,25],[[28],[27],[26]])]: 10*it(18)+7*it(22)+1*it(23)+1*it([26])+1*it([27])+2*it([28])+1*s(16)+1*s(17)+4*s(18)+2*s(22)+0 Such that:it([28]) =< V1+1 aux(10) =< V1+2*V aux(33) =< V1 aux(34) =< V1+V aux(35) =< V1/2+1/2 aux(36) =< V it(18) =< aux(33) it(22) =< aux(33) it([26]) =< aux(33) it([27]) =< aux(33) it([26]) =< aux(35) it([27]) =< aux(35) aux(5) =< aux(36) aux(20) =< aux(36)*2 aux(11) =< aux(10) aux(6) =< it(18)*aux(10) s(16) =< it(18)*aux(36) aux(16) =< it(18)*aux(20) s(23) =< it([28])*aux(5) aux(7) =< it(18)*aux(11) s(17) =< it(18)*aux(5) it(22) =< aux(7)+aux(7)+aux(6)+aux(34) it(23) =< aux(7)+aux(7)+aux(6)+aux(34) it([26]) =< aux(7)+aux(7)+aux(6)+aux(34) it([27]) =< aux(7)+aux(7)+aux(6)+aux(34) s(23) =< aux(7)+aux(7)+aux(6)+aux(34) it(23) =< aux(16)+aux(16)+aux(16)+aux(36) it([26]) =< aux(16)+aux(16)+aux(16)+aux(36) s(23) =< aux(16)+aux(16)+aux(16)+aux(36) s(20) =< it(22)*aux(5) s(22) =< s(23) s(18) =< s(20) with precondition: [V1>=1,V>=0,Out>=0] #### Cost of chains of fun3(V1,V,Out): * Chain [[29,30],31]: 17*it(29)+7*s(97)+1*s(98)+1*s(99)+1*s(100)+1*s(101)+1*s(102)+2*s(103)+4*s(104)+2*s(114)+1 Such that:aux(38) =< V1+V s(71) =< V1+2*V s(73) =< V aux(44) =< V1 it(29) =< aux(44) aux(40) =< s(73) s(112) =< aux(44)*(1/2) s(109) =< it(29)*aux(38) s(107) =< it(29)*aux(40) s(114) =< s(107) s(97) =< aux(44) s(98) =< aux(44) s(99) =< aux(44) s(98) =< s(112) s(99) =< s(112) s(80) =< s(73)*2 s(81) =< s(71) s(110) =< it(29)*s(71) s(100) =< it(29)*s(73) s(108) =< it(29)*s(80) s(106) =< it(29)*aux(40) s(111) =< it(29)*s(81) s(101) =< it(29)*aux(40) s(97) =< s(111)+s(111)+s(110)+s(109) s(102) =< s(111)+s(111)+s(110)+s(109) s(98) =< s(111)+s(111)+s(110)+s(109) s(99) =< s(111)+s(111)+s(110)+s(109) s(106) =< s(111)+s(111)+s(110)+s(109) s(102) =< s(108)+s(108)+s(108)+s(107) s(98) =< s(108)+s(108)+s(108)+s(107) s(106) =< s(108)+s(108)+s(108)+s(107) s(105) =< s(97)*aux(40) s(103) =< s(106) s(104) =< s(105) with precondition: [V1>=1,V>=0,Out>=V+1] * Chain [31]: 1 with precondition: [V1=0,V=Out,V>=0] #### Cost of chains of start(V1,V,V6,V10): * Chain [35]: 6*s(117)+47*s(122)+14*s(123)+2*s(124)+2*s(125)+2*s(130)+2*s(134)+2*s(135)+4*s(137)+8*s(138)+4*s(140)+20*s(145)+14*s(146)+2*s(147)+2*s(148)+2*s(153)+2*s(157)+2*s(158)+4*s(160)+8*s(161)+8*s(186)+7*s(223)+1*s(224)+1*s(225)+2*s(230)+2*s(234)+1*s(235)+2*s(237)+4*s(238)+4*s(240)+2*s(252)+7*s(253)+1*s(254)+1*s(255)+1*s(264)+2*s(266)+4*s(267)+5 Such that:aux(49) =< V1 aux(50) =< V1+1 aux(51) =< V1+V aux(52) =< V1+2*V aux(53) =< V1+V10 aux(54) =< V1+2*V10 aux(55) =< V1/2+1/2 aux(56) =< V aux(57) =< V6 aux(58) =< V6+1 aux(59) =< V6+V10 aux(60) =< V6+2*V10 aux(61) =< V6/2+1/2 aux(62) =< V10 s(117) =< aux(50) s(240) =< aux(56) s(140) =< aux(58) s(145) =< aux(57) s(146) =< aux(57) s(147) =< aux(57) s(148) =< aux(57) s(147) =< aux(61) s(148) =< aux(61) s(126) =< aux(62) s(127) =< aux(62)*2 s(151) =< aux(60) s(152) =< s(145)*aux(60) s(153) =< s(145)*aux(62) s(154) =< s(145)*s(127) s(155) =< s(140)*s(126) s(156) =< s(145)*s(151) s(157) =< s(145)*s(126) s(146) =< s(156)+s(156)+s(152)+aux(59) s(158) =< s(156)+s(156)+s(152)+aux(59) s(147) =< s(156)+s(156)+s(152)+aux(59) s(148) =< s(156)+s(156)+s(152)+aux(59) s(155) =< s(156)+s(156)+s(152)+aux(59) s(158) =< s(154)+s(154)+s(154)+aux(62) s(147) =< s(154)+s(154)+s(154)+aux(62) s(155) =< s(154)+s(154)+s(154)+aux(62) s(159) =< s(146)*s(126) s(160) =< s(155) s(161) =< s(159) s(122) =< aux(49) s(123) =< aux(49) s(124) =< aux(49) s(125) =< aux(49) s(124) =< aux(55) s(125) =< aux(55) s(128) =< aux(54) s(129) =< s(122)*aux(54) s(130) =< s(122)*aux(62) s(131) =< s(122)*s(127) s(132) =< s(117)*s(126) s(133) =< s(122)*s(128) s(134) =< s(122)*s(126) s(123) =< s(133)+s(133)+s(129)+aux(53) s(135) =< s(133)+s(133)+s(129)+aux(53) s(124) =< s(133)+s(133)+s(129)+aux(53) s(125) =< s(133)+s(133)+s(129)+aux(53) s(132) =< s(133)+s(133)+s(129)+aux(53) s(135) =< s(131)+s(131)+s(131)+aux(62) s(124) =< s(131)+s(131)+s(131)+aux(62) s(132) =< s(131)+s(131)+s(131)+aux(62) s(136) =< s(123)*s(126) s(137) =< s(132) s(138) =< s(136) s(186) =< aux(62) s(223) =< aux(49) s(224) =< aux(49) s(225) =< aux(49) s(224) =< aux(55) s(225) =< aux(55) s(226) =< aux(56) s(227) =< aux(56)*2 s(228) =< aux(52) s(229) =< s(122)*aux(52) s(230) =< s(122)*aux(56) s(231) =< s(122)*s(227) s(232) =< s(117)*s(226) s(233) =< s(122)*s(228) s(234) =< s(122)*s(226) s(223) =< s(233)+s(233)+s(229)+aux(51) s(235) =< s(233)+s(233)+s(229)+aux(51) s(224) =< s(233)+s(233)+s(229)+aux(51) s(225) =< s(233)+s(233)+s(229)+aux(51) s(232) =< s(233)+s(233)+s(229)+aux(51) s(235) =< s(231)+s(231)+s(231)+aux(56) s(224) =< s(231)+s(231)+s(231)+aux(56) s(232) =< s(231)+s(231)+s(231)+aux(56) s(236) =< s(223)*s(226) s(237) =< s(232) s(238) =< s(236) s(249) =< aux(49)*(1/2) s(250) =< s(122)*aux(51) s(251) =< s(122)*s(226) s(252) =< s(251) s(253) =< aux(49) s(254) =< aux(49) s(255) =< aux(49) s(254) =< s(249) s(255) =< s(249) s(261) =< s(122)*s(226) s(253) =< s(233)+s(233)+s(229)+s(250) s(264) =< s(233)+s(233)+s(229)+s(250) s(254) =< s(233)+s(233)+s(229)+s(250) s(255) =< s(233)+s(233)+s(229)+s(250) s(261) =< s(233)+s(233)+s(229)+s(250) s(264) =< s(231)+s(231)+s(231)+s(251) s(254) =< s(231)+s(231)+s(231)+s(251) s(261) =< s(231)+s(231)+s(231)+s(251) s(265) =< s(253)*s(226) s(266) =< s(261) s(267) =< s(265) with precondition: [V1>=0,V>=0] * Chain [34]: 1 with precondition: [V=0,V1>=0] * Chain [33]: 2*s(269)+10*s(274)+7*s(275)+1*s(276)+1*s(277)+1*s(282)+1*s(286)+1*s(287)+2*s(289)+4*s(290)+2*s(292)+3 Such that:s(268) =< V1 s(269) =< V1+1 s(270) =< V1+V10 s(271) =< V1+2*V10 s(272) =< V1/2+1/2 aux(63) =< V10 s(274) =< s(268) s(275) =< s(268) s(276) =< s(268) s(277) =< s(268) s(276) =< s(272) s(277) =< s(272) s(278) =< aux(63) s(279) =< aux(63)*2 s(280) =< s(271) s(281) =< s(274)*s(271) s(282) =< s(274)*aux(63) s(283) =< s(274)*s(279) s(284) =< s(269)*s(278) s(285) =< s(274)*s(280) s(286) =< s(274)*s(278) s(275) =< s(285)+s(285)+s(281)+s(270) s(287) =< s(285)+s(285)+s(281)+s(270) s(276) =< s(285)+s(285)+s(281)+s(270) s(277) =< s(285)+s(285)+s(281)+s(270) s(284) =< s(285)+s(285)+s(281)+s(270) s(287) =< s(283)+s(283)+s(283)+aux(63) s(276) =< s(283)+s(283)+s(283)+aux(63) s(284) =< s(283)+s(283)+s(283)+aux(63) s(288) =< s(275)*s(278) s(289) =< s(284) s(290) =< s(288) s(292) =< aux(63) with precondition: [V=1,V1>=0,V6>=0,V10>=0] * Chain [32]: 2*s(294)+10*s(299)+7*s(300)+1*s(301)+1*s(302)+1*s(307)+1*s(311)+1*s(312)+2*s(314)+4*s(315)+2*s(317)+3 Such that:s(293) =< V6 s(294) =< V6+1 s(295) =< V6+V10 s(296) =< V6+2*V10 s(297) =< V6/2+1/2 aux(64) =< V10 s(299) =< s(293) s(300) =< s(293) s(301) =< s(293) s(302) =< s(293) s(301) =< s(297) s(302) =< s(297) s(303) =< aux(64) s(304) =< aux(64)*2 s(305) =< s(296) s(306) =< s(299)*s(296) s(307) =< s(299)*aux(64) s(308) =< s(299)*s(304) s(309) =< s(294)*s(303) s(310) =< s(299)*s(305) s(311) =< s(299)*s(303) s(300) =< s(310)+s(310)+s(306)+s(295) s(312) =< s(310)+s(310)+s(306)+s(295) s(301) =< s(310)+s(310)+s(306)+s(295) s(302) =< s(310)+s(310)+s(306)+s(295) s(309) =< s(310)+s(310)+s(306)+s(295) s(312) =< s(308)+s(308)+s(308)+aux(64) s(301) =< s(308)+s(308)+s(308)+aux(64) s(309) =< s(308)+s(308)+s(308)+aux(64) s(313) =< s(300)*s(303) s(314) =< s(309) s(315) =< s(313) s(317) =< aux(64) with precondition: [V=2,V1>=0,V6>=0,V10>=0] Closed-form bounds of start(V1,V,V6,V10): ------------------------------------- * Chain [35] with precondition: [V1>=0,V>=0] - Upper bound: 83*V1+5+16*V1*V+12*V1*nat(V10)+(V1+V)*V1+(V1+2*V)*(6*V1)+6*V1*nat(V1+2*V10)+4*V+(V1+1)*(2*V)+nat(V6)*38+nat(V6)*12*nat(V10)+nat(V6)*6*nat(V6+2*V10)+nat(V10)*8+(V1+1)*(nat(V10)*4)+nat(V10)*4*nat(V6+1)+(V1+V)+nat(V1+V10)*2+(6*V1+6)+nat(V6+V10)*2+nat(V6+1)*4 - Complexity: n^2 * Chain [34] with precondition: [V=0,V1>=0] - Upper bound: 1 - Complexity: constant * Chain [33] with precondition: [V=1,V1>=0,V6>=0,V10>=0] - Upper bound: 19*V1+3+6*V1*V10+(V1+2*V10)*(3*V1)+2*V10+(V1+1)*(2*V10)+(V1+V10)+(2*V1+2) - Complexity: n^2 * Chain [32] with precondition: [V=2,V1>=0,V6>=0,V10>=0] - Upper bound: 19*V6+3+6*V6*V10+(V6+2*V10)*(3*V6)+2*V10+(V6+1)*(2*V10)+(V6+V10)+(2*V6+2) - Complexity: n^2 ### Maximum cost of start(V1,V,V6,V10): nat(V10)*2+2+max([nat(V6)*6*nat(V10)+nat(V6)*19+nat(V6)*3*nat(V6+2*V10)+nat(V10)*2*nat(V6+1)+nat(V6+V10)+nat(V6+1)*2,64*V1+2+16*V1*V+6*V1*nat(V10)+(V1+V)*V1+(V1+2*V)*(6*V1)+3*V1*nat(V1+2*V10)+4*V+(V1+1)*(2*V)+nat(V6)*38+nat(V6)*12*nat(V10)+nat(V6)*6*nat(V6+2*V10)+nat(V10)*6+(V1+1)*(nat(V10)*2)+nat(V10)*4*nat(V6+1)+(V1+V)+nat(V1+V10)+(4*V1+4)+nat(V6+V10)*2+nat(V6+1)*4+(6*V1*nat(V10)+19*V1+3*V1*nat(V1+2*V10)+(V1+1)*(nat(V10)*2)+nat(V1+V10)+(2*V1+2))])+1 Asymptotic class: n^2 * Total analysis performed in 970 ms. ---------------------------------------- (14) BOUNDS(1, n^2) ---------------------------------------- (15) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (16) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). The TRS R consists of the following rules: Term_sub(Case(m, xi, n), s) -> Frozen(m, Sum_sub(xi, s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var(xi), n, s) -> Case(Term_sub(m, s), xi, Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var(x), Id) -> Term_var(x) Term_sub(Term_var(x), Cons_usual(y, m, s)) -> m Term_sub(Term_var(x), Cons_usual(y, m, s)) -> Term_sub(Term_var(x), s) Term_sub(Term_var(x), Cons_sum(xi, k, s)) -> Term_sub(Term_var(x), s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(xi, Id) -> Sum_term_var(xi) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_constant(k) Sum_sub(xi, Cons_sum(psi, k, s)) -> Sum_sub(xi, s) Sum_sub(xi, Cons_usual(y, m, s)) -> Sum_sub(xi, s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(x, m, s), t) -> Cons_usual(x, Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(xi, k, s), t) -> Cons_sum(xi, k, Concat(s, t)) Concat(Id, s) -> s S is empty. Rewrite Strategy: FULL ---------------------------------------- (17) SlicingProof (LOWER BOUND(ID)) Sliced the following arguments: Case/1 Sum_sub/0 Sum_term_var/0 Term_var/0 Cons_usual/0 Cons_sum/0 ---------------------------------------- (18) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^2, INF). The TRS R consists of the following rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s S is empty. Rewrite Strategy: FULL ---------------------------------------- (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (20) Obligation: TRS: Rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum ---------------------------------------- (21) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: Term_sub, Sum_sub, Concat They will be analysed ascendingly in the following order: Sum_sub < Term_sub Term_sub = Concat ---------------------------------------- (22) Obligation: TRS: Rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum Generator Equations: gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x)) gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x)) The following defined symbols remain to be analysed: Sum_sub, Term_sub, Concat They will be analysed ascendingly in the following order: Sum_sub < Term_sub Term_sub = Concat ---------------------------------------- (23) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0) Induction Base: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1) Sum_term_var Induction Step: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(+(n8_0, 1))) ->_R^Omega(1) Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) ->_IH Sum_term_var 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: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum Generator Equations: gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x)) gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x)) The following defined symbols remain to be analysed: Sum_sub, Term_sub, Concat They will be analysed ascendingly in the following order: Sum_sub < Term_sub Term_sub = Concat ---------------------------------------- (26) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (27) BOUNDS(n^1, INF) ---------------------------------------- (28) Obligation: TRS: Rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum Lemmas: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0) Generator Equations: gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x)) gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x)) The following defined symbols remain to be analysed: Concat, Term_sub They will be analysed ascendingly in the following order: Term_sub = Concat ---------------------------------------- (29) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0) Induction Base: Concat(gen_Id:Cons_usual:Cons_sum6_0(0), gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1) gen_Id:Cons_usual:Cons_sum6_0(0) Induction Step: Concat(gen_Id:Cons_usual:Cons_sum6_0(+(n370_0, 1)), gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1) Cons_usual(Term_sub(Term_var, gen_Id:Cons_usual:Cons_sum6_0(0)), Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0))) ->_R^Omega(1) Cons_usual(Term_var, Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0))) ->_IH Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(c371_0)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (30) Obligation: TRS: Rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum Lemmas: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0) Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0) Generator Equations: gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x)) gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x)) The following defined symbols remain to be analysed: Term_sub They will be analysed ascendingly in the following order: Term_sub = Concat ---------------------------------------- (31) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) -> gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), rt in Omega(1 + n183948_0) Induction Base: Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(0)) ->_R^Omega(1) Term_var Induction Step: Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(+(n183948_0, 1))) ->_R^Omega(1) Term_sub(Term_var, gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) ->_IH gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (32) Obligation: TRS: Rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum Lemmas: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0) Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0) Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) -> gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), rt in Omega(1 + n183948_0) Generator Equations: gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x)) gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x)) The following defined symbols remain to be analysed: Concat They will be analysed ascendingly in the following order: Term_sub = Concat ---------------------------------------- (33) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: Concat(gen_Id:Cons_usual:Cons_sum6_0(n390037_0), gen_Id:Cons_usual:Cons_sum6_0(b)) -> gen_Id:Cons_usual:Cons_sum6_0(+(n390037_0, b)), rt in Omega(1 + b*n390037_0 + n390037_0) Induction Base: Concat(gen_Id:Cons_usual:Cons_sum6_0(0), gen_Id:Cons_usual:Cons_sum6_0(b)) ->_R^Omega(1) gen_Id:Cons_usual:Cons_sum6_0(b) Induction Step: Concat(gen_Id:Cons_usual:Cons_sum6_0(+(n390037_0, 1)), gen_Id:Cons_usual:Cons_sum6_0(b)) ->_R^Omega(1) Cons_usual(Term_sub(Term_var, gen_Id:Cons_usual:Cons_sum6_0(b)), Concat(gen_Id:Cons_usual:Cons_sum6_0(n390037_0), gen_Id:Cons_usual:Cons_sum6_0(b))) ->_L^Omega(1 + b) Cons_usual(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), Concat(gen_Id:Cons_usual:Cons_sum6_0(n390037_0), gen_Id:Cons_usual:Cons_sum6_0(b))) ->_IH Cons_usual(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(+(b, c390038_0))) We have rt in Omega(n^2) and sz in O(n). Thus, we have irc_R in Omega(n^2). ---------------------------------------- (34) Obligation: Proved the lower bound n^2 for the following obligation: TRS: Rules: Term_sub(Case(m, n), s) -> Frozen(m, Sum_sub(s), n, s) Frozen(m, Sum_constant(Left), n, s) -> Term_sub(m, s) Frozen(m, Sum_constant(Right), n, s) -> Term_sub(n, s) Frozen(m, Sum_term_var, n, s) -> Case(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_app(m, n), s) -> Term_app(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_pair(m, n), s) -> Term_pair(Term_sub(m, s), Term_sub(n, s)) Term_sub(Term_inl(m), s) -> Term_inl(Term_sub(m, s)) Term_sub(Term_inr(m), s) -> Term_inr(Term_sub(m, s)) Term_sub(Term_var, Id) -> Term_var Term_sub(Term_var, Cons_usual(m, s)) -> m Term_sub(Term_var, Cons_usual(m, s)) -> Term_sub(Term_var, s) Term_sub(Term_var, Cons_sum(k, s)) -> Term_sub(Term_var, s) Term_sub(Term_sub(m, s), t) -> Term_sub(m, Concat(s, t)) Sum_sub(Id) -> Sum_term_var Sum_sub(Cons_sum(k, s)) -> Sum_constant(k) Sum_sub(Cons_sum(k, s)) -> Sum_sub(s) Sum_sub(Cons_usual(m, s)) -> Sum_sub(s) Concat(Concat(s, t), u) -> Concat(s, Concat(t, u)) Concat(Cons_usual(m, s), t) -> Cons_usual(Term_sub(m, t), Concat(s, t)) Concat(Cons_sum(k, s), t) -> Cons_sum(k, Concat(s, t)) Concat(Id, s) -> s Types: Term_sub :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Case :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Frozen :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Sum_constant:Sum_term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Sum_sub :: Id:Cons_usual:Cons_sum -> Sum_constant:Sum_term_var Sum_constant :: Left:Right -> Sum_constant:Sum_term_var Left :: Left:Right Right :: Left:Right Sum_term_var :: Sum_constant:Sum_term_var Term_app :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_pair :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inl :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_inr :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Term_var :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var Id :: Id:Cons_usual:Cons_sum Cons_usual :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Cons_sum :: Left:Right -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum Concat :: Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum -> Id:Cons_usual:Cons_sum hole_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var1_0 :: Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var hole_Id:Cons_usual:Cons_sum2_0 :: Id:Cons_usual:Cons_sum hole_Sum_constant:Sum_term_var3_0 :: Sum_constant:Sum_term_var hole_Left:Right4_0 :: Left:Right gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0 :: Nat -> Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var gen_Id:Cons_usual:Cons_sum6_0 :: Nat -> Id:Cons_usual:Cons_sum Lemmas: Sum_sub(gen_Id:Cons_usual:Cons_sum6_0(n8_0)) -> Sum_term_var, rt in Omega(1 + n8_0) Concat(gen_Id:Cons_usual:Cons_sum6_0(n370_0), gen_Id:Cons_usual:Cons_sum6_0(0)) -> gen_Id:Cons_usual:Cons_sum6_0(n370_0), rt in Omega(1 + n370_0) Term_sub(gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), gen_Id:Cons_usual:Cons_sum6_0(n183948_0)) -> gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0), rt in Omega(1 + n183948_0) Generator Equations: gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(0) <=> Term_var gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(+(x, 1)) <=> Case(Term_var, gen_Case:Term_app:Term_pair:Term_inl:Term_inr:Term_var5_0(x)) gen_Id:Cons_usual:Cons_sum6_0(0) <=> Id gen_Id:Cons_usual:Cons_sum6_0(+(x, 1)) <=> Cons_usual(Term_var, gen_Id:Cons_usual:Cons_sum6_0(x)) The following defined symbols remain to be analysed: Concat They will be analysed ascendingly in the following order: Term_sub = Concat ---------------------------------------- (35) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (36) BOUNDS(n^2, INF)