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

DOI10.1016/0020-0190(87)90149-9zbMath0626.20025OpenAlexW2056285149MaRDI QIDQ580494

Friedrich Otto, Klaus Madlener

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

complexityalgorithmword problemmonoid presentationstring-rewriting

Mathematics Subject Classification ID

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

Related Items (2)

The problem of deciding confluence on a given congruence class is tractable for finite special string-rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class

Cites Work

• A note on a special one-rule semi-Thue system
• A finite Thue system with decidable word problem and without equivalent finite canonical system
• On deciding whether a monoid is a free monoid or is a group
• On deciding the confluence of a finite string-rewriting system on a given congruence class
• Confluent and Other Types of Thue Systems
• Unnamed Item
• Unnamed Item
• Unnamed Item

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