@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, Volume 26 (1992) no. 5, pp. 387-402. http://archive.numdam.org/item/ITA_1992__26_5_387_0/
1. Intersection and decomposition algorithms for arrangements of curves in the plane. Ph. D., New York University, Courant Institute of Mathematical Sciences, 1989. | MR
,2. 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
, and ,3. An optimal algorithm for the boundary of a cell in a union of rays. Algorithmica, 5, (4) : 573-590, 1990. | MR | Zbl
, and ,4. Visibility of a polyhedral surface from a point. Technical Report 266, Comp. Science Dept., Courant Institute of Mathematical Sciences, New York University, December 1986.
and ,5. A combinatorial problem connected with differential equations II. Acta Arithmetica, XVII : 363-372, 1971. | MR | Zbl
,6. A combinatorial problem connected with differential equations. Amer. J. Math., 87 : 684-694, 1965. | MR | Zbl
and ,7. Analytic models and ambiguity of context-free languages. Theoretical Computer Science, 49, (2) : 283-310, 1987. | MR | Zbl
,8. Singularity analysis of generating fonctions. SIAM Journal on Discrete Mathematics, 3, (2) : 216-240, 1990. | MR | Zbl
and ,9. Deux propriétés combinatoires des nombres of Schröder. Informatique Théorique et Applications, 22, (3) : 361-388, 1988. | Numdam | MR | Zbl
and ,10. Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes. Combinatorica, 6 : 151-177, 1986. | MR | Zbl
and ,11. 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.
and ,12. A simplified construction of nonlinear Davenport-Schinzel sequences. J. Combin. Theory Ser. A, 49, (2) : 262-267, 1988. | MR | Zbl
,13. 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
and ,14. 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
and ,15. Separating two simple polygons by a sequence of translations. Discrete Comp. Geom., 3 : 123-136, 1988. | MR | Zbl
, and ,16. Almost linear upper bounds on the length of general Davenport-Schinzel sequences. Combinatorica, 7, (1) : 131-143, 1987. | MR | Zbl
,17. 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. Geometric applications of Davenport-Schinzel sequences. In 27th Symposium on Foundations of Computer Science, pp.77-86, Toronto (Canada), 1986.
, , , , and ,19. 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. On a problem by Davenport and Schinzel. Acta Arithmetica XXV: 213-224, 1974. | MR | Zbl
,21. Planar realizations of nonlinear Davenport-Schinzel sequences by segments. In 27th Symposium on Foundations of Computer Science, pp.97-106, Toronto (Canada), 1986.
,