Document Open Access Logo

All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words

Authors Jarkko Peltomäki , Markus A. Whiteland

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.79.pdf
  • Filesize: 458 kB
  • 10 pages

Document Identifiers

Author Details

Jarkko Peltomäki
  • The Turku Collegium for Science and Medicine TCSM, University of Turku, Finland
  • Turku Centre for Computer Science TUCS, Finland
  • University of Turku, Department of Mathematics and Statistics, Finland
Markus A. Whiteland
  • Max Planck Institute for Software Systems, Saarland Informatics Campus, Saarbrücken, Germany

Cite As Get BibTex

Jarkko Peltomäki and Markus A. Whiteland. All Growth Rates of Abelian Exponents Are Attained by Infinite Binary Words. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 79:1-79:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.MFCS.2020.79

Abstract

We consider repetitions in infinite words by making a novel inquiry to the maximum eventual growth rate of the exponents of abelian powers occurring in an infinite word. Given an increasing, unbounded function f: ℕ → ℝ, we construct an infinite binary word whose abelian exponents have limit superior growth rate f. As a consequence, we obtain that every nonnegative real number is the critical abelian exponent of some infinite binary word.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Combinatorics on words
Keywords
  • abelian equivalence
  • abelian power
  • abelian critical exponent

Metrics

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

References

  1. Martin Aigner. Markov’s Theorem and 100 Years of the Uniqueness Conjecture. Springer, 2013. URL: https://doi.org/10.1007/978-3-319-00888-2.
  2. Valérie Berthé and Michel Rigo, editors. Combinatorics, Words and Symbolic Dynamics. Number 159 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2016. Google Scholar
  3. Valérie Berthé and Michel Rigo, editors. Sequences, Groups, and Number Theory. Trends in Mathematics. Birkhäuser, 2018. URL: https://doi.org/10.1007/978-3-319-69152-7.
  4. Arturo Carpi. On abelian power-free morphisms. Internat. J. Algebra Comput., 3(2):151-167, 1993. URL: https://doi.org/10.1142/S0218196793000123.
  5. Julien Cassaigne and James D. Currie. Words strongly avoiding fractional powers. Eur. J. Combin., 20(8):725-737, 1999. URL: https://doi.org/10.1006/eujc.1999.0329.
  6. James D. Currie and Ali Aberkane. A cyclic binary morphism avoiding Abelian fourth powers. Theoret. Comput. Sci., 410(1):44-52, 2009. URL: https://doi.org/10.1016/j.tcs.2008.09.027.
  7. Thomas W. Cusick and Mary E. Flahive. The Markoff and Lagrange Spectra. Number 30 in Mathematical Surveys and Monographs. American Mathematical Society, Providence, Rhode Island, 1989. Google Scholar
  8. F. M. Dekking. Strongly non-repetitive sequences and progression-free sets. J. Combin. Theory Ser. A, 27(2):181-185, 1979. URL: https://doi.org/10.1016/0097-3165(79)90044-X.
  9. Fabien Durand. Corrigendum and addendum to ‘Linearly recurrent subshifts have a finite number of non-periodic factors’. Ergodic Theory Dynam. Systems, 23(2):663-669, 2003. URL: https://doi.org/10.1017/S0143385702001293.
  10. Paul Erdős. Some unsolved problems. Michigan Math. J., 4(3):291-300, 1957. Google Scholar
  11. Gabriele Fici, Alessio Langiu, Thierry Lecroq, Arnaud Lefebvre, Filippo Mignosi, Jarkko Peltomäki, and Élise Prieur-Gaston. Abelian powers and repetitions in Sturmian words. Theoret. Comput. Sci., 635:16-34, 2016. URL: https://doi.org/10.1016/j.tcs.2016.04.039.
  12. Juhani Karhumäki, Svetlana Puzynina, and Markus A. Whiteland. On abelian subshifts. In Mizuho Hoshi and Shinnosuke Seki, editors, Developments in Language Theory, number 11088 in Lecture Notes in Comput. Sci., pages 453-464. Springer, 2018. URL: https://doi.org/10.1007/978-3-319-98654-8.
  13. Juhani Karhumäki, Aleksi Saarela, and Luca Q. Zamboni. On a generalization of Abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A, 120:2189-2206, 2013. URL: https://doi.org/10.1016/j.jcta.2013.08.008.
  14. Veikko Keränen. Abelian squares are avoidable on 4 letters. In Automata, Languages and Programming, number 623 in Lecture Notes in Comput. Sci., pages 41-52. Springer, 1992. URL: https://doi.org/10.1007/3-540-55719-9.
  15. Tomasz Kociumaka, Jakub Radoszewski, and Bartłomiej Wiśniewski. Subquadratic-time algorithms for abelian stringology problems. In Ilias S. Kotsireas, Siegfried M. Rump, and Chee K. Yap, editors, Mathematical Aspects of Computer and Information Sciences, number 9582 in Lecture Notes in Comput. Sci., pages 320-334. Springer, 2015. URL: https://doi.org/10.1007/978-3-319-32859-1.
  16. Dalia Krieger and Jeffrey Shallit. Every real number greater than 1 is a critical exponent. Theoret. Comput. Sci., 381:177-182, 2007. URL: https://doi.org/10.1016/j.tcs.2007.04.037.
  17. M. Lothaire. Algebraic Combinatorics on Words. Number 90 in Encyclopedia of Mathematics and Its Applications. Cambridge University Press, 2002. Google Scholar
  18. Carlos Gustavo Moreira. Geometric properties of the Markov and Lagrange spectra. Ann. Math., 188(1):145-170, 2018. URL: https://doi.org/10.4007/annals.2018.188.1.3.
  19. Jarkko Peltomäki. Abelian periods of factors of Sturmian words. J. Number Theory, 194(2):251-285, 2020. URL: https://doi.org/10.1016/j.jnt.2020.04.007.
  20. Jarkko Peltomäki and Markus A. Whiteland. Every nonnegative real number is a critical abelian exponent. In Robert Mercaş and Daniel Reidenbach, editors, Combinatorics on Words, number 11682 in Lecture Notes in Comput. Sci., pages 275-285. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-28796-2.
  21. Jarkko Peltomäki and Markus A. Whiteland. Avoiding abelian powers cyclically. CoRR, 2020. Preprint. URL: http://arxiv.org/abs/2006.06307.
  22. Jarkko Peltomäki and Markus A. Whiteland. On k-abelian equivalence and generalized Lagrange spectra. Acta Arith., 194(2):135-154, 2020. URL: https://doi.org/10.4064/aa180927-10-9.
  23. Svetlana Puzynina. Abelian properties of words. In Robert Mercaş and Daniel Reidenbach, editors, Combinatorics on Words, number 11682 in Lecture Notes in Comput. Sci., pages 28-45. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-28796-2.
  24. Svetlana Puzynina and Luca Q. Zamboni. Abelian returns in Sturmian words. J. Combin. Theory Ser. A, 120(2):390-408, 2013. URL: https://doi.org/10.1016/j.jcta.2012.09.002.
  25. Christophe Reutenauer. From Christoffel Words to Markoff Numbers. Oxford University Press, 2019. Google Scholar
  26. Gwenaël Richomme, Kalle Saari, and Luca Q. Zamboni. Abelian complexity of minimal subshifts. J. Lond. Math. Soc., 83(1):79-95, 2011. URL: https://doi.org/10.1112/jlms/jdq063.
  27. Michel Rigo and Pavel Salimov. Another generalization of abelian equivalence: Binomial complexity of infinite words. Theoret. Comput. Sci., 601:47-57, 2015. URL: https://doi.org/10.1016/j.tcs.2015.07.025.
  28. Michel Rigo, Pavel Salimov, and Élise Vandomme. Some properties of abelian return words. J. Integer Seq., 16, 2013. Google Scholar
  29. Alexey V. Samsonov and Arseny M. Shur. On abelian repetition threshold. RAIRO Theor. Inform. Appl., 46(1):147-163, 2012. URL: https://doi.org/10.1051/ita/2011127.
  30. Markus A. Whiteland. On the k-Abelian Equivalence Relation of Finite Words. Ph.d. dissertation, Turku Centre for Computer Science, University of Turku, Turku, Finland, 2019. URL: http://urn.fi/URN:ISBN:978-952-12-3837-6.
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