Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems

DOI10.2307/2000102zbMath0583.20054OpenAlexW4229731907MaRDI QIDQ3708211

Friedrich Otto

Publication date: 1985

Full work available at URL: https://doi.org/10.2307/2000102

zbMATH Keywords

transitive closuredecision problemelements of finite orderfinite monadic 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)

Related Items (5)

Thue systems as rewriting systems ⋮ Some polynomial-time algorithms for finite monadic Church-Rosser Thue 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 ⋮ On two problems related to cancellativity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decidable sentences of Church-Rosser congruences
• Groups, the theory of ends, and context-free languages
• Monadic Thue systems
• When is a monoid a group? The Church-Rosser case is tractable
• On monoids presented by a single relation
• Cancellation rules and extended word problems
• Une généralisation des ensembles de Dyck
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• Confluent and Other Types of Thue Systems
• On direct products of theories

This page was built for publication: Elements of Finite Order for Finite Monadic Church-Rosser Thue Systems