论文标题
免费群体和无上下文语言中元素方程式的理想
Ideals of equations for elements in a free group and context-free languages
论文作者
论文摘要
令$ f $为有限生成的免费组，让$ h \ le f $为有限生成的子组。 $ h $中的系数的元素$ g \ in f $的方程是$ w（x）\ in H*\ langle x \ rangle $，因此$ w（g）= 1 $ in $ f $;方程的度数是$ w（x）$的环状减少中的$ x $和$ x^{ - 1} $的出现数量。给定一个元素$ g \在f $中，我们认为理想的$ \ mathfrak {i} _g \ subseteq h*\ langle x \ langle x \ rangle $ for $ g $的方程$，in $ h $ in $ h $;我们使用不含上下文的语言研究$ \ mathfrak {i} _g $的结构。 我们描述了一种新算法，该算法确定$ \ mathfrak {i} _g $是否微不足道；该算法在多项式时间内运行。我们还描述了一种多项式时间算法，该算法在\ mathbb {n} $中给定的$ d \决定是否subset $ \ mathfrak {i} _ {g，d} \ subseteq \ mathfrak {i}我们提供了一种多项式时间算法，该算法计算$ \ mathfrak {i} _g $中非平凡方程的最低度$ d _ {\ min} $。我们在$ d _ {\ min} $上提供了尖锐的上限。最后，我们研究了$ \ mathfrak {i} _g $和$ \ mathfrak {i} _ {g，d} $中（循环减少）方程的数量的增长。我们证明这种生长是多项式的或指数级的，并且我们提供了一种多项式时算法，该算法计算生长的类型（包括生长程度，如果是多项式）。
Let $F$ be a finitely generated free group, and let $H\le F$ be a finitely generated subgroup. An equation for an element $g\in F$ with coefficients in $H$ is an element $w(x)\in H*\langle x \rangle$ such that $w(g)=1$ in $F$; the degree of the equation is the number of occurrences of $x$ and $x^{-1}$ in the cyclic reduction of $w(x)$. Given an element $g\in F$, we consider the ideal $\mathfrak{I}_g\subseteq H*\langle x \rangle$ of equations for $g$ with coefficients in $H$; we study the structure of $\mathfrak{I}_g$ using context-free languages. We describe a new algorithm that determines whether $\mathfrak{I}_g$ is trivial or not; the algorithm runs in polynomial time. We also describe a polynomial-time algorithm that, given $d\in\mathbb{N}$, decides whether or not the subset $\mathfrak{I}_{g,d}\subseteq\mathfrak{I}_g$ of all degree-$d$ equations is empty. We provide a polynomial-time algorithm that computes the minimum degree $d_{\min}$ of a non-trivial equation in $\mathfrak{I}_g$. We provide a sharp upper bound on $d_{\min}$. Finally, we study the growth of the number of (cyclically reduced) equations in $\mathfrak{I}_g$ and in $\mathfrak{I}_{g,d}$ as a function of their length. We prove that this growth is either polynomial or exponential, and we provide a polynomial-time algorithm that computes the type of growth (including the degree of the growth if it's polynomial).
