On the binomial equivalence classes of finite words

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. We provide an algorithm generating the 2-binomial equivalence class of a word. For k ≥ 2 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 (also called free nilpotent group of class 2) on m generators is isomorphic to the quotient of the free monoid {1, . . . , m}^∗ by the 2-binomial equivalence.