An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group

DOI10.1016/0304-3975(89)90145-XzbMath0677.20049MaRDI QIDQ1123272

Louxin Zhang

Publication date: 1989

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

zbMATH Keywords

algorithmgroupmonoidalphabetregular Church-Rosser Thue system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Thue and Post systems, etc. (03D03)

Related Items (1)

Decision problems for finite special string-rewriting systems that are confluent on some congruence class

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• Some undecidability results for non-monadic Church-Rosser Thue systems
• On deciding whether a monoid is a free monoid or is a group
• Complexity of certain decision problems about congruential languages
• Elements of finite order for finite weight-reducing and confluent Thue systems
• On a special monoid with a single defining relation
• Monadic Thue systems
• When is a monoid a group? The Church-Rosser case is tractable
• On monoids presented by a single relation
• Infinite regular Thue systems
• Une généralisation des ensembles de Dyck
• Confluent and Other Types of Thue Systems

This page was built for publication: An efficient algorithm to decide whether a monoid presented by a regular Church-Rosser Thue system is a group