On the Complexity of the Generalized Fibonacci Words
RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 5

In this paper we undertake a general study of the complexity function of the generalized Fibonacci words which are generated by the morphism defined by σ l , m ( a ) = a l b m and σ l , m ( a ) = a ...

DOI : 10.1051/ita/2022007
Classification : 68R15
Keywords: Infinite words, special factors, morphisms, complexity 
@article{ITA_2022__56_1_A5_0,
     author = {Cassaigne, Julien and Kabor\'e, Idrissa},
     title = {On the {Complexity} of the {Generalized} {Fibonacci} {Words}},
     journal = {RAIRO. Theoretical Informatics and Applications},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     doi = {10.1051/ita/2022007},
     mrnumber = {4424995},
     zbl = {1517.68314},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2022007/}
}
TY  - JOUR
AU  - Cassaigne, Julien
AU  - Kaboré, Idrissa
TI  - On the Complexity of the Generalized Fibonacci Words
JO  - RAIRO. Theoretical Informatics and Applications
PY  - 2022
VL  - 56
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2022007/
DO  - 10.1051/ita/2022007
LA  - en
ID  - ITA_2022__56_1_A5_0
ER  - 
%0 Journal Article
%A Cassaigne, Julien
%A Kaboré, Idrissa
%T On the Complexity of the Generalized Fibonacci Words
%J RAIRO. Theoretical Informatics and Applications
%D 2022
%V 56
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2022007/
%R 10.1051/ita/2022007
%G en
%F ITA_2022__56_1_A5_0
Cassaigne, Julien; Kaboré, Idrissa. On the Complexity of the Generalized Fibonacci Words. RAIRO. Theoretical Informatics and Applications, Tome 56 (2022), article no. 5. doi: 10.1051/ita/2022007

[1] J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press, UK (2003). | MR | Zbl | DOI

[2] J. Berstel, Mots de Fibonacci, L.I.T.P. Séminaire d'informatique Théorique, Paris (1980–1981), 57–78. | Zbl | Numdam

[3] J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701–715. | MR | Zbl | Numdam | DOI

[4] J. Cassaigne, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. 4 (1997) 67–88. | MR | Zbl

[5] J. Cassaigne, An algorithm to test if a given circular HDOL-language avoids a pattern, in IFIP World Computer Congress'94, North-Holland (1994) 459–464. | MR

[6] J. Cassaigne and I. Kaboré, Etude de la complexité du mot de Fibonacci géneralisé, in: Proceedings of 11th African Conference on Research in Computer Science and Applied Mathematics, CARI' 12 (2012) 62–69. | Zbl

[7] J. Cassaigne and F. Nicolas, Complexity, in: Combinatorics, Automata and Number Theory, edited by V. Berthé and M. Rigo. Vol. 135 of Encyclopedia of Mathematics and its Applications. Cambridge University Press (2010). | MR | Zbl | DOI

[8] A. Ehrenfeucht, K. P. Lee and G. Rozenberg, Subword complexities of various classes of deterministic developmental languages without interaction. Theoret. Comput. Sci. 1 (1975) 59–75. | MR | Zbl | DOI

[9] A. De Luca, A combinatorial property of the Fibonacci words. Inform. Process. Lett. 12 (1981) 193–195. | MR | Zbl | DOI

[10] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (2002). | Zbl | MR | DOI

[11] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199–204. | MR | Zbl | Numdam | DOI

[12] G. Pirillo, From the Fibonacci word to Sturmian words. Publ. Math. Debrecen 54 (1999) 961–971. | MR | Zbl

Cité par Sources :