Eprint first made available on ORBi (E-prints, working papers and research blog)
Templates for the k-binomial complexity of the Tribonacci word
Lejeune, Marie; Rigo, Michel; Rosenfeld, Matthieu
2019
 

Files


Full Text
version_kronecker.pdf
Author preprint (574.35 kB)
Download
Annexes
calculAncestorsTemplates_LastVersion.pdf
Publisher postprint (80.7 kB)
Printed version of the Mathematica notebook
Download
calculAncestorsTemplates_LastVersion.nb
Publisher postprint (133.14 kB)
Mathematica notebook
Download
CsmallList.m
Publisher postprint (247 B)
Computed bounds for small eigenvalues
Download
CgreatList_n6l600.m
Publisher postprint (200 B)
Computed bounds for large eigenvalues
Download
seenTemplates.m
Publisher postprint (18.89 MB)
List of possibly realizable ancestors
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
combinatorics on words; binomial coefficients; k-binomial complexity; Tribonacci word
Abstract :
[en] Consider the k-binomial equivalence: two finite words are equivalent if they share the same subwords of length at most k with the same multiplicities. With this relation, the k-binomial complexity of an infinite word x maps the integer n to the number of pairwise non-equivalent factors of length n occurring in x. In this paper based on the notion of template introduced by Currie et al., we show that, for all k > 1, the k-binomial complexity of the Tribonacci word coincides with its usual factor complexity p(n)=2n+1. A similar result was already known for Sturmian words but the proof relies on completely different techniques that seemingly could not be applied for Tribonacci.
Disciplines :
Mathematics
Computer science
Author, co-author :
Lejeune, Marie ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Rosenfeld, Matthieu ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Templates for the k-binomial complexity of the Tribonacci word
Publication date :
April 2019
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 05 April 2019

Statistics


Number of views
155 (17 by ULiège)
Number of downloads
244 (5 by ULiège)

Bibliography


Similar publications



Contact ORBi