论文标题
双曲线和实际上nilpotent组的邮政对应问题
Post's correspondence problem for hyperbolic and virtually nilpotent groups
论文作者
论文摘要
Post的对应问题（PCP）是理论计算机科学中的一个经典决策问题，它询问是否存在一对免费的单体形态$ G，H \COLONς^*\toΔ^*$，是否存在任何非平地$ x \inς^*$，例如$ g（x）= h（x）$。 Post $γ$的通信问题取得了成对的组同构$ G，H \ COLON F（σ）\toγ$，并且同样询问是否存在$ x $，因此出于非元素的原因，$ g（x）= h（x）$持有。为了获得非元素解决方案而对$ x $施加的限制导致了对问题的几种解释；我们认为自然限制要求$ x \ notin \ ker（g）\ cap \ ker（h）$（h）$，并证明对PCP的解释是不可证明的，对于任意双曲线$γ$是不可证明的，但是当$γ$几乎是nilpotent时，可确定的。我们还研究了该问题，例如亚组，直接产品和有限扩展。当一张地图具有射层时，这个问题等于由于肌尼科夫，尼科尔和乌萨科夫而引起的解释。
Post's Correspondence Problem (the PCP) is a classical decision problem in theoretical computer science that asks whether for pairs of free monoid morphisms $g, h\colonΣ^*\toΔ^*$ there exists any non-trivial $x\inΣ^*$ such that $g(x)=h(x)$. Post's Correspondence Problem for a group $Γ$ takes pairs of group homomorphisms $g, h\colon F(Σ)\to Γ$ instead, and similarly asks whether there exists an $x$ such that $g(x)=h(x)$ holds for non-elementary reasons. The restrictions imposed on $x$ in order to get non-elementary solutions lead to several interpretations of the problem; we consider the natural restriction asking that $x \notin \ker(g) \cap \ker(h)$ and prove that the resulting interpretation of the PCP is undecidable for arbitrary hyperbolic $Γ$, but decidable when $Γ$ is virtually nilpotent. We also study this problem for group constructions such as subgroups, direct products and finite extensions. This problem is equivalent to an interpretation due to Myasnikov, Nikolev and Ushakov when one map is injective.
