论文标题
某些自由组和单型形态的后通信问题和均衡器
The Post Correspondence Problem and equalisers for certain free group and monoid morphisms
论文作者
论文摘要
明显的自由单型形态是一种形态，每个发电机的图像以不同的字母开头，沉浸式是自由组中的类似图。我们表明（同时）PCP是对自由组的浸入式的（同时）PCP，并提供了一种算法来计算称为均衡器的碱基的碱基，浸入浸入相同的值的基集中。我们还回答了有关均衡器等级的拖延问题。 相似的结果被证明是自由单粒细胞的明显形态。
A marked free monoid morphism is a morphism for which the image of each generator starts with a different letter, and immersions are the analogous maps in free groups. We show that the (simultaneous) PCP is decidable for immersions of free groups, and provide an algorithm to compute bases for the sets, called equalisers, on which the immersions take the same values. We also answer a question of Stallings about the rank of the equaliser. Analogous results are proven for marked morphisms of free monoids.
