BibTex RIS Kaynak Göster

Approximate counting with m counters: A probabilistic analysis

Yıl 2015, , 191 - 209, 14.09.2015

Guy Louchard Helmut Prodinger

https://doi.org/10.13069/jacodesmath.36015

Öz

Motivated by a recent paper by Cicho\'n and Macyna [1], who introduced $m$ counters (instead of just one) in the approximate counting scheme first analysed by Flajolet [2], we analyse the moments of the sum of the $m$ counters, using techniques that proved to be successful already in several other contexts [11].

Anahtar Kelimeler

Approximate counting Moments Constant and fluctuating components Complex analysis Product ofFourier series

Kaynakça

  • J. Cichoń and W. Macyna, Approximate counters for flash memory, 17th IEEE International Confer- ence on Embedded and Real-Time Computing Systems and Applications (RTCSA), Toyama, Japan, 20 P. Flajolet, Approximate counting: A detailed analysis, BIT, 25, 113–134, 1985.
  • P. Flajolet and R. Sedgewick, Digital search trees revisited, SIAM J. Comput., 3, 748–767, 1986.
  • M. Fuchs, C. K. Lee, and H. Prodinger, Approximate counting via the Poisson-Laplace-Mellin method, DMTCS, proc AQ, 13–28, 2012.
  • H.-K. Hwang, M. Fuchs and V. Zacharovas, Asymptotic variance of random symmetric digital search trees, Discrete Math. Theor. Comput. Sci., 12, 103–166, 2010.
  • P. Kirschenhofer and H. Prodinger, Approximate counting: An alternative approach, RAIRO Theor. Inform. Appl., 25, 43–48, 1991.
  • D. E. Knuth, The art of computer programming, volume 3: Sorting and searching, Addison-Wesley, 1973, (Second edition, 1998).
  • M. Loève, Probability theory, 3rd ed, D. Van Nostrand, 1963.
  • G. Louchard, Exact and asymptotic distributions in digital and binary search trees, RAIRO Theor. Inform. Appl., 21(4), 479–496, 1987.
  • G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Technical report, 2005. Long version: http://www.ulb.ac.be/di/mcs/louchard/moml.ps.
  • G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica, 46, 431–467, 2006.
  • G. Louchard and H. Prodinger, Generalized approximate counting revisited, Theoret. Comput. Sci., 391, 109–125, 2008.
  • H. Prodinger, Hypothetic analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet, Theoret. Comput. Sci., 100, 243–251, 1992.
  • H. Prodinger, Approximate counting via Euler transform, Mathematica Slovaka, 44, 569–574, 1994.
  • H. Prodinger, Periodic oscillations in the analysis of algorithms and their cancellations, J. Iran. Stat. Soc., 3, 251–270, 2004.
  • H. Prodinger, Approximate counting with m counters: a detailed analysis, Theoret. Comput. Sci., 439, 58–68, 2012.

Yıl 2015, , 191 - 209, 14.09.2015

Guy Louchard Helmut Prodinger

https://doi.org/10.13069/jacodesmath.36015

Öz

Kaynakça

  • J. Cichoń and W. Macyna, Approximate counters for flash memory, 17th IEEE International Confer- ence on Embedded and Real-Time Computing Systems and Applications (RTCSA), Toyama, Japan, 20 P. Flajolet, Approximate counting: A detailed analysis, BIT, 25, 113–134, 1985.
  • P. Flajolet and R. Sedgewick, Digital search trees revisited, SIAM J. Comput., 3, 748–767, 1986.
  • M. Fuchs, C. K. Lee, and H. Prodinger, Approximate counting via the Poisson-Laplace-Mellin method, DMTCS, proc AQ, 13–28, 2012.
  • H.-K. Hwang, M. Fuchs and V. Zacharovas, Asymptotic variance of random symmetric digital search trees, Discrete Math. Theor. Comput. Sci., 12, 103–166, 2010.
  • P. Kirschenhofer and H. Prodinger, Approximate counting: An alternative approach, RAIRO Theor. Inform. Appl., 25, 43–48, 1991.
  • D. E. Knuth, The art of computer programming, volume 3: Sorting and searching, Addison-Wesley, 1973, (Second edition, 1998).
  • M. Loève, Probability theory, 3rd ed, D. Van Nostrand, 1963.
  • G. Louchard, Exact and asymptotic distributions in digital and binary search trees, RAIRO Theor. Inform. Appl., 21(4), 479–496, 1987.
  • G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Technical report, 2005. Long version: http://www.ulb.ac.be/di/mcs/louchard/moml.ps.
  • G. Louchard and H. Prodinger, Asymptotics of the moments of extreme-value related distribution functions, Algorithmica, 46, 431–467, 2006.
  • G. Louchard and H. Prodinger, Generalized approximate counting revisited, Theoret. Comput. Sci., 391, 109–125, 2008.
  • H. Prodinger, Hypothetic analyses: Approximate counting in the style of Knuth, path length in the style of Flajolet, Theoret. Comput. Sci., 100, 243–251, 1992.
  • H. Prodinger, Approximate counting via Euler transform, Mathematica Slovaka, 44, 569–574, 1994.
  • H. Prodinger, Periodic oscillations in the analysis of algorithms and their cancellations, J. Iran. Stat. Soc., 3, 251–270, 2004.
  • H. Prodinger, Approximate counting with m counters: a detailed analysis, Theoret. Comput. Sci., 439, 58–68, 2012.
Toplam 15 adet kaynakça vardır.

Ayrıntılar

Birincil Dil İngilizce
Bölüm Makaleler
Yazarlar

Guy Louchard Bu kişi benim

Helmut Prodinger Bu kişi benim

Yayımlanma Tarihi 14 Eylül 2015
Yayımlandığı Sayı Yıl 2015

Kaynak Göster

APA Louchard, G., & Prodinger, H. (2015). Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications, 2(3), 191-209. https://doi.org/10.13069/jacodesmath.36015
AMA Louchard G, Prodinger H. Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications. Eylül 2015;2(3):191-209. doi:10.13069/jacodesmath.36015
Chicago Louchard, Guy, ve Helmut Prodinger. “Approximate Counting With M Counters: A Probabilistic Analysis”. Journal of Algebra Combinatorics Discrete Structures and Applications 2, sy. 3 (Eylül 2015): 191-209. https://doi.org/10.13069/jacodesmath.36015.
EndNote Louchard G, Prodinger H (01 Eylül 2015) Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications 2 3 191–209.
IEEE G. Louchard ve H. Prodinger, “Approximate counting with m counters: A probabilistic analysis”, Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 3, ss. 191–209, 2015, doi: 10.13069/jacodesmath.36015.
ISNAD Louchard, Guy - Prodinger, Helmut. “Approximate Counting With M Counters: A Probabilistic Analysis”. Journal of Algebra Combinatorics Discrete Structures and Applications 2/3 (Eylül 2015), 191-209. https://doi.org/10.13069/jacodesmath.36015.
JAMA Louchard G, Prodinger H. Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2:191–209.
MLA Louchard, Guy ve Helmut Prodinger. “Approximate Counting With M Counters: A Probabilistic Analysis”. Journal of Algebra Combinatorics Discrete Structures and Applications, c. 2, sy. 3, 2015, ss. 191-09, doi:10.13069/jacodesmath.36015.
Vancouver Louchard G, Prodinger H. Approximate counting with m counters: A probabilistic analysis. Journal of Algebra Combinatorics Discrete Structures and Applications. 2015;2(3):191-209.