Another generalization of abelian equivalence: binomial complexity of infinite words (Q496049): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / author | |||
Property / author: Pavel Salimov / rank | |||
Property / author | |||
Property / author: Pavel Salimov / rank | |||
Normal rank | |||
Property / review text | |||
Two words are abelian-equivalent if they induce the same Parikh vector, i.e., one can be obtained by permutation of symbols of the other. A generalization of this term is \(k\)-abelian equivalence, introduced by Karhumäki. Two words are \(m\)-abelian-equivalent, \(m\geq0\), if any of their factors of length at most \(m\) occurs in both words the same number of times. Another generalization -- \(m\)-binomial equivalence -- is obtained if occurrences of scattered subwords (subsequences) instead of occurrences of factors are counted. The number of occurrences of a scattered subword \(v\) in a word \(u\) is denoted as \(\binom {u}{v}\), since these counts have properties similar to those of binomial numbers. The \(m\)-binomial complexity of an infinite word \(x\) is a function \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \) expressing the number of \(m\)-binomial equivalence classes containing a factor of \(x\) of length \(n\). The paper deals with \(m\)-binomial complexity of two classes of infinite words. If \(x\) is a Sturmian word then it is known that \(x\) has constant abelian complexity, in particular, \(\mathbf{b}_{x}^{\left( 1\right) }\left( n\right) =2\) for \(n\geq0\). The authors prove a general result stating that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) =n+1\) for \(m\geq 2\), \(n\geq0\). If \(x\) is a fixed point of a Parikh-constant morphism (as the word of Thue-Morse) they prove that, for any \(m\geq2,\) there is a constant \(C_{x,m}\) such that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \leq C_{x,m}\) for all \(n\geq0\). They show as well that if an infinite recurrent word (a word where each finite factor occurs infinitely many times) \(x_{0}x_{1}\cdots\) has bounded \(2\)-binomial complexity, then the frequency \(\lim_{n\rightarrow\infty}\frac{\binom{x_{0}x_{1}\cdots x_{n-1}}{a}}{n}\) of each of its symbols \(a\) exists and is rational. Finally, the authors introduce a morphism mapping words to matrices and word concatenation to matrix product. The values occurring in the matrix assigned to a word \(v\) are of the form \(\binom{v}{z}\) where \(z\) is a prefix of a fixed word \(u\). The morphism is different from the well-known Parikh matrix morphism. | |||
Property / review text: Two words are abelian-equivalent if they induce the same Parikh vector, i.e., one can be obtained by permutation of symbols of the other. A generalization of this term is \(k\)-abelian equivalence, introduced by Karhumäki. Two words are \(m\)-abelian-equivalent, \(m\geq0\), if any of their factors of length at most \(m\) occurs in both words the same number of times. Another generalization -- \(m\)-binomial equivalence -- is obtained if occurrences of scattered subwords (subsequences) instead of occurrences of factors are counted. The number of occurrences of a scattered subword \(v\) in a word \(u\) is denoted as \(\binom {u}{v}\), since these counts have properties similar to those of binomial numbers. The \(m\)-binomial complexity of an infinite word \(x\) is a function \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \) expressing the number of \(m\)-binomial equivalence classes containing a factor of \(x\) of length \(n\). The paper deals with \(m\)-binomial complexity of two classes of infinite words. If \(x\) is a Sturmian word then it is known that \(x\) has constant abelian complexity, in particular, \(\mathbf{b}_{x}^{\left( 1\right) }\left( n\right) =2\) for \(n\geq0\). The authors prove a general result stating that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) =n+1\) for \(m\geq 2\), \(n\geq0\). If \(x\) is a fixed point of a Parikh-constant morphism (as the word of Thue-Morse) they prove that, for any \(m\geq2,\) there is a constant \(C_{x,m}\) such that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \leq C_{x,m}\) for all \(n\geq0\). They show as well that if an infinite recurrent word (a word where each finite factor occurs infinitely many times) \(x_{0}x_{1}\cdots\) has bounded \(2\)-binomial complexity, then the frequency \(\lim_{n\rightarrow\infty}\frac{\binom{x_{0}x_{1}\cdots x_{n-1}}{a}}{n}\) of each of its symbols \(a\) exists and is rational. Finally, the authors introduce a morphism mapping words to matrices and word concatenation to matrix product. The values occurring in the matrix assigned to a word \(v\) are of the form \(\binom{v}{z}\) where \(z\) is a prefix of a fixed word \(u\). The morphism is different from the well-known Parikh matrix morphism. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R15 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05A10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 11B65 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6482910 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
abelian equivalence | |||
Property / zbMATH Keywords: abelian equivalence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
binomial equivalence | |||
Property / zbMATH Keywords: binomial equivalence / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
factor complexity | |||
Property / zbMATH Keywords: factor complexity / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Sturmian word | |||
Property / zbMATH Keywords: Sturmian word / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Thue-Morse word | |||
Property / zbMATH Keywords: Thue-Morse word / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
Parikh-constant morphism | |||
Property / zbMATH Keywords: Parikh-constant morphism / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
recurrent word | |||
Property / zbMATH Keywords: recurrent word / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Anton Černý / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.025 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2468104078 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Balances for fixed points of primitive substitutions. / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumeration of factors in the Thue-Morse word / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Thue-Morse sequence and p-adic topology for the free monoid / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Complexity and special factors / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniform tag sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the factors of the Thue-Morse word on three symbols / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A limit theorem for set of subwords in deterministic TOL laguages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subword complexities of various classes of deterministic developmental languages without interactions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Sequence entropy and the maximal pattern complexity of infinite words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On a generalization of abelian equivalence and complexity of infinite words / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4341774 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4529547 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4681771 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A sharpening of the Parikh mapping / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Subword histories and Parikh matrices / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Substitutions in dynamics, arithmetics and combinatorics / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Avoiding 2-binomial squares and cubes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Balance and abelian complexity of the Tribonacci word / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Abelian complexity of minimal subshifts / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 19:26, 10 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Another generalization of abelian equivalence: binomial complexity of infinite words |
scientific article |
Statements
Another generalization of abelian equivalence: binomial complexity of infinite words (English)
0 references
16 September 2015
0 references
Two words are abelian-equivalent if they induce the same Parikh vector, i.e., one can be obtained by permutation of symbols of the other. A generalization of this term is \(k\)-abelian equivalence, introduced by Karhumäki. Two words are \(m\)-abelian-equivalent, \(m\geq0\), if any of their factors of length at most \(m\) occurs in both words the same number of times. Another generalization -- \(m\)-binomial equivalence -- is obtained if occurrences of scattered subwords (subsequences) instead of occurrences of factors are counted. The number of occurrences of a scattered subword \(v\) in a word \(u\) is denoted as \(\binom {u}{v}\), since these counts have properties similar to those of binomial numbers. The \(m\)-binomial complexity of an infinite word \(x\) is a function \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \) expressing the number of \(m\)-binomial equivalence classes containing a factor of \(x\) of length \(n\). The paper deals with \(m\)-binomial complexity of two classes of infinite words. If \(x\) is a Sturmian word then it is known that \(x\) has constant abelian complexity, in particular, \(\mathbf{b}_{x}^{\left( 1\right) }\left( n\right) =2\) for \(n\geq0\). The authors prove a general result stating that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) =n+1\) for \(m\geq 2\), \(n\geq0\). If \(x\) is a fixed point of a Parikh-constant morphism (as the word of Thue-Morse) they prove that, for any \(m\geq2,\) there is a constant \(C_{x,m}\) such that \(\mathbf{b}_{x}^{\left( m\right) }\left( n\right) \leq C_{x,m}\) for all \(n\geq0\). They show as well that if an infinite recurrent word (a word where each finite factor occurs infinitely many times) \(x_{0}x_{1}\cdots\) has bounded \(2\)-binomial complexity, then the frequency \(\lim_{n\rightarrow\infty}\frac{\binom{x_{0}x_{1}\cdots x_{n-1}}{a}}{n}\) of each of its symbols \(a\) exists and is rational. Finally, the authors introduce a morphism mapping words to matrices and word concatenation to matrix product. The values occurring in the matrix assigned to a word \(v\) are of the form \(\binom{v}{z}\) where \(z\) is a prefix of a fixed word \(u\). The morphism is different from the well-known Parikh matrix morphism.
0 references
abelian equivalence
0 references
binomial equivalence
0 references
factor complexity
0 references
Sturmian word
0 references
Thue-Morse word
0 references
Parikh-constant morphism
0 references
recurrent word
0 references
0 references