An isolated point in the Heinis spectrum

Turki, Ramzi

doi:10.1051/ita/2016004

Turki, Ramzi ^1,²

¹ Institut de mathématiques de Marseille, Université d’Aix-Marseille, Case 907, 163, avenue de Luminy, 13288 Marseille, cedex 9, France
² Faculté des Sciences de Sfax, Département de Mathématiques, Route de la Soukra km 3.5, B.P. 1171, 3000 Sfax, Tunisie

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 21-38.

Résumé

This paper continues the study initiated by Alex Heinis of the set $H$ of pairs $(α, β)$ obtained as the lower and upper limit of the ratio of complexity and length for an infinite word. Heinis proved that this set contains no point under a certain curve. We extend this result by proving that there are only three points on this curve, namely $(1, 1)$ , (3/2, 5/3) and $(2, 2)$ , and moreover the point (3/2, 5/3) is an isolated point in the set $H$ . For this, we use Rauzy graphs, generalizing techniques of Ali Aberkane.

Reçu le : 2016-03-24
Accepté le : 2016-03-24

MR Zbl

DOI : 10.1051/ita/2016004

Classification : 68R15
Mots-clés : Rauzy graph, Sturmian words, complexity function

Affiliations des auteurs :

Turki, Ramzi ^{1, 2}

@article{ITA_2016__50_1_21_0,
     author = {Turki, Ramzi},
     title = {An isolated point in the {Heinis} spectrum},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {21--38},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ita/2016004},
     mrnumber = {3518157},
     zbl = {1354.68218},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2016004/}
}

TY  - JOUR
AU  - Turki, Ramzi
TI  - An isolated point in the Heinis spectrum
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 21
EP  - 38
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2016004/
DO  - 10.1051/ita/2016004
LA  - en
ID  - ITA_2016__50_1_21_0
ER  -

%0 Journal Article
%A Turki, Ramzi
%T An isolated point in the Heinis spectrum
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 21-38
%V 50
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2016004/
%R 10.1051/ita/2016004
%G en
%F ITA_2016__50_1_21_0

Turki, Ramzi. An isolated point in the Heinis spectrum. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 21-38. doi : 10.1051/ita/2016004. http://www.numdam.org/articles/10.1051/ita/2016004/

Bibliographie
Cité par

A. Aberkane, Exemples de suites de complexité inférieure à 2 $n$ . Bull. Belg. Math. Soc. 8 (2001) 161–180. | MR | Zbl

A. Aberkane, Utilisation des graphes de Rauzy dans la caractérisation de certaines familles de suites de faible complexité, Ph. D. thesis. Université d’Aix-Marseille 2 (2002).

P. Arnoux and G. Rauzy, Représentation géometrique des suites de complexité 2 $n$ +1. Bull. Soc. Math. France 119 (1991) 199–215. | DOI | Numdam | MR | Zbl

V. Berthé and M. Rigo, Combinatorics, Automata, and Number Theory. Cambridge University Press, Cambridge (2010). | MR | Zbl

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

D. Damanik, Local symmetries in the period doubling sequence. Discrete Appl. Math. 100 (2000) 115–121. | DOI | MR | Zbl

A. Heinis, Arithmetics and combinatorics of words of low complexity. Ph. D. thesis, University of Leiden (2001). | Zbl

A. Heinis, The $P (n) / n$ -function for bi-infinite words. Theoret. Comput. Sci. 273 (2002) 35–46. | DOI | MR | Zbl

J. Leroy, An $S$ -adic characterization of minimal subshifts with first difference of complexity $1 \leq p (n + 1) - p (n) \leq 2$ . Discrete Math. Theor. Comput. Sci. 16 (2014) 233–286. | MR | Zbl

M. Lothaire, Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002). | Zbl

M. Morse, G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938) 815–866. | DOI | JFM | MR

G. Rote, Sequences with subword complexity $2 n$ . J. Number Theory 46 (1994) 196–213. | DOI | MR | Zbl

Cité par Sources :