Reference : Templates for the k-binomial complexity of the Tribonacci word
E-prints/Working papers : First made available on ORBi
Engineering, computing & technology : Computer science
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/234215
Templates for the k-binomial complexity of the Tribonacci word
English
Lejeune, Marie mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Rigo, Michel mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Rosenfeld, Matthieu mailto [Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes >]
Apr-2019
No
[en] combinatorics on words ; binomial coefficients ; k-binomial complexity ; Tribonacci word
[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.
Fédération Wallonie Bruxelles. Fonds de la Recherche Scientifique - F.R.S.-FNRS
Researchers
http://hdl.handle.net/2268/234215

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
version_kronecker.pdfAuthor preprint560.89 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
calculAncestorsTemplates_LastVersion.pdfPrinted version of the Mathematica notebook78.81 kBView/Open
Open access
calculAncestorsTemplates_LastVersion.nbMathematica notebook130.02 kBView/Open
Open access
CsmallList.mComputed bounds for small eigenvalues247 BView/Open
Open access
CgreatList_n6l600.mComputed bounds for large eigenvalues200 BView/Open
Open access
seenTemplates.mList of possibly realizable ancestors18.45 MBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.