A functional equation often arising in the analysis of algorithms (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A functional equation often arising in the analysis of algorithms (extended abstract)

Full text

Pdf (819 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing table of contents

Montreal, Quebec, Canada

Pages: 780 - 789

Year of Publication: 1994

ISBN:0-89791-663-8

Authors

Philippe Jacquet	INRIA, Rocquencourt, 78153 Le Chesnay Cedex, France
Wojciech Szpankowski	Department of Computer Science, Purdue University, W. Lafayette, IN

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 13, Citation Count: 0

Additional Information:

references index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/195058.195456 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Aldous and P. Shields, A Diffusion Limit for a Class of Random-Growing Binary Trees, Probab. Th. Rel. Fields, 79, 509-542 (1988).
	2	Amihood Amir , Gary Benson, Two-dimensional periodicity and its applications, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.440-452, September 1992, Orlando, Florida, United States
	3	P. Billingsley, Convergence of Probability Measures, John Wiley & Sons, New York 1968.
	4	Dany Breslauer , Zvi Galil, An optimal O(log n)time parallel string matching algorithm, SIAM Journal on Computing, v.19 n.6, p.1051-1058, Dec. 1990 [doi>10.1137/0219072]
	5	Thomas M. Cover , Joy A. Thomas, Elements of information theory, Wiley-Interscience, New York, NY, 1991
	6	Philippe Flajolet , Robert Sedgewick, Digital search trees revisited, SIAM Journal on Computing, v.15 n.3, p.748-767, August 1986 [doi>10.1137/0215054]
	7	P. Flajolet and B. Richmond, Generalized Digital Trees and Their Difference-Differential Equations, Random Structures # Algorithms, 3, 305- 320 (1992).
	8	Z. Galil and K. Park, Truly Alphabet Independent Two-Dimensional Pattern Matching, Proc. 33-rd IEEE Conference on Foundation of Computer Science, Pittsburgh, 1992.
	9	E. Gilbert and T. Kadota, The Lempel-Ziv Algorithm and Message Complexity, IEEE Trans. information Theory, 38, 1839-1842 (1992).
	10	P. Jacquet, Contribution de l'Analy#e d'Algorithmes a l'Evaluation de Protocoles de Communication, Th&se Universitg de Paris Sud-Orsay, 1989.
	11	P. Jacquet and M. Rfignier, Normal Limiting Distribution for the Size and the External Path Length of Tries, INRIA TR-827, (1988).
	12	P. Jacquet and W. Szpankowski, Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees, Purdue University, CSD- TR-088, 1993.
	13	P. Kirschenhofer , H. Prodinger , W. Szpankowski, On the variance of the external path length in a symmetric digital trie, Discrete Applied Mathematics, v.25 n.1-2, p.129-143, 1989 [doi>10.1016/0166-218X(89)90050-4]
	14	Peter Kirschenhofer , H. Prodinger , Wojciech Szpankowski, On the balance property of Patricia tries: external path length viewpoint, Theoretical Computer Science, v.68 n.1, p.1-17, Oct. 16, 1989 [doi>10.1016/0304-3975(89)90115-1]
	15	Peter Kirschenhofer , Helmut Prodinger , Wojciech Szpankowski, Digital Search Trees Again Revisited: The Internal Path Length Perspective, SIAM Journal on Computing, v.23 n.3, p.598-616, June 1994 [doi>10.1137/S0097539790189368]
	16	Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
	17	A. Lempel and J. Ziv, On the Complexity of Finite Sequences, IEEE Information Theory 22, 1, 75-81 (1976).
	18	G. Louchard and W. Szpankowski, Average Profile and Limiting Distribution for a Phrase Size in the Lempel-Ziv Parsing Algorithm, INRIA Rapport de Recherche, 1993 (also IEEE Information Theory, to appear).
	19	H. Mahmoud, Evolution of Random Search Trees, John Wiley & Sons, New York (1992).
	20	Bonita Rais , Philippe Jacquet , Wojciech Szpankowski, Limiting distribution for the depth in Patricia tries, SIAM Journal on Discrete Mathematics, v.6 n.2, p.197-213, May 1993 [doi>10.1137/0406016]
	21	L. Sirovich, Techniques of Asymptotic Analysis, Springer-Verlag, New York 1971.
	22	Wojciech Szpankowski, A characterization of digital search trees from the successful search viewpoint, Theoretical Computer Science, v.85 n.1, p.117-134, Aug. 5, 1991 [doi>10.1016/0304-3975(91)90050-C]
	23	Wojciech Szpankowski, A generalized suffix tree and its (un)expected asymptotic behaviors, SIAM Journal on Computing, v.22 n.6, p.1176-1198, Dec. 1993 [doi>10.1137/0222070]
	24	W. Szpankowski, Asymptotic Properties of Data Compression and Suffix Trees, IEEE Trans. Informalion Theory, 39, 1647-1659 (1993).
	25	J. Ziv, Compression, tests for randomness and estimating the statistical model of an individual sequence, Sequences: combinatorics, compression, security, and transmission, Springer-Verlag New York, Inc., New York, NY, 1990
	26	J. Ziv and A. Lempel, A Universal Algorithm for Sequential Data Compression, IEEE Trans. Information Theory, 23, 3, 337-343 (1977).