论文标题
Cayley多项式计算组
Cayley Polynomial-Time Computable Groups
论文作者
论文摘要
我们提出了对Cayley自动组的新概括，改变了计算乘法的时间复杂性以及正常形式代表的语言复杂性。我们首先考虑在类$ \ Mathcal C $中具有正常形式语言的组，并在某个受限的Turing Machine模型（位置 - 信仰一式录像带）上以线性时间计算的发电机乘以乘法。我们表明，保留了自动组的许多算法属性（二次时间词问题），证明了各种闭合属性，并表明该类很大。例如，它包括所有虚拟的多环类。然后，我们将其推广到在类$ \ Mathcal C $中具有正常形式语言的组，以及在（标准）Turing Machine上在多项式时间中计算的生成器乘法。特别感兴趣的是$ \ MATHCAL C = \ MATHRM {REG} $（常规语言类）。我们证明$ \ mathrm {reg} $ - Cayley多项式计算组包括所有有限生成的nilpotent组，花圈产品$ \ mathbb z_2 \ wr \ mathbb z^2 $和汤普森的$ f $。
We propose a new generalisation of Cayley automatic groups, varying the time complexity of computing multiplication, and language complexity of the normal form representatives. We first consider groups which have normal form language in the class $\mathcal C$ and multiplication by generators computable in linear time on a certain restricted Turing machine model (position-faithful one-tape). We show that many of the algorithmic properties of automatic groups are preserved (quadratic time word problem), prove various closure properties, and show that the class is quite large; for example it includes all virtually polycyclic groups. We then generalise to groups which have normal form language in the class $\mathcal C$ and multiplication by generators computable in polynomial time on a (standard) Turing machine. Of particular interest is when $\mathcal C= \mathrm{REG}$ (the class of regular languages). We prove that $\mathrm{REG}$-Cayley polynomial-time computable groups includes all finitely generated nilpotent groups, the wreath product $\mathbb Z_2 \wr \mathbb Z^2$, and Thompson's group $F$.
