科研之友
微信
新浪微博
Facebook
分享链接
摘要
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. Two words x and y are m-binomially equivalent, if, for all words v of length at most m, the binomial coefficients of x and v and respectively, y and v are equal. 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 two classes of words: Sturmian words and (pure) morphic words that are fixed points of Parikh-constant morphisms like the Thue-Morse word, i.e., images by themorphism of all the letters have the same Parikh vector. We prove that the frequency of each symbol of an infinite recurrent word with bounded 2-binomial complexity is rational.
- 出版日期2015-10-11
