Algorithmic Problems for Amalgams of Finite Semigroups
Algorithmic Problems for Amalgams of Finite Semigroups
复制标题
有限半群并合的算法问题
DOI：
10.1006/jabr.1999.8138
复制
发表时间：
2000
影响因子：
0.9
通讯作者：
M. Sapir
中科院分区：
文献类型：
--
作者：
M. Sapir
本文证明了存在两个有限的4-幂零半群的合并体，使得相应的合并积有一个不可判定的字问题。我们还证明了有限半群拼图在任意半群中的可嵌入性问题和有限半群拼图在有限半群中的可嵌入性问题是不可判定的。我们使用了几种不同版本的Minsky算法和Slobodskoj关于有限群普适理论不可判定性的结果。
Abstract We prove that there exists an amalgam of two finite 4-nilpotent semigroups such that the corresponding amalgamated product has an undecidable word problem. We also show that the problem of embeddability of finite semigroup amalgams in any semigroups and the problem of embeddability of finite semigroup amalgams into finite semigroups are undecidable. We use several versions of Minsky algorithms and Slobodskoj's result about undecidability of the universal theory of finite groups.