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
Available on ORBi :
since 05 April 2019

Statistics


Number of views
203 (17 by ULiège)
Number of downloads
313 (5 by ULiège)

Bibliography


Similar publications



Sorry the service is unavailable at the moment. Please try again later.
Contact ORBi