On deciding whether a monoid is a free monoid or is a group
From MaRDI portal
Publication:1075439
DOI10.1007/BF00268077zbMath0592.20059OpenAlexW2090238248MaRDI QIDQ1075439
Publication date: 1986
Published in: Acta Informatica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf00268077
Generators, relations, and presentations of groups (20F05) Free semigroups, generators and relations, word problems (20M05) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)
Related Items
Computing presentations for subgroups of polycyclic groups and of context-free groups ⋮ Thue systems as rewriting systems ⋮ An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group ⋮ About the descriptive power of certain classes of finite string-rewriting systems ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ Commutativity in groups presented by finite Church-Rosser Thue systems ⋮ It is undecidable whether a finite special string-rewriting system presents a group ⋮ When is an extension of a specification consistent? Decidable and undecidable cases ⋮ On weakly confluent monadic string-rewriting systems ⋮ Using string-rewriting for solving the word problem for finitely presented groups ⋮ ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS ⋮ New results on the prefix membership problem for one-relator groups ⋮ Contributions of Ronald V. Book to the theory of string-rewriting systems ⋮ On two problems related to cancellativity
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Decidable sentences of Church-Rosser congruences
- Some undecidability results for non-monadic Church-Rosser Thue systems
- Complexity results on the conjugacy problem for monoids
- When is a monoid a group? The Church-Rosser case is tractable
- Church–Rosser Thue Systems that Present Free Monoids
