Complete semi-Thue systems for abelian groups

DOI10.1016/0304-3975(86)90117-9zbMath0609.68028OpenAlexW2073165419MaRDI QIDQ1087012

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

rewriting systemsfinitely generated abelian groupsdecidable word problemfinite semi-Thue systems

Mathematics Subject Classification ID

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

Related Items (10)

SOME EXACT SEQUENCES FOR THE HOMOTOPY (BI-)MODULE OF A MONOID ⋮ 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 ⋮ Finite canonical rewriting systems for congruences generated by concurrency relations ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Word problems over traces which are solvable in linear time ⋮ On weakly confluent monadic string-rewriting systems ⋮ Abelian groups ⋮ On the Knuth-Bendix completion for concurrent processes

Cites Work

• Unnamed Item
• Unnamed Item
• Finite complete rewriting systems and the complexity of word problem
• A note on a special one-rule semi-Thue system
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• Word problems and a homological finiteness condition for monoids
• New decision algorithms for finitely presented commutative semigroups
• Rational sets in commutative monoids

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