Long finite sequences
From MaRDI portal
Let \(n(k)\) be the length of the longest finite sequence \((x_m)\) in \(k\) letters with the property that no consecutive block \(x_i,\dots,x_{2i}\) is a subsequence of any later block \(x_j,\dots,x_{2j}\). It is shown that \(n(1)=3,\;n(2)=11,\) and a lower bound is given for \(n(3)\) in terms of the Ackermann hierarchy, so that \(n(3)\) may be considered as a description of an incomprehensibly large integer. Asymptotic upper and lower bounds for \(n(k)\) are established, too.
Recommendations
Cites work
- A classification of the ordinal recursive functions
- Elementary descent recursion and proof theory
- Hierarchies of number-theoretic functions I, II: A correction
- Hierarchies of number-theoretic functions. I
- scientific article; zbMATH DE number 3857078 (Why is no real title available?)
- scientific article; zbMATH DE number 4033746 (Why is no real title available?)
- scientific article; zbMATH DE number 3627183 (Why is no real title available?)
- scientific article; zbMATH DE number 3198033 (Why is no real title available?)
- Nested recursion
- Ordering by Divisibility in Abstract Algebras
- Ordinal numbers and the Hilbert basis theorem
- Ordinal recursion, and a refinement of the extended Grzegorczyk hierarchy
- The varieties of arboreal experience
Cited in
(12)- scientific article; zbMATH DE number 1301820 (Why is no real title available?)
- Extended skolem sequences
- A fast-growing sequence inspired by \(\mathrm{TREE}(k)\)
- Zeno, Hercules, and the Hydra: safety metric temporal logic is Ackermann-complete
- Finite State Incompressible Infinite Sequences
- Weakly self-avoiding words and a construction of Friedman
- Laver's results and low-dimensional topology
- Functorial Fast-Growing Hierarchies
- Well partial orders
- Busy agents on a line
- Tight length theorems for multiset extensions of Higman's lemma
- Nondecreasing subsequences of t-sequences
This page was built for publication: Long finite sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5940305)
