The binomial equivalence classes of finite words

DOI10.1142/S0218196720500459zbMATH Open1453.68145arXiv2001.11732MaRDI QIDQ4970534FDOQ4970534

Authors: Marie Lejeune, Matthieu Rosenfeld, Michel Rigo 

Publication date: 14 October 2020

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

Abstract: Two finite words $u$ and $v$ are $k$-binomially equivalent if, for each word $x$ of length at most $k$, $x$ appears the same number of times as a subsequence (i.e., as a scattered subword) of both $u$ and $v$. This notion generalizes abelian equivalence. In this paper, we study the equivalence classes induced by the $k$-binomial equivalence with a special focus on the cardinalities of the classes. We provide an algorithm generating the $2$-binomial equivalence class of a word. For $kgeq2$ and alphabet of $3$ or more symbols, the language made of lexicographically least elements of every $k$-binomial equivalence class and the language of singletons, i.e., the words whose $k$-binomial equivalence class is restricted to a single element, are shown to be non context-free. As a consequence of our discussions, we also prove that the submonoid generated by the generators of the free nil-$2$ group on $m$ generators is isomorphic to the quotient of the free monoid ${1,ldots,m}^{*}$ by the $2$-binomial equivalence.

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

Recommendations

• Equations over the \(k\)-binomial monoids
• \(k\)-abelian equivalence and rationality
• Another generalization of abelian equivalence: binomial complexity of infinite words
• Another generalization of abelian equivalence: binomial complexity of infinite words
• \(k\)-abelian equivalence and rationality

zbMATH Keywords

combinatorics on wordscontext-free languagesbinomial coefficients2-nilpotent groupnil-2 groupk-binomial equivalence

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (11)

• Avoiding 2-binomial squares and cubes
• Equations over the \(k\)-binomial monoids
• On Simon's congruence closure of a string
• Matching patterns with variables under Simon's congruence
• An equivalence relation on a set of words of finite length
• A toolkit for Parikh matrices
• Binomial coefficients and enumeration of restricted words
• On Simon's congruence closure of a string
• Binomial coefficients, valuations, and words
• On the number of distinct \(k\)-decks: enumeration and bounds
• Abelian combinatorics on words: a survey

Uses Software

• ALGOL 60

This page was built for publication: The binomial equivalence classes of finite words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4970534)