Reference : Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
Scientific congresses and symposiums : Paper published in a journal
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/2268/149313
Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
English
Rigo, Michel mailto [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
Salimov, Pavel [Université de Liège - ULg > Département de mathématique > Mathématiques discrètes >]
2013
Lecture Notes in Computer Science
Springer
8079
Combinatorics on Words
217-228
Yes
No
International
0302-9743
1611-3349
Berlin
Germany
WORDS 2013
from 16-09-2013 to 20-09-2013
Turku
Finland
[en] Sturmian word ; Thue-Morse word ; Abelian complexity ; Combinatorics on words ; Binomial coefficient
[en] The binomial coefficient of two words u and v is the number of times v occurs as a subsequence of u. Based on this classical notion, we introduce the m-binomial equivalence of two words refining the abelian equivalence. The m-binomial complexity of an infinite word x maps an integer n to the number of m-binomial equivalence classes of factors of length n occurring in x. We study the first properties of m-binomial equivalence. We compute the m-binomial complexity of the Sturmian words and of the Thue-Morse word. We also mention the possible avoidance of 2-binomial squares.
Researchers
http://hdl.handle.net/2268/149313
10.1007/978-3-642-40579-2-23
This is the long version corresponding to the submission (limited to 12 pages). It contains an appendix with the omitted proofs.

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
binomial_final_short.pdfAuthor preprint174.64 kBView/Open

Additional material(s):

File Commentary Size Access
Open access
binomial_final_long.pdfLong version with ommitted proofs266.81 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.