Complete semi-Thue systems for abelian groups

DOI10.1016/0304-3975(86)90117-9MaRDI QIDQ1087012zbMATH OpenOpenAlexFDO

Authors Volker Diekert

Publication date 1986

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(86)90117-9

zbMATH Keywords

decidable word problemfinite semi-Thue systemsfinitely generated abelian groupsrewriting systems

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Word problems, etc. in computability and recursion theory (03D40) Abelian groups (20K99) Free semigroups, generators and relations, word problems (20M05) Abstract data types; algebraic specification (68Q65)

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.

Recommendations

• Some combinatorial properties of complete semi-Thue systems
• Some generalized semi-thue systems
• scientific article; zbMATH DE number 6426
• Complete decompositions of finite abelian groups
• On finite commutative Thue systems
• Complete decompositions of Abelian groups
• Complete factorizations of finite abelian groups
• scientific article; zbMATH DE number 221463
• A completion for partially ordered Abelian groups

Cites work

• A finite Thue system with decidable word problem and without equivalent finite canonical system
• A note on a special one-rule semi-Thue system
• Finite complete rewriting systems and the complexity of word problem
• scientific article; zbMATH DE number 16608 (Why is no real title available?)
• scientific article; zbMATH DE number 3798986 (Why is no real title available?)
• New decision algorithms for finitely presented commutative semigroups
• Rational sets in commutative monoids
• Word problems and a homological finiteness condition for monoids

Cited in

(13)

• A note on a special one-rule semi-Thue system
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Commutative monoids have complete presentations by free (non-commutative) monoids
• An example of a one-relator group that is not a one-relation monoid
• Complexity, combinatorial group theory and the language of palutators
• On the Knuth-Bendix completion for concurrent processes
• Finite canonical rewriting systems for congruences generated by concurrency relations
• Theorem proving with group presentations: examples and questions
• SOME EXACT SEQUENCES FOR THE HOMOTOPY (BI-)MODULE OF A MONOID
• Abelian groups
• On weakly confluent monadic string-rewriting systems
• About the descriptive power of certain classes of finite string-rewriting systems
• Word problems over traces which are solvable in linear time

This page was built for publication: Complete semi-Thue systems for abelian groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1087012)