Document Open Access Logo

Convergence of the Number of Period Sets in Strings

Authors Eric Rivals , Michelle Sweering , Pengfei Wang

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.100.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Eric Rivals
  • LIRMM, Université Montpellier, CNRS, France
Michelle Sweering
  • CWI, Amsterdam, The Netherlands
Pengfei Wang
  • LIRMM, Université Montpellier, CNRS, France

Funding

  • Rivals, Eric: European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 956229.
  • Sweering, Michelle: The Netherlands Organisation for Scientific Research (NWO) through Gravitation-grant NETWORKS-024.002.003.
  • Wang, Pengfei: European Union's Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agreement No 956229.

Cite As Get BibTex

Eric Rivals, Michelle Sweering, and Pengfei Wang. Convergence of the Number of Period Sets in Strings. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 100:1-100:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.ICALP.2023.100

Abstract

Consider words of length n. The set of all periods of a word of length n is a subset of {0,1,2,…,n-1}. However, any subset of {0,1,2,…,n-1} is not necessarily a valid set of periods. In a seminal paper in 1981, Guibas and Odlyzko proposed to encode the set of periods of a word into an n long binary string, called an autocorrelation, where a one at position i denotes the period i. They considered the question of recognizing a valid period set, and also studied the number of valid period sets for strings of length n, denoted κ_n. They conjectured that ln(κ_n) asymptotically converges to a constant times ln²(n). Although improved lower bounds for ln(κ_n)/ln²(n) were proposed in 2001, the question of a tight upper bound has remained open since Guibas and Odlyzko’s paper. Here, we exhibit an upper bound for this fraction, which implies its convergence and closes this longstanding conjecture. Moreover, we extend our result to find similar bounds for the number of correlations: a generalization of autocorrelations which encodes the overlaps between two strings.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Discrete mathematics
Keywords
  • Autocorrelation
  • period
  • border
  • combinatorics
  • correlation
  • periodicity
  • upper bound
  • asymptotic convergence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Dragana Bajic and Tatjana Loncar-Turukalo. A simple suboptimal construction of cross-bifix-free codes. Cryptography and Communications, 6(6):27-37, 2014. URL: https://doi.org/10.1007/s12095-013-0088-8.
  2. Stefano Bilotta. Variable-length non-overlapping codes. IEEE Transactions on Information Theory, 63(10):6530-6537, 2017. URL: https://doi.org/10.1109/TIT.2017.2742506.
  3. Stefano Bilotta, Elisa Pergola, and Renzo Pinzani. A new approach to cross-bifix-free sets. IEEE Transactions on Information Theory, 58(6):4058-4063, 2012. URL: https://doi.org/10.1109/TIT.2012.2189479.
  4. Francine Blanchet-Sadri and S. Duncan. Partial words and the critical factorization theorem. Journal of Combinatorial Theory, Series. A, 109(2):221-245, 2005. URL: https://doi.org/10.1016/j.jcta.2004.09.002.
  5. Francine Blanchet-Sadri, Justin Fowler, Joshua D. Gafni, and Kevin H. Wilson. Combinatorics on partial word correlations. Journal of Combinatorial Theory, Series. A, 117(6):607-624, 2010. URL: https://doi.org/10.1016/j.jcta.2010.03.001.
  6. Francine Blanchet-Sadri, Joshua D. Gafni, and Kevin H. Wilson. Correlations of partial words. In Wolfgang Thomas and Pascal Weil, editors, STACS 2007, 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007, Proceedings, volume 4393 of Lecture Notes in Computer Science, pages 97-108. Springer, 2007. URL: https://doi.org/10.1007/978-3-540-70918-3_9.
  7. Nathan J. Fine and Herbert S. Wilf. Uniqueness theorems for periodic functions. Proceedings of the American Mathematical Society, 16(1):109-114, 1965. URL: https://doi.org/10.1090/S0002-9939-1965-0174934-9.
  8. Daniel Gabric. Mutual borders and overlaps. IEEE Transactions on Information Theory, 68(10):6888-6893, 2022. URL: https://doi.org/10.1109/TIT.2022.3167935.
  9. Daniel Gabric, Narad Rampersad, and Jeffrey Shallit. An inequality for the number of periods in a word. International Journal of Foundations of Computer Science, 32(05):597-614, June 2021. URL: https://doi.org/10.1142/s0129054121410094.
  10. Leonidas J. Guibas and Andrew M. Odlyzko. Periods in strings. Journal of Combinatorial Theory, Series. A, 30:19-42, 1981. URL: https://doi.org/10.1016/0097-3165(81)90038-8.
  11. Leonidas J. Guibas and Andrew M. Odlyzko. String overlaps, pattern matching, and nontransitive games. Journal of Combinatorial Theory, Series A, 30(2):183-208, 1981. URL: https://doi.org/10.1016/0097-3165(81)90005-4.
  12. Vesa Halava, Tero Harju, and Lucian Ilie. Periods and binary words. Journal of Combinatorial Theory, Series A, 89(2):298-303, 2000. URL: https://doi.org/10.1006/jcta.1999.3014.
  13. Stepan Holub and Jeffrey O. Shallit. Periods and borders of random words. In Nicolas Ollinger and Heribert Vollmer, editors, 33rd Symposium on Theoretical Aspects of Computer Science, STACS 2016, February 17-20, 2016, Orléans, France, volume 47 of LIPIcs, pages 44:1-44:10. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.STACS.2016.44.
  14. M. Lothaire, editor. Combinatorics on Words. Cambridge University Press, second edition, 1997. Google Scholar
  15. Ora E. Percus and Paula A. Whitlock. Theory and Application of Marsaglia’s Monkey Test for Pseudorandom Number Generators. ACM Transactions on Modeling and Computer Simulation, 5(2):87-100, April 1995. URL: https://doi.org/10.1145/210330.210331.
  16. Sven Rahmann and Eric Rivals. On the distribution of the number of missing words in random texts. Combinatorics, Probability and Computing, 12(01), January 2003. URL: https://doi.org/10.1017/s0963548302005473.
  17. Eric Rivals and Sven Rahmann. Combinatorics of Periods in Strings. In F. Orejas, P. Spirakis, and J. van Leuween, editors, ICALP 2001, Proc. of the 28th International Colloquium on Automata, Languages and Programming, (ICALP), Crete, Greece, July 8-12, 2001, volume 2076 of Lecture Notes in Computer Science, pages 615-626. Springer Verlag, 2001. URL: https://doi.org/10.1007/3-540-48224-5_51.
  18. Eric Rivals and Sven Rahmann. Combinatorics of periods in strings. Journal of Combinatorial Theory, Series A, 104(1):95-113, 2003. URL: https://doi.org/10.1016/s0097-3165(03)00123-7.
  19. Stéphane Robin, François Rodolphe, and Sophie Schbath. DNA, Words and Models. Cambrigde University Press, 2005. Google Scholar
  20. Neil J. A. Sloane. The on-line encyclopedia of integer sequences. Published electronically at https://oeis.org, 2022.
  21. William F. Smyth. Computating Pattern in Strings. Pearson - Addison Wesley, 2003. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact