The binomial equivalence classes of finite words

DOI10.1142/S0218196720500459zbMath1453.68145arXiv2001.11732MaRDI QIDQ4970534

Marie Lejeune, Matthieu Rosenfeld, Michel Rigo

Publication date: 14 October 2020

Published in: International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2001.11732

zbMATH Keywords

context-free languagesbinomial coefficientscombinatorics on words2-nilpotent groupnil-2 groupk-binomial equivalence

Mathematics Subject Classification ID

Combinatorics on words (68R15) Permutations, words, matrices (05A05) Formal languages and automata (68Q45) Nilpotent groups (20F18)

Related Items

Equations over the \(k\)-binomial monoids, A toolkit for Parikh matrices, Abelian combinatorics on words: a survey, On the number of distinct \(k\)-decks: enumeration and bounds, On Simon's congruence closure of a string, On Simon's congruence closure of a string

Uses Software

• ALGOL 60

Cites Work

• On a generalization of abelian equivalence and complexity of infinite words
• Another generalization of abelian equivalence: binomial complexity of infinite words
• On cardinalities of \(k\)-abelian equivalence classes
• Some characterizations of Parikh matrix equivalent binary words
• Criteria for the matrix equivalence of words
• Automaticity. I: Properties of a measure of descriptional complexity
• Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence
• A sharpening of the Parikh mapping
• Finding the Growth Rate of a Regular of Context-Free Language in Polynomial Time
• Generalized Parikh mappings and homomorphisms
• k-Abelian Equivalence and Rationality
• Bounded Algol-Like Languages
• The growth function of context-free languages