论文标题
关于有限词的二项式等效类
On the binomial equivalence classes of finite words
论文作者
论文摘要
两个有限的单词$ u $和$ v $是$ k $ binom上等价的，如果对于最多$ k $的每个单词$ x $，则$ x $的数量与$ u $和$ v $的子序列（即，作为分散的子词）相同的次数。这个概念概括了阿贝尔等效性。在本文中，我们研究了由$ k $ binmial等价造成的等价类别，特别关注班级的基础性。我们提供一种算法生成一个单词的$ 2 $ binorial等价类。对于$ k \ geq 2 $和$ 3 $或更多符号的字母，用词典的语言，每一个$ k $ binomial等价类别的词典最少的元素和单元的语言，即$ k $ k $ k $ bibinmial等价类别的单词，仅限于单个元素，显示为非上下文。由于我们的讨论，我们还证明了免费的nil-nil- $ 2 $组生成的$ m $生成器上的下monoid与$ 2 $ -2 $ -Binomial Equivalence the Free Monoid $ \ {1，\}^{*} $同构。
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 $k \geq 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 on $m$ generators is isomorphic to the quotient of the free monoid $\{ 1, \ldots , m\}^{*}$ by the $2$-binomial equivalence.
