On two conjectures of Shallit about Thue-Morse-like sequences

Dvořáková, Lubomíra; Kreczman, Savinien; Pelantová, Edita

doi:10.1016/j.ejc.2025.104250

Download

Article (Scientific journals)

On two conjectures of Shallit about Thue-Morse-like sequences

Dvořáková, Lubomíra; Kreczman, Savinien; Pelantová, Edita

2025 • In European Journal of Combinatorics, 132 (B), p. 104250, 1-25

Peer Reviewed verified by ORBi

Permalink
https://hdl.handle.net/2268/333319

DOI
10.1016/j.ejc.2025.104250

Files (2)Send to Details Statistics Bibliography Similar publications

Files

Full Text

EJC.pdf

Author postprint (643.35 kB)

Creative Commons License - Attribution, Non-Commercial, No Derivative

Download

Annexes

On_two_conjectures_of_Shallit_about_Thue_Morse_like_words.pdf

(729.72 kB)

First preprint version

Download

All documents in ORBi are protected by a user license.

Send to

RIS BibTex APA Chicago Permalink X Linkedin

Details

Keywords :

morphism; Thue-Morse sequence; factor complexity; critical exponent; asymptotic critical exponent; bispecial factors

Abstract :

[en] We study a class of infinite words $\xx_k$, $k \in \N, k\geq 1$, recently introduced by J. Shallit. This class includes the Thue-Morse sequence $\xx_1$, the Fibonacci-Thue-Morse sequence $\xx_2$, and the Allouche-Johnson sequence $\xx_3$. Shallit stated and for $k=3$ proved two conjectures on properties of $\xx_k$. The first conjecture concerns the factor complexity, the second one the critical exponent of these words. We confirm the validity of both conjectures for every $k$.

Disciplines :

Mathematics

Author, co-author :

Dvořáková, Lubomíra; Czech Technical University > Department of Mathematics, Faculty of Nuclear Sciences and Physical Engineering

Kreczman, Savinien ; Université de Liège - ULiège > Mathematics

Pelantová, Edita; Czech Technical University > Department of Mathematics, Faculty of Nuclear Sciences and Physical Engeneering

Language :

English

Title :

On two conjectures of Shallit about Thue-Morse-like sequences

Publication date :

09 October 2025

Journal title :

European Journal of Combinatorics

ISSN :

0195-6698

eISSN :

1095-9971

Publisher :

Elsevier, Netherlands

Volume :

132

Issue :

Pages :

104250, 1-25

Peer reviewed :

Peer Reviewed verified by ORBi

Additional URL :

https://doi.org/10.48550/arXiv.2506.04407

Funders :

F.R.S.-FNRS - Fonds de la Recherche Scientifique
WBI - Wallonie-Bruxelles International
FWB - Fédération Wallonie-Bruxelles
ULiège - Université de Liège

Funding number :

1.A.789.23F; WBI.WORLD/CD 2025/658054; 40030822

Funding text :

FNRS : Mandat "Aspirant". WBI : Bourse "WBI.WORLD". FWB : Bourse de voyage

Available on ORBi :

since 19 June 2025

Statistics

Number of views

86 (11 by ULiège)

Number of downloads

49 (0 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

OpenAlex citations

Bibliography

J.-P. Allouche, T. Johnson, Narayana's Cows and Delayed Morphisms, in: Journées D'Informatique Musicale, île de Tatihou, France, 1996, URL https://hal.science/hal-02986050.
Berstel, J., Perrin, D., The origins of combinatorics on words. European J. Combin. 28:3 (2007), 996–1022, 10.1016/j.ejc.2005.07.019.
Brlek, S., Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24:1 (1989), 83–96, 10.1016/0166-218X(92)90274-E.
Cassaigne, J., Complexité et facteurs spéciaux (Complexity and special factors). Bull. Belg. Math. Soc. - Simon Stevin 4:1 (1997), 67–88 URL http://eudml.org/doc/119937.
Damanik, D., Lenz, D., The index of Sturmian sequences. European J. Combin. 23:1 (2002), 23–29, 10.1006/eujc.2000.0496.
de Luca, A., Varicchio, S., Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), 333–348, 10.1016/0304-3975(89)90013-3.
Dolce, F., Dvořáková, L., Pelantová, E., On balanced sequences and their critical exponent. Theoret. Comput. Sci. 939 (2023), 18–47, 10.1016/j.tcs.2022.10.014.
Klouda, K., Bispecial factors in circular non-pushy D0L languages. Theoret. Comput. Sci. 445 (2012), 63–74, 10.1016/j.tcs.2012.05.007.
Letouzey, P., Generalized Hofstadter functions G,H and beyond: numeration systems and discrepancy. 2025 arXiv:2502.12615.
Meek, D.S., Rees, G.H.J.V., The solution of an iterated recurrence. Fibonacci Quart. 22:2 (1984), 101–104, 10.1080/00150517.1984.12429900.
Queffélec, M., Substitution dynamical systems - Spectral analysis. Lecture Notes in Math., 1294, 1987, 10.1007/BFb0081893.
Rajasekaran, A., Shallit, J., Smith, T., Additive number theory via automata theory. Theory Comput. Syst. 64:3 (2020), 542–567, 10.1007/s00224-019-09929-9.
Shallit, J., Subword complexity of the Fibonacci–Thue–Morse sequence: The proof of Dekking's conjecture. Indag. Math. 32:3 (2021), 729–735, 10.1016/j.indag.2021.03.004.
Shallit, J., The Narayana morphism and related words. 2025 arXiv:2503.01026.
Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas. Bull. Soc. R. Sci. Liege 41 (1972), 179–182.