A simplified construction of nonlinear Davenport-Schinzel sequences (Q1120575)

\textit{H. Davenport} and \textit{A. Schinzel} [Am. J. Math. 57, 684-694 (1965; Zbl 0132.006); Acta Arith. 17, 363-372 (1971; Zbl 0216.302)] haben ein Problem aufgestellt zur Beurteilung der Länge von aus n Buchstaben zusammengesetzten Wörtern mit nicht unmittelbaren Wiederholungen derselben Buchstaben oder Unterwörtern vom Typ abab... der Länge \(s+2\). Die maximale Länge soll mit \(\lambda_ s(n)\) bezeichnet werden. Ein langdauerndes Problem war zu bestimmen, ob \(\lambda_ 3(n)\) linear ist. \textit{S. Hart} und \textit{M. Sharir} [Combinatorica 6, 151-177 (1986; Zbl 0636.05003)] haben das Problem gelöst. Der Zweck dieses Artikels ist, eine direkte Konstruktion für die untere Grenze auszuarbeiten. Es werden zunächst die Begriffe der regulären und singulären Blöcke erörtert, die in den Wörtern vorkommen. Es folgt eine Aussage S(k,m) über eine Zahl \(F_ k(m)\), welche in 7 Punkten die Eigenschaften eines in reguläre und singuläre Blöcke zerlegten Wortes zusammenfaßt. Im Schlußteil des Artikels wird das Problem der unteren Grenzen mittels der Funktionalinverse \(\alpha (n)=\min \{k:\quad n\leq A_ k(k)\}\) der Ackermann-Funktion \(A_ k(m)\) mit den Beziehungen \(A_ 1(m)=2^{m+1},\) \(A_{k+1}(1)=A_ k(2),\) \(A_{k+1}(m+1)=A_ k(A_{k+1}(m)),\) behandelt.