Complete semi-Thue systems for abelian groups
type: Item
instance of: scholarly article
title: Complete semi-Thue systems for abelian groups
zbMATH Open document ID: 0609.68028
DOI: 10.1016/0304-3975(86)90117-9
author: Volker Diekert
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: We show that there are infinitely many examples of finite semi-Thue systems with decidable word problem and which have no finite equivalent noetherian and confluent \((=complete)\) reduction system. These examples have a very simple algebraic structure: they are abelian groups. More precisely, we develop necessary and sufficient conditions for the existence of complete semi-Thue systems for presentations of finitely generated abelian groups.
Mathematics Subject Classification ID: 68Q65
Mathematics Subject Classification ID: 20M05
Mathematics Subject Classification ID: 20K99
Mathematics Subject Classification ID: 03D03
Mathematics Subject Classification ID: 03D40
zbMATH DE Number: 3986634
zbMATH Keywords: rewriting systems
zbMATH Keywords: finite semi-Thue systems
zbMATH Keywords: decidable word problem
zbMATH Keywords: finitely generated abelian groups
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90117-9
OpenAlex ID: W2073165419
cites work: Q3973295
cites work: New decision algorithms for finitely presented commutative semigroups
cites work: Finite complete rewriting systems and the complexity of word problem
cites work: Rational sets in commutative monoids
cites work: A note on a special one-rule semi-Thue system
cites work: A finite Thue system with decidable word problem and without equivalent finite canonical system
cites work: Q4743710
cites work: Word problems and a homological finiteness condition for monoids
Recommended article: Some combinatorial properties of complete semi-Thue systems
Recommended article: Some generalized semi-thue systems
Recommended article: Q4712332
Recommended article: Complete decompositions of finite abelian groups
Recommended article: On finite commutative Thue systems
Recommended article: Complete decompositions of Abelian groups
Recommended article: Complete factorizations of finite abelian groups
Recommended article: Q4696953
Recommended article: A completion for partially ordered Abelian groups
description: scientific article; zbMATH DE number 3986634