Nonlinearity of davenport—Schinzel sequences and of generalized path compression schemes |
| |
Authors: | Sergiu Hart Micha Sharir |
| |
Institution: | (1) School of Mathematical Sciences, Tel Aviv University, 69978 Tel Aviv, Israel |
| |
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
ofn 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.
Work on this paper by the second author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation. |
| |
Keywords: | 05 A 99 05 C 35 68 B 15 |
本文献已被 SpringerLink 等数据库收录! |
|