×

A simplified construction of nonlinear Davenport-Schinzel sequences. (English) Zbl 0673.05001

H. Davenport and 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. S. Hart und 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.
Reviewer: A.Huťa jun

MSC:

05A05 Permutations, words, matrices
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Davenport, H; Schinzel, A, A cominatorial problem connected with differential equations, Amer. J. math., 86, 684-694, (1965) · Zbl 0132.00601
[2] Davenport, H, A combinatorial problem connected with differential equations, II, Acta arith., 17, 363-372, (1971) · Zbl 0216.30204
[3] Hart, S; Sharir, M, Nonlinearity of Davenport-schinzel sequences and of generalized path compression schemes, Combinatorica, 6, 151-177, (1986) · Zbl 0636.05003
[4] Sharir, M, Almost linear upper bounds on the length of general Davenport-schinzel sequences, Combinatorica, 7, 131-193, (1987) · Zbl 0636.05004
[5] {\scM. Sharir and A. Wiernik}, Planar realizations of nonlinear Davenport-Schinzel sequences by segments, to appear. · Zbl 0636.68043
[6] Szemerédi, E, On a problem of Davenport and schinzel, Acta arith., 25, 213-224, (1974) · Zbl 0291.05003
[7] Tarjan, R.E, Efficiency of a good but not linear set union algorithm, J. assoc. comput. Mach., 22, 215-225, (1975) · Zbl 0307.68029
[8] Tarjan, R.E, Data structures and network algorithms, () · Zbl 0749.90027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.