论文标题
原始单词集
Primitive Sets of Words
论文作者
论文摘要
给定有限字母$ a $的（有限或无限的）子集$ x $，$ x $的排名是$ x \ subseteq f^*$的最小基数。我们说，如果不存在$ a^*$的$ k $元素生成的sibonoid $ m $，则如果不存在最多由包含$ m $的$ k $单词生成的另一个subonoid，则是{\ em $ k $ -maximal}。如果它是$ | x | $ -maximal submonoid的基础，我们将其称为$ x \ subseteq a^*$ {\ em primitive}。此定义涵盖了原始单词的概念 - 实际上，$ \ {w \} $是原始集合，并且仅当$ w $是原始词时。根据定义，对于任何集合$ x $，都存在原始集合$ y $，以便$ x \ subseteq y^*$。因此，我们称$ y $ a {\ em原始根}的$ x $。作为主要结果，我们证明，如果一套的排名$ 2 $，则它具有独特的原始根。为了获得此结果，我们证明了两个$ 2 $ - maximal subonoids的相交是一个空的单词或一个由一个单个原始单词生成的sibonoid。对于一个单词$ w $，我们说如果可以将$ w $的$ \ {x，y \} $是$ w $的{\ em bi-root}，如果$ w $可以写为$ x $和$ y $和$ y $和$ y $ and $ \ \ {x，x，y \ \} $的副本的串联。我们证明，每个原始单词$ w $最多都有一个bi-root $ \ {x，y \} $，这样$ | x |+| y | <\ sqrt {| w |} $。也就是说，一个单词的双根是唯一的，只要单词相对于根的大小（长度）足够长。我们的结果也与以前研究伪重复的方法进行了比较，其中在$ a^*$上定义了形态涉及功能$θ$。在此设置中，定义了$θ$ - 功率，$θ$ - 主要和$θ$ - root的概念，并且显示任何单词都具有唯一的$θ$ - 主要词根。可以通过我们的方法来获得此结果，显示一个$ w $是$θ$ - 主要是且仅当$ \ {w，θ（w）\} $是原始集合时。
Given a (finite or infinite) subset $X$ of the free monoid $A^*$ over a finite alphabet $A$, the rank of $X$ is the minimal cardinality of a set $F$ such that $X \subseteq F^*$. We say that a submonoid $M$ generated by $k$ elements of $A^*$ is {\em $k$-maximal} if there does not exist another submonoid generated by at most $k$ words containing $M$. We call a set $X \subseteq A^*$ {\em primitive} if it is the basis of a $|X|$-maximal submonoid. This definition encompasses the notion of primitive word -- in fact, $\{w\}$ is a primitive set if and only if $w$ is a primitive word. By definition, for any set $X$, there exists a primitive set $Y$ such that $X \subseteq Y^*$. We therefore call $Y$ a {\em primitive root} of $X$. As a main result, we prove that if a set has rank $2$, then it has a unique primitive root. To obtain this result, we prove that the intersection of two $2$-maximal submonoids is either the empty word or a submonoid generated by one single primitive word. For a single word $w$, we say that the set $\{x,y\}$ is a {\em bi-root} of $w$ if $w$ can be written as a concatenation of copies of $x$ and $y$ and $\{x,y\}$ is a primitive set. We prove that every primitive word $w$ has at most one bi-root $\{x,y\}$ such that $|x|+|y|<\sqrt{|w|}$. That is, the bi-root of a word is unique provided the word is sufficiently long with respect to the size (sum of lengths) of the root. Our results are also compared to previous approaches that investigate pseudo-repetitions, where a morphic involutive function $θ$ is defined on $A^*$. In this setting, the notions of $θ$-power, $θ$-primitive and $θ$-root are defined, and it is shown that any word has a unique $θ$-primitive root. This result can be obtained with our approach by showing that a word $w$ is $θ$-primitive if and only if $\{w, θ(w)\}$ is a primitive set.
