首页 | 本学科首页   官方微博 | 高级检索  
     


Constructing finitely presented monoids which have no finite complete presentation
Authors:Masashi Katsura  Yuji Kobayashi
Affiliation:(1) Department of Mathematics Faculty of Science, Kyoto Sangyo University, 607 Kyoto, Japan;(2) Department of Information Science Faculty of Science, Toho University, 274 Funabashi, Japan
Abstract: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.
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号