Enumerating Davenport-Schinzel sequences
Gardy, D. ; Gouyou-Beauchamps, D.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992), p. 387-402 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1992-01-01
@article{ITA_1992__26_5_387_0,
     author = {Gardy, D. and Gouyou-Beauchamps, D.},
     title = {Enumerating Davenport-Schinzel sequences},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {26},
     year = {1992},
     pages = {387-402},
     mrnumber = {1187509},
     zbl = {0769.05007},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_1992__26_5_387_0}
}

Gardy, D.; Gouyou-Beauchamps, D. Enumerating Davenport-Schinzel sequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992) pp. 387-402. http://gdmltest.u-ga.fr/item/ITA_1992__26_5_387_0/

1. P. Agarwal, Intersection and decomposition algorithms for arrangements of curves in the plane. Ph. D., New York University, Courant Institute of Mathematical Sciences, 1989. | MR 2638381

2. P. Agarwal, M. Sharir and P. Shor, Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences. J. Combinat. Theory Ser. A, 52, (2) : 228-274, 1989. | MR 1022320 | Zbl 0697.05003

3. P. Alevizos, J. D. Boissonnat and F. Preparata, An optimal algorithm for the boundary of a cell in a union of rays. Algorithmica, 5, (4) : 573-590, 1990. | MR 1072808 | Zbl 0697.68030

4. R. Cole and M. Sharir, Visibility of a polyhedral surface from a point. Technical Report 266, Comp. Science Dept., Courant Institute of Mathematical Sciences, New York University, December 1986.

5. H. Davenport, A combinatorial problem connected with differential equations II. Acta Arithmetica, XVII : 363-372, 1971. | MR 285401 | Zbl 0216.30204

6. H. Davenport and A. Schinzel, A combinatorial problem connected with differential equations. Amer. J. Math., 87 : 684-694, 1965. | MR 190010 | Zbl 0132.00601

7. P. Flajolet, Analytic models and ambiguity of context-free languages. Theoretical Computer Science, 49, (2) : 283-310, 1987. | MR 909335 | Zbl 0612.68069

8. P. Flajolet and A. Odlyzko, Singularity analysis of generating fonctions. SIAM Journal on Discrete Mathematics, 3, (2) : 216-240, 1990. | MR 1039294 | Zbl 0712.05004

9. D. Gouyou-Beauchamps and B. Vauquelin, Deux propriétés combinatoires des nombres of Schröder. Informatique Théorique et Applications, 22, (3) : 361-388, 1988. | Numdam | MR 963597 | Zbl 0669.05002

10. S. Hart and M. Sharir, Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica, 6 : 151-177, 1986. | MR 875839 | Zbl 0636.05003

11. K. Kedem and M. Sharir, An efficient algorithm for planning collision-free translational motion of a convex polygonal object in 2-dimensional space amidst polygonal obstacles. In ACM Symp. on Computational Geometry, pp. 75-8, 1985.

12. P. Komjáth, A simplified construction of nonlinear Davenport-Schinzel sequences. J. Combin. Theory Ser. A, 49, (2) : 262-267, 1988. | MR 964387 | Zbl 0673.05001

13. D. Leven and M. Sharir, On the number of critical free contacts of a convex polygonal object moving in 2-dimensional polygonal space. Discrete Comp. Geom., 2 : 255-270, 1987. | MR 892172 | Zbl 0616.52009

14. J. Pach and M. Sharir, The upper envelope of a piecewise linear function and the boundary of a region enclosed by convex plates: Combinatorial Analysis. Discrete Comp. Geom., 4, (4) : 291-309, 1989. | MR 996764 | Zbl 0734.05054

15. R. Pollack, M. Sharir and S. Sifrony, Separating two simple polygons by a sequence of translations. Discrete Comp. Geom., 3 : 123-136, 1988. | MR 920698 | Zbl 0646.68052

16. M. Sharir, Almost linear upper bounds on the length of general Davenport-Schinzel sequences. Combinatorica, 7, (1) : 131-143, 1987. | MR 905160 | Zbl 0636.05004

17. M. Sharir, Davenport-Schinzel sequences and their geometric applications, chapter Theoretical Foundations of Computer Graphics and CAD, pp. 253-278. Springer-Verlag, NATO ASI Series, Vol. F-40, R.A. Earnshaw edition, 1988. | MR 944720

18. M. Sharir, R. Cole, K. Kedem, D. Leven, R. Pollack and S. Sifrony, Geometric applications of Davenport-Schinzel sequences. In 27th Symposium on Foundations of Computer Science, pp.77-86, Toronto (Canada), 1986.

19. M. Soria, Méthodes d'analyse pour les constructions combinatoires et les algorithmes. Thèse d'État, L.R.I, Université Paris-Sud (Orsay), Juillet 1990.

20. E. Szemerédi, On a problem by Davenport and Schinzel. Acta Arithmetica XXV: 213-224, 1974. | MR 335463 | Zbl 0291.05003

21. A. Wiernik, Planar realizations of nonlinear Davenport-Schinzel sequences by segments. In 27th Symposium on Foundations of Computer Science, pp.97-106, Toronto (Canada), 1986.