Using string-rewriting for solving the word problem for finitely presented groups

DOI10.1016/0020-0190(87)90149-9MaRDI QIDQ580494zbMATH OpenOpenAlexFDO

Authors Klaus Madlener, Friedrich Otto

Publication date 1987

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(87)90149-9

zbMATH Keywords

algorithmcomplexitymonoid presentationstring-rewritingword problem

Mathematics Subject Classification ID

Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Review text

It is shown that the word problem for the group \(<\{a,b\}\), \(abba=1>\) can be solved through the technique of string-rewriting. The time complexity of the algorithm is given.

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
• Confluent and Other Types of Thue Systems
• scientific article; zbMATH DE number 3898258 (Why is no real title available?)
• scientific article; zbMATH DE number 3941518 (Why is no real title available?)
• scientific article; zbMATH DE number 1988983 (Why is no real title available?)
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• On deciding whether a monoid is a free monoid or is a group

Cited in

(5)

• The use of Knuth-Bendix methods to solve the word problem in automatic groups
• The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems
• scientific article; zbMATH DE number 475444 (Why is no real title available?)
• An Isabelle/HOL formalization of semi-Thue and conditional semi-Thue systems
• Decision problems for finite special string-rewriting systems that are confluent on some congruence class

This page was built for publication: Using string-rewriting for solving the word problem for finitely presented groups

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