Long finite sequences (Q5940305): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 01:47, 30 January 2024
scientific article; zbMATH DE number 1624770
Language | Label | Description | Also known as |
---|---|---|---|
English | Long finite sequences |
scientific article; zbMATH DE number 1624770 |
Statements
Long finite sequences (English)
0 references
7 August 2002
0 references
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.
0 references
longest finite sequences
0 references
Ackermann hierarchy
0 references