Geodesic
On possible growths of arithmetical complexity
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 443-458

Voir la notice de l'article provenant de la source Numdam

The arithmetical complexity of infinite words, defined by Avgustinovich, Fon-Der-Flaass and the author in 2000, is the number of words of length n which occur in the arithmetical subsequences of the infinite word. This is one of the modifications of the classical function of subword complexity, which is equal to the number of factors of the infinite word of length n. In this paper, we show that the orders of growth of the arithmetical complexity can behave as many sub-polynomial functions. More precisely, for each sequence u of subword complexity f u (n) and for each prime p≥3 we build a Toeplitz word on the same alphabet whose arithmetical complexity is a(n)=Θ(nf u (⌈log p n⌉)).

DOI : 10.1051/ita:2006021
Classification : 68R15, 68Q45
Keywords: arithmetical complexity, infinite word, subword complexity, Toeplitz word, bispecial words 
@article{ITA_2006__40_3_443_0,
     author = {Frid, Anna E.},
     title = {On possible growths of arithmetical complexity},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {443--458},
     publisher = {EDP-Sciences},
     volume = {40},
     number = {3},
     year = {2006},
     doi = {10.1051/ita:2006021},
     mrnumber = {2269203},
     zbl = {1110.68120},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006021/}
}
TY  - JOUR
AU  - Frid, Anna E.
TI  - On possible growths of arithmetical complexity
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2006
SP  - 443
EP  - 458
VL  - 40
IS  - 3
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006021/
DO  - 10.1051/ita:2006021
LA  - en
ID  - ITA_2006__40_3_443_0
ER  - 
%0 Journal Article
%A Frid, Anna E.
%T On possible growths of arithmetical complexity
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2006
%P 443-458
%V 40
%N 3
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006021/
%R 10.1051/ita:2006021
%G en
%F ITA_2006__40_3_443_0
Frid, Anna E. On possible growths of arithmetical complexity. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 443-458. doi: 10.1051/ita:2006021

Cité par Sources :