Constructing finitely presented monoids which have no finite complete presentation
Constructing finitely presented monoids which have no finite complete presentation
复制标题
构造没有有限完整表示的有限表示幺半群
DOI：
--
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
Yuji Kobayashi
中科院分区：
文献类型：
--
作者：
M. Katsura;Yuji Kobayashi
Squier（1987）证明了如果一个幺半群是由一个有限的完全重写系统定义的，那么它满足同调有限性条件FP 3，并利用这个事实，他给出了有可解的字问题但不能由有限的完全系统表示的幺半群（群）。在本文中，我们表明，一个幺半群不能有一个有限的完整的表现，如果它包含某些特殊的元素。这一发现使我们能够直接地、初等地构造没有有限完全表示的幺半群。本文给出了一个非线性表示幺半群，它具有（1）一个线性时间可解的字问题，（2）线性增长，但（3）没有有限的完全表示。我们还给出了一个具有（1）线性时间可解的字问题，（2）Squier意义下的有限导子型，（3）FP∞性质，但（4）没有有限完全表示的幺半群.
Squier (1987) showed that if a monoid is defined by a finite complete rewriting system, then it satisfies the homological finiteness condition FP3, and using this fact he gave monoids (groups) which have solvable word problems but cannot be presented by finite complete systems. In the present paper we show that a monoid cannot have a finite complete presentation if it contains certain special elements. This observation enables us to construct monoids without finite complete presentation in a direct and elementary way. We give a finitely presented monoid which has (1) a word problem solvable in linear time and (2) linear growth but (3) no finite complete presentation. We also give a finitely presented monoid which has (1) a word problem solvable in linear time, (2) finite derivation type in the sense of Squier and (3) the property FP∞, but (4) no finite complete presentation.