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

algorithm; group; monoid; alphabet; regular Church-Rosser Thue system

Mathematics Subject Classification ID

68Q45: Formal languages and automata

20M05: Free semigroups, generators and relations, word problems

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

03D03: Thue and Post systems, etc.

Related Items

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