Nonlinearity of Davenport - Schinzel Sequences and of Generalized
Path Compression Schemes
Sergiu Hart and Micha Sharir
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
Devenport - Schinzel sequence composed of n symbols is
Θ(nα(n)), where α(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.
-
Proceedings of the 25th Annual Symposium on Foundations of Computer
Science (FOCS) (1984), 313-319
[extended abstract]
-
Combinatorica 6 (1986), 2, 151-177
[full paper]