The binomial equivalence classes of finite words

DOI10.1142/S0218196720500459MaRDI QIDQ4970534zbMATH OpenFDO

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)

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

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)

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}^{\ast }$ by the $2$-binomial equivalence.

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

Cites work

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

Cited in

(15)

• Abelian combinatorics on words: a survey
• Avoiding 2-binomial squares and cubes
• Introducing q-deformed binomial coefficients of words
• Equations over the \(k\)-binomial monoids
• On Simon's congruence closure of a string
• New examples of words for which binomial complexities and subword complexity coincide
• Matching patterns with variables under Simon's congruence
• An equivalence relation on a set of words of finite length
• On some 2-binomial coefficients of binary words: geometrical interpretation, partitions of integers, and fair words
• A toolkit for Parikh matrices
• Binomial coefficients and enumeration of restricted words
• Another generalization of abelian equivalence: binomial complexity of infinite words
• On Simon's congruence closure of a string
• Binomial coefficients, valuations, and words
• On the number of distinct \(k\)-decks: enumeration and bounds

Describes a project that uses

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)