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