On extended boundary sequences of morphic and Sturmian words

Theoretical Computer Science; Geometry and Topology; Discrete Mathematics and Combinatorics; Computational Theory and Mathematics; Applied Mathematics

Abstract :

[en] 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 abstract numeration systems S, we show that if an infinite word is S-automatic, then the same holds for its ℓ-boundary sequence. In particular, they are both morphic (or generated by an HD0L system). To precise the limits of this result, we discuss examples of non-addable numeration systems and Sautomatic words for which the boundary sequence is nevertheless S-automatic and conversely, S-automatic words with a boundary sequence that is not S-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.

Disciplines :

Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Stipulanti, Manon ; Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes

Whiteland, Markus ; Université de Liège - ULiège > Mathematics

Language :

English

Title :

On extended boundary sequences of morphic and Sturmian words

Publication date :

2024

Journal title :

Electronic Journal of Combinatorics

ISSN :

1097-1440

eISSN :

1077-8926

Publisher :

Australian National University

Volume :

Issue :

Pages :

P1.9

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://www.combinatorics.org/ojs/index.php/eljc/article/download/v31i1p9/pdf

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique

Funding text :

Michel Rigo is supported by the FNRS Research grant T.196.23 (PDR). Manon Stipulanti is supported by the FNRS Research grant 1.C.104.24F. Markus Whiteland is supported by the FNRS Research grant 1.B.466.21F.

Available on ORBi :

since 30 May 2024

Statistics

Number of views

27 (0 by ULiège)

Number of downloads

14 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenAlex citations

Bibliography

Jean-Paul Allouche, Julien Cassaigne, Jeffrey Shallit, and Luca Q. Zamboni. A taxonomy of morphic sequences, 2017. arXiv:1711.10807.
Jean-Paul Allouche and Jeffrey Shallit. Automatic sequences: Theory, applications, generalizations. Cambridge University Press, Cambridge, 2003.
Tom M. Apostol. Introduction to analytic number theory. Undergraduate Texts in Mathematics. Springer-Verlag, New York-Heidelberg, 1976.
Aseem Baranwal, Luke Schaeffer, and Jeffrey Shallit. Ostrowski-automatic sequences: Theory and applications. Theoretical Computer Science, 858:122–142, 2021. doi: 10.1016/j.tcs.2021.01.018.
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. doi:10.1051/ita:2007026.
Valérie Berthé, Charles Holton, and Luca Q. Zamboni. Initial powers of Sturmian sequences. Acta Arithmetica, 122(4):315–347, 2006. doi:10.4064/aa122-4-1.
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. doi:10.1017/CBO9780511777653.
Véronique Bruyère and Georges Hansel. Bertrand numeration systems and recognizability. Theoretical Computer Science, 181(1):17–43, 1997. doi:10.1016/S0304-3975(96)00260-5.
Véronique Bruyère, Georges Hansel, Christian Michaux, and Roger Villemaire. Logic and p-recognizable sets of integers. Bulletin of the Belgian Mathematical Society. Simon Stevin, 1(2):191–238, 1994. Journées Montoises (Mons, 1992). doi:10.36045/bbms/1103408547.
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.
Émilie Charlier, Célia Cisternino, and Manon Stipulanti. Regular sequences and synchronized sequences in abstract numeration systems. European Journal of Combinatorics, 101:103475, 2022. doi:10.1016/j.ejc.2021.103475.
Jin Chen and Zhi-Xiong Wen. On the abelian complexity of generalized Thue–Morse sequences. Theoretical Computer Science, 780:66–73, 2019. doi:10.1016/j.tcs. 2019.02.014.
Alan Cobham. Uniform tag seqences. Mathematical Systems Theory, 6(3):164–192, 1972. doi:10.1007/BF01706087.
Ethan M. Coven. Sequences with minimal block growth II. Mathematical Systems Theory, 8:376–382, 1974. doi:10.1007/BF01780584.
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. doi:10.2307/26273915.
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. doi:10.1016/j.tcs.2019.10.006.
Gilles Didier. Caractérisation des N-écritures et application à l’étude des suites de complexité ultimement n+cste. Theoretical Computer Science, 215(1–2):31–49, 1999. doi:10.1016/S0304-3975(97)00122-9.
Fabien Durand and Michel Rigo. Syndeticity and independent substitutions. Advances in Applied Mathematics, 42(1):1–22, 2009. doi:10.1016/j.aam.2008.02. 001.
Jean-Pierre Duval. Relationship between the period of a finite word and the length of its unbordered segments. Discrete Mathematics, 40:31–44, 1982. doi:10.1016/0012-365X(82)90186-8.
Sébastien Ferenczi and Christian Mauduit. Transcendence of numbers with a low complexity expansion. Journal of Number Theory, 67(2):146–161, 1997. doi:10. 1006/jnth.1997.2175.
Aviezri S. Fraenkel. Systems of numeration. The American Mathematical Monthly, 92:105–114, 1985. doi:10.2307/2322638.
Christiane Frougny. On the sequentiality of the successor function. Information and Computation, 139(1):17–38, 1997. doi:10.1006/inco.1997.2650.
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. doi:10.1101/gr.074906.107.
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. doi: 10.1016/j.disc.2021.112632.
Philipp Hieronymi and Alonza Terry Jr. Ostrowski Numeration Systems, Addition, and Finite Automata. Notre Dame Journal of Formal Logic, 59(2):215–232, 2018. doi:10.1215/00294527-2017-0027.
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. doi: 10.4230/LIPIcs.CSL.2022.24.
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. doi:10.1016/j.jcta.2013.08.008.
Pierre B. A. Lecomte and Michel Rigo. Numeration systems on a regular language. Theory of Computing Systems, 34(1):27–44, 2001. doi:10.1007/s002240010014.
Jana Lepšová, Edita Pelantová, and Štěpán Starosta. On a faithful representation of Sturmian morphisms. European Journal of Combinatorics, 110:Paper No. 103707, 20, 2023. doi:10.1016/j.ejc.2023.103707.
M. Lothaire. Algebraic combinatorics on words, volume 90 of Encyclopedia of Mathematics and its Applications. Cambridge: Cambridge University Press, 2002.
Xiao-Tao Lü, Jin Chen, Zhi-Xiong Wen, and Wen Wu. On the 2-binomial complexity of the generalized Thue-Morse words, 2021. Preprint. arXiv:2112.05347.
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.
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. doi:10.1016/j.aam.2019.03.003.
Hamoon Mousavi. Walnut prover, 2016. https://github.com/hamousavi/Walnut, https://cs.uwaterloo.ca/~shallit/walnut.html.
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. doi:10.1051/ita/2016010.
Reed Oei, Dun Ma, Christian Schulz, and Philipp Hieronymi. Pecan: An automated theorem prover for automatic sequences using Büchi automata, 2021. arXiv:2102.01727.
Bruno Parvaix. Propriétés d’invariance des mots sturmiens. Journal de Théorie des Nombres de Bordeaux, 9(2):351–369, 1997. doi:10.5802/jtnb.207.
Michael E. Paul. Minimal symbolic flows having minimal block growth. Mathematical systems theory, 8:309–315, 1974. doi:10.1007/BF01780578.
Jarkko Peltomäki and Ville Salo. Automatic winning shifts. Information and Computation, 285:104883, 2022. doi:10.1016/j.ic.2022.104883.
Jarkko Peltomäki and Markus A. Whiteland. On k-abelian equivalence and generalized Lagrange spectra. Acta Arithmetica, 194(2):135–154, 2020. doi:10.4064/aa180927-10-9.
Li Peng and Bo Tan. Sturmian Sequences and Invertible Substitutions. Discrete Mathematics & Theoretical Computer Science, 13(2), 2011. doi:10.46298/dmtcs. 554.
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. doi:10.4230/LIPIcs.FSTTCS.2013.363.
Michel Rigo. Numeration systems on a regular language: Arithmetic operations, recognizability and formal power series. Theoretical Computer Science, 269(1-2):469– 498, 2001. doi:10.1016/S0304-3975(01)00184-0.
Michel Rigo. Construction of regular languages and recognizability of polynomials. Discrete Mathematics, 254(1-3):485–496, 2002. doi:10.1016/S0012-365X(01) 00377-6.
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é.
Michel Rigo. Relations on words. Indagationes Mathematicae, 28(1):183–204, 2017. doi:10.1016/j.indag.2016.11.018.
Michel Rigo and Arnaud Maes. More on generalized automatic sequences. Journal of Automata, Languages, and Combinatorics, 7(3):351–376, 2002. doi:10.25596/jalc-2002-351.
Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. On Extended Boundary Sequences of Morphic and Sturmian Words. In Stefan Szeider, Robert Ganian, and Alexandra Silva, editors, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), volume 241 of Leibniz International Proceedings in Informatics (LIPIcs), pages 79:1–79:16, Dagstuhl, Germany, 2022. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.MFCS.2022.79.
Michel Rigo, Manon Stipulanti, and Markus A. Whiteland. Characterizations of families of morphisms and words via binomial complexities. European Journal of Combinatorics, 2023. To appear. arXiv:2201.04603.
Klaus Schmidt. On periodic expansions of Pisot numbers and Salem numbers. Bulletin of the London Mathematical Society, 12:269–278, 1980. doi:10.1112/blms/12. 4.269.
Jeffrey Shallit. A second course in formal languages and automata theory. Cambridge: Cambridge University Press, 2009. doi:10.1017/CBO9780511808876.
Jeffrey Shallit. The Logical Approach to Automatic Sequences: Exploring Combinatorics on Words with Walnut. London Mathematical Society Lecture Note Series. Cambridge University Press, 2022. doi:10.1017/9781108775267.
Neil Sloane. The On-Line Encyclopedia of Integer Sequences. http://oeis.org.
Bo Tan and Zhi-Ying Wen. Invertible substitutions and Sturmian sequences. European Journal of Combinatorics, 24(8):983–1002, 2003. doi:10.1016/S0195-6698(03)00105-7.
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.