Paper published in a journal (Scientific congresses and symposiums)
Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
Rigo, Michel; Salimov, Pavel
2013In Lecture Notes in Computer Science, 8079, p. 217-228
Peer reviewed
 

Files


Full Text
binomial_final_short.pdf
Author preprint (178.84 kB)
Download
Annexes
binomial_final_long.pdf
(273.21 kB)
Long version with ommitted proofs
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
Sturmian word; Thue-Morse word; Abelian complexity; Combinatorics on words; Binomial coefficient
Abstract :
[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.
Disciplines :
Mathematics
Author, co-author :
Rigo, Michel  ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Salimov, Pavel ;  Université de Liège - ULiège > Département de mathématique > Mathématiques discrètes
Language :
English
Title :
Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
Publication date :
2013
Event name :
WORDS 2013
Event place :
Turku, Finland
Event date :
from 16-09-2013 to 20-09-2013
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer, Berlin, Germany
Special issue title :
Combinatorics on Words
Volume :
8079
Pages :
217-228
Peer reviewed :
Peer reviewed
Commentary :
This is the long version corresponding to the submission (limited to 12 pages). It contains an appendix with the omitted proofs.
Available on ORBi :
since 27 May 2013

Statistics


Number of views
177 (29 by ULiège)
Number of downloads
286 (5 by ULiège)

Scopus citations®
 
9
Scopus citations®
without self-citations
3
OpenCitations
 
2

Bibliography


Similar publications



Contact ORBi