Document Open Access Logo

Periods and Borders of Random Words

Authors Štepán Holub, Jeffrey Shallit

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.44.pdf
  • Filesize: 0.58 MB
  • 10 pages

Document Identifiers

Author Details

Štepán Holub
Jeffrey Shallit

Cite As Get BibTex

Štepán Holub and Jeffrey Shallit. Periods and Borders of Random Words. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 44:1-44:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.44

Abstract

We investigate the behavior of the periods and border lengths of random words over a fixed alphabet. We show that the asymptotic probability that a random word has a given maximal border length k is a constant, depending only on k and the alphabet size l. We give a recurrence that allows us to determine these constants with any required precision. This also allows us to evaluate the expected period of a random word. For the binary case, the expected period is asymptotically about n-1.641. We also give explicit formulas for the probability that a random word is unbordered or has maximum border length one.

Subject Classification

Keywords
  • random word
  • period
  • word border

Metrics

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

References

  1. A. Alatabbi, A. S. S. Islam, M. S. Rahman, J. Simpson, and W. F. Smyth. Enhanced covers of regular & indeterminate strings using prefix tables. CoRR, abs/1506.06793, 2015. URL: http://arxiv.org/abs/1506.06793.
  2. G. Blom. Overlapping binary sequences (problem 94-20). SIAM Review, 37:619-620, 1995. Google Scholar
  3. A. Ehrenfeucht and D. M. Silberger. Periodicity and unbordered segments of words. Discrete Math., 26:101-109, 1979. Google Scholar
  4. N. J. Fine and H. S. Wilf. Uniqueness theorems for periodic functions. Proc. Amer. Math. Soc., 16:109-114, 1965. Google Scholar
  5. L. Guibas. Periodicities in strings. In A. Apostolico and Z. Galil, editors, Combinatorial Algorithms on Words, volume F12 of NATO ASI, pages 257-269. Springer-Verlag, 1985. Google Scholar
  6. L. J. Guibas and A. M. Odlyzko. Periods in strings. J. Combin. Theory. Ser. A, 30:19-42, 1981. Google Scholar
  7. L. J. Guibas and A. M. Odlyzko. String overlaps, pattern matching, and nontransitive games. J. Combin. Theory. Ser. A, 30:183-208, 1981. Google Scholar
  8. V. Halava, T. Harju, and L. Ilie. Periods and binary words. J. Combin. Theory. Ser. A, 89:298-303, 2000. Google Scholar
  9. H. Harborth. Endliche 0-1-Folgen mit gleichen Teilblöcken. Journal für die reine und angewandte Mathematik, 271:139-154, 1974. Google Scholar
  10. A. Loptev, G. Kucherov, and T. Starikovskaya. On maximal unbordered factors. In F. Cicalese et al., editor, CPM 2015, volume 9133 of Lecture Notes in Computer Science, pages 343-354. Springer-Verlag, 2015. Google Scholar
  11. P. T. Nielsen. A note on bifix-free sequences. IEEE Trans. Inform. Theory, IT-19:704-706, 1973. Google Scholar
  12. E. Rivals and S. Rahmann. Combinatorics of periods in strings. J. Combin. Theory. Ser. A, 104:95-113, 2003. Google Scholar
  13. D. M. Silberger. Borders and roots of a word. Progress in Mathematics, 30:191-199, 1971. Google Scholar
  14. D. M. Silberger. How many unbordered words? Comment. Math. Prace Mat., 22:143-145, 1980. Google Scholar
  15. R. Tijdeman and L. Zamboni. Fine and Wilf words for any periods. Indag. Math., 14:135-147, 2003. Google Scholar
  16. R. Tijdeman and L. Q. Zamboni. Fine and Wilf words for any periods II. Theor. Comput. Sci., 410(30-32):3027-3034, 2009. Google Scholar
  17. Š. Holub. On an algorithm for multiperiodic words. Acta Polytechnica, 53(4):344-346, 2013. 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