Nonlinearity Of Davenport-Schinzel Sequences And Of A Generalized Path Compression Scheme
- 25 August 2005
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
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 (n /spl alpha/(n)), where /spl alpha/ (n) is the functional inverse of Ackermann's function, and is thus very slow growing. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes.Keywords
This publication has 5 references indexed in Scilit:
- Dynamic computational geometryPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Efficiency of a Good But Not Linear Set Union AlgorithmJournal of the ACM, 1975
- Efficiency of Equivalence AlgorithmsPublished by Springer Nature ,1972
- A Combinatorial Problem Connected with Differential EquationsAmerican Journal of Mathematics, 1965
- Zum Hilbertschen Aufbau der reellen ZahlenMathematische Annalen, 1928