论文标题
求解多项式半程上的均匀线性方程
Solving homogeneous linear equations over polynomial semirings
论文作者
论文摘要
对于$ \ mathbb {r} $的子集$ b $，用$ \ operatatorName {u}（b）表示$是$ \ mathbb {r} [x] $的（univariate）多项式的半元素，这些$ b $严格为$ b $。令$ \ mathbb {n} [x] $为具有非阴性整数系数的（单变量）多项式的半度。我们研究了多项式半度的均质线性方程的解决方案$ \ operatotorName {u}（b）$和$ \ mathbb {n} [x] $。特别是，我们证明了局部全球全球原则，用于在这些半段中求解单个均匀的线性方程。然后，我们显示了在$ \ mathbb {n} [x] [x] $的单个同质线性方程式上确定非零解决方案的存在。 我们对这些多项式半度的研究在很大程度上是由花圈产品中的几个半群算法问题$ \ mathbb {z} \ wr \ mathbb {z} $。 As an application of our results, we show that the Identity Problem (whether a given semigroup contains the neutral element?) and the Group Problem (whether a given semigroup is a group?) for finitely generated sub-semigroups of the wreath product $\mathbb{Z} \wr \mathbb{Z}$ is decidable when elements of the semigroup generator have the form $(y, \pm 1)$.
For a subset $B$ of $\mathbb{R}$, denote by $\operatorname{U}(B)$ be the semiring of (univariate) polynomials in $\mathbb{R}[X]$ that are strictly positive on $B$. Let $\mathbb{N}[X]$ be the semiring of (univariate) polynomials with non-negative integer coefficients. We study solutions of homogeneous linear equations over the polynomial semirings $\operatorname{U}(B)$ and $\mathbb{N}[X]$. In particular, we prove local-global principles for solving single homogeneous linear equations over these semirings. We then show PTIME decidability of determining the existence of non-zero solutions over $\mathbb{N}[X]$ of single homogeneous linear equations. Our study of these polynomial semirings is largely motivated by several semigroup algorithmic problems in the wreath product $\mathbb{Z} \wr \mathbb{Z}$. As an application of our results, we show that the Identity Problem (whether a given semigroup contains the neutral element?) and the Group Problem (whether a given semigroup is a group?) for finitely generated sub-semigroups of the wreath product $\mathbb{Z} \wr \mathbb{Z}$ is decidable when elements of the semigroup generator have the form $(y, \pm 1)$.
