scientific article; zbMATH DE number 4014693
[For the entire collection see Zbl 0619.00025.] The main purpose of this paper is to describe a negative answer to the following question: Does every finitely presented monoid with a decidable word problem have a presentation (\(\Sigma\) ;R) where R is a finite canonical rewriting system? To obtain this answer a certain homological finiteness condition for monoids is considered. If M is a monoid that can be presented by a finite canonical rewriting system, then M is an \((FP)_ 3\)-monoid. Since there are well-known examples of finitely presented groups that have easily decidable word problem, but that do not meet this condition, this implies that there are finitely presented monoids (and groups) with decidable word problem that cannot be presented by finite canonical rewriting systems.
- A finiteness condition for rewriting systems
- Church-Rooser property and homology of monoids
- On deciding whether a monoid is a free monoid or is a group
- About the descriptive power of certain classes of finite string-rewriting systems
- Constructing finitely presented monoids which have no finite complete presentation
- Pseudo-natural algorithms for the word problem for finitely presented monoids and groups
- On deciding whether a monoid is a free monoid or is a group
- Word problems and a homological finiteness condition for monoids
- Complexity, combinatorial group theory and the language of palutators
- Infinite convergent string-rewriting systems and cross-sections for finitely presented monoids
- A finiteness condition for rewriting systems
- Constructing finitely presented monoids which have no finite complete presentation
- A new finiteness condition for monoids presented by complete rewriting systems (after Craig C. Squier)
- The monadic theory of finite representations of infinite words
- Ends for subsemigroups of finite index.
- Characterizing the normal forms of a finitely presented monoid
- scientific article; zbMATH DE number 3871338 (Why is no real title available?)
- A decidable word problem without equivalent canonical term rewriting system
- Church-Rooser property and homology of monoids
- Finite Monoids: From Word to Circuit Evaluation
- Cross-sections for finitely presented monoids with decidable word problems
- New undecidability results for finitely presented monoids
- Context-free rewriting systems and word-hyperbolic structures with uniqueness
- FDT is undecidable for finitely presented monoids with solvable word problems
- Conditional semi-Thue systems for presenting monoids
- A rewriting coherence theorem with applications in homotopy type theory
- Decidability problem for exponential equations in finitely presented groups
- A finitely presented monoid which has solvable word problem but has no regular complete presentation
- Finite complete rewriting systems and the complexity of word problem
- About the descriptive power of certain classes of finite string-rewriting systems
- Complete rewriting systems and homology of monoid algebras
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3026992)