Document Open Access Logo

On Extended Boundary Sequences of Morphic and Sturmian Words

Authors Michel Rigo , Manon Stipulanti , Markus A. Whiteland

PDF

File

Thumbnail PDF
PDF
LIPIcs.MFCS.2022.79.pdf
  • Filesize: 0.88 MB
  • 16 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Regular languages
  • Mathematics of computing → Combinatorics on words
Keywords
  • Boundary sequences
  • Sturmian words
  • Numeration systems
  • Automata
  • Graph of addition

Metrics

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

Abstract

Generalizing the notion of the boundary sequence introduced by Chen and Wen, the nth term of the 𝓁-boundary sequence of an infinite word is the finite set of pairs (u,v) of prefixes and suffixes of length 𝓁 appearing in factors uyv of length n+𝓁 (n ≥ 𝓁 ≥ 1). Otherwise stated, for increasing values of n, one looks for all pairs of factors of length 𝓁 separated by n-𝓁 symbols.
For the large class of addable numeration systems U, we show that if an infinite word is U-automatic, then the same holds for its 𝓁-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). We also provide examples of numeration systems and U-automatic words with a boundary sequence that is not U-automatic. In the second part of the paper, we study the 𝓁-boundary sequence of a Sturmian word. We show that it is obtained through a sliding block code from the characteristic Sturmian word of the same slope. We also show that it is the image under a morphism of some other characteristic Sturmian word.

Cite As Get BibTex

Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. On Extended Boundary Sequences of Morphic and Sturmian Words. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 79:1-79:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.MFCS.2022.79

Author Details

Michel Rigo
  • Department of Mathematics, University of Liège, Belgium
Manon Stipulanti
  • Department of Mathematics, University of Liège, Belgium
Markus A. Whiteland
  • Department of Mathematics, University of Liège, Belgium

Funding

  • Stipulanti, Manon: Supported by the FNRS Research grant 1.B.397.20F.
  • Whiteland, Markus A.: Supported by the FNRS Research grant 1.B.466.21F.

Acknowledgements

We thank Jean-Paul Allouche for references [Ethan M. Coven, 1974; Parvaix, 1997; Michael E. Paul, 1974], and Jeffrey Shallit for discussions about the "logical approach". The anonymous referees are warmly thanked for providing useful feedback improving the quality of the text.

References

  1. Jean-Paul Allouche and Jeffrey Shallit. Automatic sequences: Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003. Google Scholar
  2. Aseem Baranwal, Luke Schaeffer, and Jeffrey Shallit. Ostrowski-automatic sequences: Theory and applications. Theoretical Computer Science, 858:122-142, 2021. URL: https://doi.org/10.1016/j.tcs.2021.01.018.
  3. Valérie Berthé, Hiromi Ei, Shunji Ito, and Hui Rao. On substitution invariant Sturmian words: an application of Rauzy fractals. RAIRO Theoretical Informatics and Applications, 41(3):329-349, 2007. URL: https://doi.org/10.1051/ita:2007026.
  4. Valérie Berthé and Michel Rigo, editors. Combinatorics, Automata, and Number Theory, volume 135 of Encyclopedia of Mathematics and its Applications. Cambridge University Press, 2010. URL: https://doi.org/10.1017/CBO9780511777653.
  5. Véronique Bruyère and Georges Hansel. Bertrand numeration systems and recognizability. Theoretical Computer Science, 181(1):17-43, 1997. URL: https://doi.org/10.1016/S0304-3975(96)00260-5.
  6. Julien Cassaigne. Sequences with grouped factors. In Symeon Bozapalidis, editor, Proceedings of the 3rd International Conference Developments in Language Theory, pages 211-222. Aristotle University of Thessaloniki, 1997. Google Scholar
  7. Émilie Charlier, Célia Cisternino, and Manon Stipulanti. Regular sequences and synchronized sequences in abstract numeration systems. European Journal of Combinatorics, 101:103475, 2022. URL: https://doi.org/10.1016/j.ejc.2021.103475.
  8. Jin Chen and Zhi-Xiong Wen. On the abelian complexity of generalized Thue-Morse sequences. Theoretical Computer Science, 780:66-73, 2019. URL: https://doi.org/10.1016/j.tcs.2019.02.014.
  9. Alan Cobham. Uniform tag seqences. Mathematical Systems Theory, 6(3):164-192, 1972. URL: https://doi.org/10.1007/BF01706087.
  10. Ethan M. Coven. Sequences with minimal block growth ii. Mathematical systems theory, 8:376-382, 1974. URL: https://doi.org/10.1007/BF01780584.
  11. David Crisp, William Moran, Andrew Pollington, and Peter Shiue. Substitution invariant cutting sequences. Journal de Théorie des Nombres de Bordeaux, 5(1):123-137, 1993. URL: https://doi.org/10.2307/26273915.
  12. James Currie, Tero Harju, Pascal Ochem, and Narad Rampersad. Some further results on squarefree arithmetic progressions in infinite words. Theoretical Computer Science, 799:140-148, 2019. URL: https://doi.org/10.1016/j.tcs.2019.10.006.
  13. Gilles Didier. Caractérisation des N-écritures et application à l'étude des suites de complexité ultimement n+c^ste. Theoretical Computer Science, 215(1-2):31-49, 1999. URL: https://doi.org/10.1016/S0304-3975(97)00122-9.
  14. Jean-Pierre Duval. Relationship between the period of a finite word and the length of its unbordered segments. Discrete Mathematics, 40:31-44, 1982. URL: https://doi.org/10.1016/0012-365X(82)90186-8.
  15. Sébastien Ferenczi and Christian Mauduit. Transcendence of numbers with a low complexity expansion. Journal of Number Theory, 67(2):146-161, 1997. URL: https://doi.org/10.1006/jnth.1997.2175.
  16. Aviezri S. Fraenkel. Systems of numeration. The American Mathematical Monthly, 92:105-114, 1985. URL: https://doi.org/10.2307/2322638.
  17. Christiane Frougny. On the sequentiality of the successor function. Information and Computation, 139(1):17-38, 1997. URL: https://doi.org/10.1006/inco.1997.2650.
  18. Melissa J. Fullwood, Chia-Lin Wei, Edison T. Liu, and Yijun Ruan. Next-generation DNA sequencing of paired-end tags (PET) for transcriptome and genome analyses. Genome research, 19(4):521-532, 2009. URL: https://doi.org/10.1101/gr.074906.107.
  19. Ying-Jun Guo, Xiao-Tao Lü, and Zhi-Xiong Wen. On the boundary sequence of an automatic sequence. Discrete Mathematics, 345(1):9, 2022. Id/No 112632. URL: https://doi.org/10.1016/j.disc.2021.112632.
  20. Philipp Hieronymi and Alonza Terry Jr. Ostrowski Numeration Systems, Addition, and Finite Automata. Notre Dame Journal of Formal Logic, 59(2):215-232, 2018. URL: https://doi.org/10.1215/00294527-2017-0027.
  21. Philipp Hieronymi, Dun Ma, Reed Oei, Luke Schaeffer, Christian Schulz, and Jeffrey Shallit. Decidability for Sturmian Words. In Florin Manea and Alex Simpson, editors, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022), volume 216 of Leibniz International Proceedings in Informatics (LIPIcs), pages 24:1-24:23, Dagstuhl, Germany, 2022. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. URL: https://doi.org/10.4230/LIPIcs.CSL.2022.24.
  22. Juhani Karhumäki, Aleksi Saarela, and Luca Q. Zamboni. On a generalization of abelian equivalence and complexity of infinite words. Journal of Combinatorial Theory, Series A, 120(8):2189-2206, 2013. URL: https://doi.org/10.1016/j.jcta.2013.08.008.
  23. Jana Lepšová, Edita Pelantová, and Štěpán Starosta. On a faithful representation of Sturmian morphisms, 2022. Preprint. URL: https://doi.org/10.48550/ARXIV.2203.00373.
  24. M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 2002. Google Scholar
  25. Xiao-Tao Lü, Jin Chen, Zhi-Xiong Wen, and Wen Wu. On the 2-binomial complexity of the generalized Thue-Morse words, 2021. Preprint. URL: https://doi.org/10.48550/ARXIV.2112.05347.
  26. Dimitris Margaritis and Steven S. Skiena. Reconstructing strings from substrings in rounds. In 36th Annual symposium on Foundations of computer science. Held in Milwaukee, WI, USA, October 23-25, 1995, pages 613-620. Los Alamitos, CA: IEEE Computer Society Press, 1995. Google Scholar
  27. Adeline Massuir, Jarkko Peltomäki, and Michel Rigo. Automatic sequences based on Parry or Bertrand numeration systems. Advances in Applied Mathematics, 108:11-30, 2019. URL: https://doi.org/10.1016/j.aam.2019.03.003.
  28. Hamoon Mousavi. Walnut prover, 2016. , https://cs.uwaterloo.ca/~shallit/walnut.html. URL: https://github.com/hamousavi/Walnut.
  29. Hamoon Mousavi, Luke Schaeffer, and Jeffrey Shallit. Decision algorithms for Fibonacci-automatic words. I: Basic results. RAIRO Theoretical Informatics and Applications, 50(1):39-66, 2016. URL: https://doi.org/10.1051/ita/2016010.
  30. Bruno Parvaix. Propriétés d'invariance des mots sturmiens. Journal de Théorie des Nombres de Bordeaux, 9(2):351-369, 1997. URL: https://doi.org/10.5802/jtnb.207.
  31. Michael E. Paul. Minimal symbolic flows having minimal block growth. Mathematical systems theory, 8:309-315, 1974. URL: https://doi.org/10.1007/BF01780578.
  32. Jarkko Peltomäki and Ville Salo. Automatic winning shifts. Information and Computation, 285:104883, 2022. URL: https://doi.org/10.1016/j.ic.2022.104883.
  33. Jarkko Peltomäki and Markus A. Whiteland. On k-abelian equivalence and generalized Lagrange spectra. Acta Arithmetica, 194(2):135-154, 2020. URL: https://doi.org/10.4064/aa180927-10-9.
  34. Li Peng and Bo Tan. Sturmian Sequences and Invertible Substitutions. Discrete Mathematics & Theoretical Computer Science, 13(2), 2011. URL: https://doi.org/10.46298/dmtcs.554.
  35. Thomas Place, Lorijn Van Rooijen, and Marc Zeitoun. Separating regular languages by locally testable and locally threshold testable languages. In 33nd international conference on foundations of software technology and theoretical computer science, FSTTCS 2013, Guwahati, India, December 12-14, 2013. Proceedings, pages 363-375. Wadern: Schloss Dagstuhl - Leibniz Zentrum für Informatik, 2013. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2013.363.
  36. Michel Rigo. Formal languages, automata and numeration systems. 2. Networks and Telecommunications Series. ISTE, London; John Wiley & Sons, Inc., Hoboken, NJ, 2014. Applications to recognizability and decidability, With a foreword by Valérie Berthé. Google Scholar
  37. Michel Rigo. Relations on words. Indagationes Mathematicae, 28(1):183-204, 2017. URL: https://doi.org/10.1016/j.indag.2016.11.018.
  38. Michel Rigo and Arnaud Maes. More on generalized automatic sequences. Journal of Automata, Languages, and Combinatorics, 7(3):351-376, 2002. URL: https://doi.org/10.25596/jalc-2002-351.
  39. Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. Binomial complexities and Parikh-collinear morphisms. In Volker Diekert and Mikhail Volkov, editors, Developments in Language Theory, pages 251-262, Cham, 2022. Springer International Publishing. URL: https://doi.org/10.1007/978-3-031-05578-2_20.
  40. Jeffrey Shallit. A second course in formal languages and automata theory. Cambridge: Cambridge University Press, 2009. URL: https://doi.org/10.1017/CBO9780511808876.
  41. Jeffrey Shallit. The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut. London Mathematical Society Lecture Note Series. Cambridge University Press, 2022. To appear. Google Scholar
  42. Bo Tan and Zhi-Ying Wen. Invertible substitutions and Sturmian sequences. European Journal of Combinatorics, 24(8):983-1002, 2003. URL: https://doi.org/10.1016/S0195-6698(03)00105-7.
  43. Shin-Ichi Yasutomi. On Sturmian sequences which are invariant under some substitution. In Number Theory and Its Applications (Kyoto, 1997), volume 2 of Dev. Math., pages 347-373. Kluwer Academic Publishers, Dordrecht, 1999. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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