An isolated point in the Heinis spectrum

Turki, Ramzi

doi:10.1051/ita/2016004

¹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, 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
Keywords: Rauzy graph, Sturmian words, complexity function

Affiliations des auteurs :

Turki, Ramzi ^{1
,

2}

¹ 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

@article{ITA_2016__50_1_21_0,
     author = {Turki, Ramzi},
     title = {An isolated point in the {Heinis} spectrum},
     journal = {RAIRO. Theoretical Informatics and Applications},
     pages = {21--38},
     year = {2016},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     doi = {10.1051/ita/2016004},
     mrnumber = {3518157},
     zbl = {1354.68218},
     language = {en},
     url = {https://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
PY  - 2016
SP  - 21
EP  - 38
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - https://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
%D 2016
%P 21-38
%V 50
%N 1
%I EDP-Sciences
%U https://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, 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

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. | MR | Zbl | Numdam | DOI

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. | MR | Zbl | DOI

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. | MR | Zbl | DOI

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. | MR | JFM | DOI

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

Cité par Sources :