Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. (English) Zbl 0636.05003

Davenport-Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport-Schinzel sequence composed of \(n\) symbols is \(\theta(n \alpha(n))\), where \(\alpha(n)\) is the functional inverse of Ackermann’s function, and is thus very slowly increasing to infinity. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes.


05A05 Permutations, words, matrices
05C05 Trees
11B83 Special sequences and polynomials
11Y55 Calculation of integer sequences
Full Text: DOI


[1] W. Ackermann, Zum Hilbertschen Aufbau der reellen Zahlen,Math. Ann. 99 (1928), 113–133. · JFM 54.0056.06 · doi:10.1007/BF01459088
[2] M. Atallah, Dynamic Computational Geometry,Proc. 24th Symp. on Foundations of Computer Science, 1983, 92–99.
[3] H. Davenport, A Combinatorial Problem Connected with Differential Equations, II,Acta Arithmetica 17 (1971), 363–372. · Zbl 0216.30204
[4] H. Davenport andA. Schinzel, A Combinatorial Problem Connected with Differential Equations,Amer. J. Math. 87 (1965), 684–694. · Zbl 0132.00601 · doi:10.2307/2373068
[5] M. J. Fisher, Efficiency of Equivalence Algorithms,in: Complexity of Computer Computations, (R. E. Miller and J. W. Thatcher, Eds.), Plenum Press, New York, 1972, 153–168.
[6] R. L. Graham, B. L. Rothschild andJ. H. Spencer,Ramsey Theory, Wiley-Interscience, New York, 1980.
[7] G. Kreisel, On the Interpretation of Nonfinitistic Proofs, II,J. Symbolic Logic 17 (1952), 43–58. · Zbl 0046.00701 · doi:10.2307/2267457
[8] J. Ketonen andR. M. Solovay, Rapidly Growing Ramsey Functions,Ann. of Math. 113 (1981), 267–314. · Zbl 0494.03027 · doi:10.2307/2006985
[9] R. Livne andM. Sharir, On Minima of Functions, Intersection Patterns of Curves, and Davenport–Schinzel Sequences,Proc. 26th IEEE Symposium on Foundations of Computer Science, Portland, Ore., October 1985, 312–320.
[10] J. Paris andL. Harrington, A Mathematical Incompleteness in Peano Arithmetic,in: Handbook of Mathematical Logic, (ed: J. Barwise), North-Holland 1977, 1133–1142.
[11] H. Rogers,Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967. · Zbl 0183.01401
[12] D. P. Roselle andR. G. Stanton, Some Properties of Davenport–Schinzel Sequences,Acta Arithmetica 17 (1971), 355–362. · Zbl 0215.33203
[13] M. Sharir, Almost Linear Upper Bounds on the Length of General Davenport–Schinzel Sequences,Combinatorica 7 (1987),to appear. · Zbl 0636.05004
[14] M. Sharir, On the Two-dimensional Davenport–Schinzel Problem,Techn. Rep. 193, Comp. Sci. Dept., Courant Institute, 1985.
[15] E. Szemerédi, On a Problem by Davenport and Schinzel,Acta Arithmetica 25 (1974), 213–224.
[16] R. E. Tarjan, Efficiency of a Good but not Linear Set-union Algorithm,J. Assoc. Computing Machinery 22 (1975), 215–225. · Zbl 0307.68029
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.