Another generalization of abelian equivalence: binomial complexity of infinite words

DOI10.1016/j.tcs.2015.07.025zbMath1330.68243OpenAlexW2468104078MaRDI QIDQ496049

Michel Rigo, Pavel Salimov

Publication date: 16 September 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2015.07.025

zbMATH Keywords

Sturmian wordThue-Morse wordabelian equivalencefactor complexityrecurrent wordbinomial equivalenceParikh-constant morphism

Mathematics Subject Classification ID

Factorials, binomial coefficients, combinatorial functions (05A10) Binomial coefficients; factorials; (q)-identities (11B65) Combinatorics on words (68R15)

Related Items (27)

Scattered Factor-Universality of Words ⋮ Reconstructing Words from Right-Bounded-Block Words ⋮ Weighted prefix normal words: mind the gap ⋮ Equations over the \(k\)-binomial monoids ⋮ Binomial complexities and Parikh-collinear morphisms ⋮ Absent Subsequences in Words ⋮ Abelian combinatorics on words: a survey ⋮ A compactness property of the \(k\)-abelian monoids ⋮ On the number of distinct \(k\)-decks: enumeration and bounds ⋮ Longest Common Subsequence with Gap Constraints ⋮ Automaticity and Parikh-Collinear Morphisms ⋮ On the 2-binomial complexity of the generalized Thue-Morse words ⋮ Subsequences in bounded ranges: matching and analysis problems ⋮ Characterizations of families of morphisms and words via binomial complexities ⋮ Absent subsequences in words ⋮ Unnamed Item ⋮ Avoiding abelian powers cyclically ⋮ On $k$-abelian equivalence and generalized Lagrange spectra ⋮ On the additive complexity of a Thue-Morse-like sequence ⋮ Relations on words ⋮ Unnamed Item ⋮ Computing the \(k\)-binomial complexity of the Thue-Morse word ⋮ Templates for the \(k\)-binomial complexity of the Tribonacci word ⋮ The binomial equivalence classes of finite words ⋮ On the Lie complexity of Sturmian words ⋮ GAPS IN THE THUE–MORSE WORD ⋮ Reconstructing Words from Right-Bounded-Block Words

Cites Work

• On a generalization of abelian equivalence and complexity of infinite words
• Substitutions in dynamics, arithmetics and combinatorics
• Balance and abelian complexity of the Tribonacci word
• Thue-Morse sequence and p-adic topology for the free monoid
• A limit theorem for set of subwords in deterministic TOL laguages
• Subword complexities of various classes of deterministic developmental languages without interactions
• Complexity and special factors
• Balances for fixed points of primitive substitutions.
• On the factors of the Thue-Morse word on three symbols
• Enumeration of factors in the Thue-Morse word
• Subword histories and Parikh matrices
• Avoiding 2-binomial squares and cubes
• Another Generalization of Abelian Equivalence: Binomial Complexity of Infinite Words
• Abelian complexity of minimal subshifts
• A sharpening of the Parikh mapping
• Sequence entropy and the maximal pattern complexity of infinite words
• Uniform tag sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Another generalization of abelian equivalence: binomial complexity of infinite words