Constructing finitely presented monoids which have no finite complete presentation
type: Item
instance of: scholarly article
title: Constructing finitely presented monoids which have no finite complete presentation
zbMATH Open document ID: 0876.20035
DOI: 10.1007/BF02676612
author: Masashi Katsura
author: Yuji Kobayashi
published in: Semigroup Forum
publication date: 1997-10-07T00:00:00Z
full work available at URL: https://eudml.org/doc/135529
review text: A complete rewriting system \(R\) over an alphabet \(\Sigma\) consists of a set of rules \(u\to v\) for words from the word monoid \(\Sigma^*\) such that the relation \(\to\) is noetherian and confluent. An application of a rule \(u\to v\) leads from a word \(x=x_1ux_2\) to \(y=x_1vx_2\), denoted by \(x\to_Ry\). Let \(\to^*_R\) be the reflexive and transitive closure of \(\to_R\), and let \(\leftrightarrow^*_R\) be the least congruence on \(\Sigma^*\) that contains \(\to_R\). The main features of a complete rewriting system \(R\) are: (1) for any word \(x\in\Sigma^*\) there exists a unique irreducible element \(\widehat x\) (for which no rule is applicable) such that \(x\to^*\widehat x\); (2) \(x\leftrightarrow^*_Ry\) if and only if \(\widehat x=\widehat y\). A monoid \(M\) is said to be presented by \(R\) if \(M=\Sigma^*/\leftrightarrow_R^*\). \textit{C. C. Squier} [J. Pure Appl. Algebra 49, 201-217 (1987; Zbl 0648.20045)] showed that there are finitely presented monoids (and groups) that have a solvable word problem, but which are not presented by a complete rewriting system. The authors of the present paper show that there is such a monoid that has a presentation with trivial homotopy (and hence this monoid satisfies Squier's condition \(FP_\infty\)).
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20M35
zbMATH DE Number: 1022337
zbMATH Keywords: complete rewriting systems
zbMATH Keywords: word problem
zbMATH Keywords: presentations of monoids
zbMATH Keywords: irreducible elements
zbMATH Keywords: finitely presented monoids
reviewed by: Tero Harju
MaRDI profile type: Publication
cites work: Q4846257
cites work: Finite derivation type implies the homological finiteness condition \(FP_ 3\)
cites work: For groups the property of having finite derivation type is equivalent to the homological finiteness condition \(FP_ 3\)
cites work: The Knuth-Bendix Completion Procedure and Thue Systems
cites work: Complete rewriting systems and homology of monoid algebras
cites work: A finitely presented monoid which has solvable word problem but has no regular complete presentation
cites work: A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
cites work: Word problems and a homological finiteness condition for monoids
cites work: A finiteness condition for rewriting systems
OpenAlex ID: W2058817145
Recommended article: A finitely presented monoid which has solvable word problem but has no regular complete presentation
Recommended article: Q3026992
Recommended article: Church-Rooser property and homology of monoids
Recommended article: New undecidability results for finitely presented monoids
Recommended article: A finiteness condition for rewriting systems
Recommended article: On deciding whether a monoid is a free monoid or is a group
Recommended article: Finite complete rewriting systems and the complexity of word problem
Recommended article: n-level rewriting systems
Recommended article: About the descriptive power of certain classes of finite string-rewriting systems
Recommended article: Finite complete rewriting systems for groups
description: scientific article; zbMATH DE number 1022337