/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), ?) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). (0) CpxTRS (1) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] (2) CpxTRS (3) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] (4) typed CpxTrs (5) OrderProof [LOWER BOUND(ID), 0 ms] (6) typed CpxTrs (7) RewriteLemmaProof [LOWER BOUND(ID), 69.0 s] (8) BEST (9) proven lower bound (10) LowerBoundPropagationProof [FINISHED, 0 ms] (11) BOUNDS(n^1, INF) (12) typed CpxTrs (13) RewriteLemmaProof [LOWER BOUND(ID), 1216 ms] (14) typed CpxTrs ---------------------------------------- (0) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0, cons(X, Z)) -> mark(X) a__first(0, Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0, cons(X, Z)) -> a__quote(X) a__first1(0, Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0) -> 01 a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01) -> 0 a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0) -> 0 mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01) -> 01 mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (1) RenamingProof (BOTH BOUNDS(ID, ID)) Renamed function symbols to avoid clashes with predefined symbol. ---------------------------------------- (2) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). The TRS R consists of the following rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0', cons(X, Z)) -> mark(X) a__first(0', Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0', cons(X, Z)) -> a__quote(X) a__first1(0', Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0') -> 01' a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01') -> 0' a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0') -> 0' mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01') -> 01' mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (3) TypeInferenceProof (BOTH BOUNDS(ID, ID)) Infered types. ---------------------------------------- (4) Obligation: Innermost TRS: Rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0', cons(X, Z)) -> mark(X) a__first(0', Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0', cons(X, Z)) -> a__quote(X) a__first1(0', Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0') -> 01' a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01') -> 0' a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0') -> 0' mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01') -> 01' mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) Types: a__sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons mark :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 0' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 01' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons hole_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons1_0 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0 :: Nat -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons ---------------------------------------- (5) OrderProof (LOWER BOUND(ID)) Heuristically decided to analyse the following defined symbols: a__sel, mark, a__from, a__sel1, a__quote, a__first1, a__quote1, a__unquote, a__unquote1, a__fcons They will be analysed ascendingly in the following order: a__sel = mark a__sel = a__from a__sel = a__sel1 a__sel = a__quote a__sel = a__first1 a__sel = a__quote1 a__sel = a__unquote a__sel = a__unquote1 a__sel = a__fcons mark = a__from mark = a__sel1 mark = a__quote mark = a__first1 mark = a__quote1 mark = a__unquote mark = a__unquote1 mark = a__fcons a__from = a__sel1 a__from = a__quote a__from = a__first1 a__from = a__quote1 a__from = a__unquote a__from = a__unquote1 a__from = a__fcons a__sel1 = a__quote a__sel1 = a__first1 a__sel1 = a__quote1 a__sel1 = a__unquote a__sel1 = a__unquote1 a__sel1 = a__fcons a__quote = a__first1 a__quote = a__quote1 a__quote = a__unquote a__quote = a__unquote1 a__quote = a__fcons a__first1 = a__quote1 a__first1 = a__unquote a__first1 = a__unquote1 a__first1 = a__fcons a__quote1 = a__unquote a__quote1 = a__unquote1 a__quote1 = a__fcons a__unquote = a__unquote1 a__unquote = a__fcons a__unquote1 = a__fcons ---------------------------------------- (6) Obligation: Innermost TRS: Rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0', cons(X, Z)) -> mark(X) a__first(0', Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0', cons(X, Z)) -> a__quote(X) a__first1(0', Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0') -> 01' a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01') -> 0' a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0') -> 0' mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01') -> 01' mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) Types: a__sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons mark :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 0' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 01' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons hole_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons1_0 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0 :: Nat -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons Generator Equations: gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(0) <=> 0' gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(x, 1)) <=> s(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(x)) The following defined symbols remain to be analysed: mark, a__sel, a__from, a__sel1, a__quote, a__first1, a__quote1, a__unquote, a__unquote1, a__fcons They will be analysed ascendingly in the following order: a__sel = mark a__sel = a__from a__sel = a__sel1 a__sel = a__quote a__sel = a__first1 a__sel = a__quote1 a__sel = a__unquote a__sel = a__unquote1 a__sel = a__fcons mark = a__from mark = a__sel1 mark = a__quote mark = a__first1 mark = a__quote1 mark = a__unquote mark = a__unquote1 mark = a__fcons a__from = a__sel1 a__from = a__quote a__from = a__first1 a__from = a__quote1 a__from = a__unquote a__from = a__unquote1 a__from = a__fcons a__sel1 = a__quote a__sel1 = a__first1 a__sel1 = a__quote1 a__sel1 = a__unquote a__sel1 = a__unquote1 a__sel1 = a__fcons a__quote = a__first1 a__quote = a__quote1 a__quote = a__unquote a__quote = a__unquote1 a__quote = a__fcons a__first1 = a__quote1 a__first1 = a__unquote a__first1 = a__unquote1 a__first1 = a__fcons a__quote1 = a__unquote a__quote1 = a__unquote1 a__quote1 = a__fcons a__unquote = a__unquote1 a__unquote = a__fcons a__unquote1 = a__fcons ---------------------------------------- (7) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: mark(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0)) -> gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0), rt in Omega(1 + n4_0) Induction Base: mark(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(0)) ->_R^Omega(1) 0' Induction Step: mark(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(n4_0, 1))) ->_R^Omega(1) s(mark(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0))) ->_IH s(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(c5_0)) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (8) Complex Obligation (BEST) ---------------------------------------- (9) Obligation: Proved the lower bound n^1 for the following obligation: Innermost TRS: Rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0', cons(X, Z)) -> mark(X) a__first(0', Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0', cons(X, Z)) -> a__quote(X) a__first1(0', Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0') -> 01' a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01') -> 0' a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0') -> 0' mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01') -> 01' mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) Types: a__sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons mark :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 0' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 01' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons hole_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons1_0 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0 :: Nat -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons Generator Equations: gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(0) <=> 0' gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(x, 1)) <=> s(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(x)) The following defined symbols remain to be analysed: mark, a__sel, a__from, a__sel1, a__quote, a__first1, a__quote1, a__unquote, a__unquote1, a__fcons They will be analysed ascendingly in the following order: a__sel = mark a__sel = a__from a__sel = a__sel1 a__sel = a__quote a__sel = a__first1 a__sel = a__quote1 a__sel = a__unquote a__sel = a__unquote1 a__sel = a__fcons mark = a__from mark = a__sel1 mark = a__quote mark = a__first1 mark = a__quote1 mark = a__unquote mark = a__unquote1 mark = a__fcons a__from = a__sel1 a__from = a__quote a__from = a__first1 a__from = a__quote1 a__from = a__unquote a__from = a__unquote1 a__from = a__fcons a__sel1 = a__quote a__sel1 = a__first1 a__sel1 = a__quote1 a__sel1 = a__unquote a__sel1 = a__unquote1 a__sel1 = a__fcons a__quote = a__first1 a__quote = a__quote1 a__quote = a__unquote a__quote = a__unquote1 a__quote = a__fcons a__first1 = a__quote1 a__first1 = a__unquote a__first1 = a__unquote1 a__first1 = a__fcons a__quote1 = a__unquote a__quote1 = a__unquote1 a__quote1 = a__fcons a__unquote = a__unquote1 a__unquote = a__fcons a__unquote1 = a__fcons ---------------------------------------- (10) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (11) BOUNDS(n^1, INF) ---------------------------------------- (12) Obligation: Innermost TRS: Rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0', cons(X, Z)) -> mark(X) a__first(0', Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0', cons(X, Z)) -> a__quote(X) a__first1(0', Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0') -> 01' a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01') -> 0' a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0') -> 0' mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01') -> 01' mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) Types: a__sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons mark :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 0' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 01' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons hole_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons1_0 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0 :: Nat -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons Lemmas: mark(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0)) -> gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0), rt in Omega(1 + n4_0) Generator Equations: gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(0) <=> 0' gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(x, 1)) <=> s(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(x)) The following defined symbols remain to be analysed: a__sel, a__from, a__sel1, a__quote, a__first1, a__quote1, a__unquote, a__unquote1, a__fcons They will be analysed ascendingly in the following order: a__sel = mark a__sel = a__from a__sel = a__sel1 a__sel = a__quote a__sel = a__first1 a__sel = a__quote1 a__sel = a__unquote a__sel = a__unquote1 a__sel = a__fcons mark = a__from mark = a__sel1 mark = a__quote mark = a__first1 mark = a__quote1 mark = a__unquote mark = a__unquote1 mark = a__fcons a__from = a__sel1 a__from = a__quote a__from = a__first1 a__from = a__quote1 a__from = a__unquote a__from = a__unquote1 a__from = a__fcons a__sel1 = a__quote a__sel1 = a__first1 a__sel1 = a__quote1 a__sel1 = a__unquote a__sel1 = a__unquote1 a__sel1 = a__fcons a__quote = a__first1 a__quote = a__quote1 a__quote = a__unquote a__quote = a__unquote1 a__quote = a__fcons a__first1 = a__quote1 a__first1 = a__unquote a__first1 = a__unquote1 a__first1 = a__fcons a__quote1 = a__unquote a__quote1 = a__unquote1 a__quote1 = a__fcons a__unquote = a__unquote1 a__unquote = a__fcons a__unquote1 = a__fcons ---------------------------------------- (13) RewriteLemmaProof (LOWER BOUND(ID)) Proved the following rewrite lemma: a__quote(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(1, n14758984_0))) -> *3_0, rt in Omega(n14758984_0) Induction Base: a__quote(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(1, 0))) Induction Step: a__quote(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(1, +(n14758984_0, 1)))) ->_R^Omega(1) s1(a__quote(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(1, n14758984_0)))) ->_IH s1(*3_0) We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). ---------------------------------------- (14) Obligation: Innermost TRS: Rules: a__sel(s(X), cons(Y, Z)) -> a__sel(mark(X), mark(Z)) a__sel(0', cons(X, Z)) -> mark(X) a__first(0', Z) -> nil a__first(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z)) a__from(X) -> cons(mark(X), from(s(X))) a__sel1(s(X), cons(Y, Z)) -> a__sel1(mark(X), mark(Z)) a__sel1(0', cons(X, Z)) -> a__quote(X) a__first1(0', Z) -> nil1 a__first1(s(X), cons(Y, Z)) -> cons1(a__quote(Y), a__first1(mark(X), mark(Z))) a__quote(0') -> 01' a__quote1(cons(X, Z)) -> cons1(a__quote(X), a__quote1(Z)) a__quote1(nil) -> nil1 a__quote(s(X)) -> s1(a__quote(X)) a__quote(sel(X, Z)) -> a__sel1(mark(X), mark(Z)) a__quote1(first(X, Z)) -> a__first1(mark(X), mark(Z)) a__unquote(01') -> 0' a__unquote(s1(X)) -> s(a__unquote(mark(X))) a__unquote1(nil1) -> nil a__unquote1(cons1(X, Z)) -> a__fcons(a__unquote(mark(X)), a__unquote1(mark(Z))) a__fcons(X, Z) -> cons(mark(X), Z) mark(sel(X1, X2)) -> a__sel(mark(X1), mark(X2)) mark(first(X1, X2)) -> a__first(mark(X1), mark(X2)) mark(from(X)) -> a__from(mark(X)) mark(sel1(X1, X2)) -> a__sel1(mark(X1), mark(X2)) mark(quote(X)) -> a__quote(X) mark(first1(X1, X2)) -> a__first1(mark(X1), mark(X2)) mark(quote1(X)) -> a__quote1(X) mark(unquote(X)) -> a__unquote(mark(X)) mark(unquote1(X)) -> a__unquote1(mark(X)) mark(fcons(X1, X2)) -> a__fcons(mark(X1), mark(X2)) mark(s(X)) -> s(mark(X)) mark(cons(X1, X2)) -> cons(mark(X1), X2) mark(0') -> 0' mark(nil) -> nil mark(nil1) -> nil1 mark(cons1(X1, X2)) -> cons1(mark(X1), mark(X2)) mark(01') -> 01' mark(s1(X)) -> s1(mark(X)) a__sel(X1, X2) -> sel(X1, X2) a__first(X1, X2) -> first(X1, X2) a__from(X) -> from(X) a__sel1(X1, X2) -> sel1(X1, X2) a__quote(X) -> quote(X) a__first1(X1, X2) -> first1(X1, X2) a__quote1(X) -> quote1(X) a__unquote(X) -> unquote(X) a__unquote1(X) -> unquote1(X) a__fcons(X1, X2) -> fcons(X1, X2) Types: a__sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons mark :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 0' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons from :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons nil1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons cons1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons 01' :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons s1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons a__fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons sel1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons first1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons quote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons unquote1 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons fcons :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons hole_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons1_0 :: s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0 :: Nat -> s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons Lemmas: mark(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0)) -> gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(n4_0), rt in Omega(1 + n4_0) a__quote(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(1, n14758984_0))) -> *3_0, rt in Omega(n14758984_0) Generator Equations: gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(0) <=> 0' gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(+(x, 1)) <=> s(gen_s:cons:0':nil:first:from:nil1:cons1:01':s1:sel:sel1:quote:first1:quote1:unquote:unquote1:fcons2_0(x)) The following defined symbols remain to be analysed: a__first1, a__sel, mark, a__from, a__sel1, a__quote1, a__unquote, a__unquote1, a__fcons They will be analysed ascendingly in the following order: a__sel = mark a__sel = a__from a__sel = a__sel1 a__sel = a__quote a__sel = a__first1 a__sel = a__quote1 a__sel = a__unquote a__sel = a__unquote1 a__sel = a__fcons mark = a__from mark = a__sel1 mark = a__quote mark = a__first1 mark = a__quote1 mark = a__unquote mark = a__unquote1 mark = a__fcons a__from = a__sel1 a__from = a__quote a__from = a__first1 a__from = a__quote1 a__from = a__unquote a__from = a__unquote1 a__from = a__fcons a__sel1 = a__quote a__sel1 = a__first1 a__sel1 = a__quote1 a__sel1 = a__unquote a__sel1 = a__unquote1 a__sel1 = a__fcons a__quote = a__first1 a__quote = a__quote1 a__quote = a__unquote a__quote = a__unquote1 a__quote = a__fcons a__first1 = a__quote1 a__first1 = a__unquote a__first1 = a__unquote1 a__first1 = a__fcons a__quote1 = a__unquote a__quote1 = a__unquote1 a__quote1 = a__fcons a__unquote = a__unquote1 a__unquote = a__fcons a__unquote1 = a__fcons