Normal Forms for Free Aperiodic Semigroups
Normal Forms for Free Aperiodic Semigroups
复制标题
自由非周期半群的范式
DOI：
--
复制
发表时间：
2001
影响因子：
0.8
通讯作者：
Jon McCammond
中科院分区：
文献类型：
--
作者：
Jon McCammond
隐式运算ω是一元运算，它将有限半群中的每个元素赋给它所生成的子半群中唯一的幂等元。利用ω可以得到一个定义良好的代数，称为自由非周期半群。在本文中，我们引入了一个特定的、相当初级的伪恒等式列表，我们证明了对于每一个n， n生成的自由非周期半群是由这个伪恒等式列表定义的，然后我们用这个识别来证明它有一个可决的词问题。用隐式运算的语言，证明了有限非周期半群的伪变是κ-递归的。这向证明每一个有限半群的Krohn-Rhodes复杂度是可决定的方向迈出了关键的一步。
The implicit operation ω is the unary operation which sends each element of a finite semigroup to the unique idempotent contained in the subsemigroup it generates. Using ω there is a well-defined algebra which is known as the free aperiodic semigroup. In this article we introduce a specific and rather elementary list of pseudoidentitites, we show that for each n, the n-generated free aperiodic semigroup is defined by this list of pseudoidentities, and then we use this identification to show that it has a decidable word problem. In the language of implicit operations, this shows that the pseudovariety of finite aperiodic semigroups is κ-recursive. This completes a crucial step towards showing that the Krohn–Rhodes complexity of every finite semigroup is decidable.