When is a monoid a group? The Church-Rosser case is tractable

DOI10.1016/0304-3975(82)90072-XzbMath0489.68021OpenAlexW1994922201WikidataQ127857713 ScholiaQ127857713MaRDI QIDQ1166924

Ronald V. Book

Publication date: 1982

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

Full work available at URL: https://doi.org/10.1016/0304-3975(82)90072-x

zbMATH Keywords

context-free grammarfinite monadic Church-Rosser Thue systempolynomial-time decision procedureThue system on a finite alphabet

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Abstract data types; algebraic specification (68Q65) Decidability of theories and sets of sentences (03B25) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Thue and Post systems, etc. (03D03)

Related Items (10)

Decidable sentences of Church-Rosser congruences ⋮ An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group ⋮ Decision problems for finite special string-rewriting systems that are confluent on some congruence class ⋮ It is undecidable whether a finite special string-rewriting system presents a group ⋮ Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems ⋮ Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems ⋮ Contributions of Ronald V. Book to the theory of string-rewriting systems ⋮ Finite complete rewriting systems for the Jantzen monoid and the Greendlinger group ⋮ Some undecidability results for non-monadic Church-Rosser Thue systems ⋮ On deciding whether a monoid is a free monoid or is a group

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Testing for the Church-Rosser property
• On a special monoid with a single defining relation
• Monadic Thue systems
• Infinite regular Thue systems
• Une généralisation des ensembles de Dyck
• Confluent Reductions: Abstract Properties and Applications to Term Rewriting Systems
• Confluent and Other Types of Thue Systems
• Tree-Manipulating Systems and Church-Rosser Theorems

This page was built for publication: When is a monoid a group? The Church-Rosser case is tractable