KERNEL WORDS AND GAP SEQUENCE OF THE TRIBONACCI SEQUENCE

doi:10.1016/S0252-9602(15)30086-2

Abstract

Abstract:

In this paper, we investigate the factor properties and gap sequence of the Tri-bonacci sequence, the fixed point of the substitution σ(a, b, c)=(ab, ac, a). Let ω_p be the p-th occurrence of ω and G_p(ω) be the gap between ω_p and ω_p+1. We introduce a notion of kernel for each factor ω, and then give the decomposition of the factor ω with respect to its kernel. Using the kernel and the decomposition, we prove the main result of this paper:for each factor ω, the gap sequence {G_p(ω)}_p≥1 is the Tribonacci sequence over the alphabet {G₁(ω), G₂(ω), G₄(ω)}, and the expressions of gaps are determined completely. As an appli-cation, for each factor ω and p∈N, we determine the position of ω_p. Finally we introduce a notion of spectrum for studying some typical combinatorial properties, such as power, overlap and separate of factors.

Key words: the Tribonacci sequence, gap sequence, kernel word, combinatorial property, spectrum

CLC Number:

11B85

Yuke HUANG, Zhiying WEN. KERNEL WORDS AND GAP SEQUENCE OF THE TRIBONACCI SEQUENCE[J].Acta mathematica scientia,Series B, 2016, 36(1): 173-194.

Trendmd

References

[1] Aráujo I M, Bruyère V. Words derivated from Sturmian words. Theor Comput Sci, 2005, 340:204-219
[2] Arnoux P, Rauzy G. Représentation géométrique de suites de complexité 2n +1. Bull Soc Math France, 1991, 119:199-215
[3] Allouche J P, Shallit J. Automatic Sequences:Theory, Applications, Generalizations. Cambridge:Cam-bridge Univ Press, 2003
[4] Berstel J. Recent results in Sturmian words//Dassow J, Salomaa A, eds. Developments in Language Theory. Singapore:World Scientific, 1966:13-24
[5] Berstel J. Mot de Fibonacci, Séminaire d'informatique thérique. LITP, Paris, Année, 1980/1981:57-78
[6] Berstel J. Recent results on extensions of Sturmian words. Inter J Algebra Comput, 2002, 12:371-385
[7] Balková L, Pelantová E, Steiner W. Sequences with constant number of return words. Monatsh Math, 2008, 155:251-263
[8] Chekhova N, Hubert P, Messaoudi A. Propriétés combinatoires, ergodiques et arithmétiques de la substi-tution de Tribonacci. J Théor Nombres Bordeaux, 2001, 13:371-394
[9] Cao W T, Wen Z Y. Some properties of the factors of Sturmian sequences. Theor Comput Sci, 2003, 304:365-385
[10] Durand F. A characterization of substitutive sequences using return words. Discrete Math, 1998, 179:89-101
[11] Du C F, Mousavi H, Schaeffer L, Shallit J. Decision algorithms for Fibonacci-automatic words, with appli-cations to pattern avoidance. arxiv.1406.0670
[12] Huang Y K, Wen Z Y. The sequence of return words of the Fibonacci sequence. Theor Comput Sci, 2015, 593:106-116
[13] Justin J, Vuillon L. Return words in Sturmian and episturmian words. RAIRO-Theoretical Informatics and Applications, 2000, 34(5):343-356
[14] Lothaire M. Combinatorics on words//Encyclopedia of Mathematics and its Applications Vol 17. Reading, MA:Addison-Wesley, 1983
[15] Lothaire M. Algebraic Combinatorics on Words. Cambridge:Cambridge Univ Press, 2002
[16] Liu H, Wen Z Y. IFS on boundaries of homogeneous trees:WQB condition and multifractal analysis. Acta Math Sci, 2010, 30B(5):1514-1522
[17] Mousavi H, Shallit J. Mechanical proofs of properties of the Tribonacci word. arXiv:1407.5841v1
[18] Niu M, Wen Z Y. On the correlation dimension of the spectral measure for the m-multiplicative sequence. Acta Math Sci, 2007, 27B(5):862-870
[19] Rosema S W, Tijdeman R. The Tribonacci substitution. Integers:Elect J Combin Number Theory, 2005, 5(3):?A13
[20] Richomme G, Saari K, Zamboni L Q. Balance and Abelian complexity of the Tribonacci word. Adv Appl Math, 2010, 45:212-231
[21] Tan B, Wen Z Y. Some properties of the Tribonacci sequence. European J Combin, 2007, 28:1703-1719
[22] Wen Z X, Wen Z Y. Some properties of the singular words of the Fibonacci word. European J Combin, 1994, 15:587-598
[23] Vuillon L. A characterization of Sturmian words by return words. European J Combin, 2001, 22:263-275