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 等数据库收录! |
|