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

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

Ronald V. Book

Publication date: 1982

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

zbMATH Keywords

context-free grammar; finite monadic Church-Rosser Thue system; polynomial-time decision procedure; Thue system on a finite alphabet

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q65: Abstract data types; algebraic specification

03B25: Decidability of theories and sets of sentences

20M35: Semigroups in automata theory, linguistics, etc.

20F10: Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)

03D03: Thue and Post systems, etc.

Related Items

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

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