Enumerating Davenport-Schinzel sequences
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 26 (1992) no. 5, pp. 387-402. 
@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},
     pages = {387--402},
     publisher = {EDP-Sciences},
     volume = {26},
     number = {5},
     year = {1992},
     mrnumber = {1187509},
     zbl = {0769.05007},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_1992__26_5_387_0/}
}
TY  - JOUR
AU  - Gardy, D.
AU  - Gouyou-Beauchamps, D.
TI  - Enumerating Davenport-Schinzel sequences
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 1992
SP  - 387
EP  - 402
VL  - 26
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_1992__26_5_387_0/
LA  - en
ID  - ITA_1992__26_5_387_0
ER  - 
%0 Journal Article
%A Gardy, D.
%A Gouyou-Beauchamps, D.
%T Enumerating Davenport-Schinzel sequences
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 1992
%P 387-402
%V 26
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_1992__26_5_387_0/
%G en
%F 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) no. 5, pp. 387-402. http://archive.numdam.org/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

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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

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 | Zbl

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

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 | Zbl

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 | Zbl

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 | Zbl

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 | Zbl

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

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

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 | Zbl

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.