Homogeneous Thue systems and the Church-Rosser property

DOI10.1016/0012-365X(84)90177-8MaRDI QIDQ798317zbMATH OpenFDO

Authors Ronald V. Book

Publication date 1984

Published in Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

Church-Rosser propertyfinite homogeneous Thue systemmonoid presented by a Thue system

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Free semigroups, generators and relations, word problems (20M05) Word problems, etc. in computability and recursion theory (03D40)

Recommendations

• scientific article; zbMATH DE number 3898258
• The Church-Rosser property and special Thue systems
• Groups Presented by Finite Two-Monadic Church-Rosser Thue Systems
• scientific article; zbMATH DE number 4037834
• On reduced thue systems

Cites work

• scientific article; zbMATH DE number 3528212 (Why is no real title available?)
• scientific article; zbMATH DE number 3224578 (Why is no real title available?)
• scientific article; zbMATH DE number 3416078 (Why is no real title available?)
• A note on special thue systems with a single defining relation
• Confluent and Other Types of Thue Systems
• Infinite regular Thue systems
• On a special monoid with a single defining relation
• On monoids presented by a single relation
• Testing for the Church-Rosser property
• The equation \(a_ M=b^ Nc^ P\) in a free group
• Undecidable questions related to Church-Rosser Thue systems

Cited in

(21)

• The undecidability of the preperfectness of Thue systems
• A note on regular classes in special Thue systems
• Undecidable questions related to Church-Rosser Thue systems
• Thue systems as rewriting systems
• Some undecidable termination problems for semi-Thue systems
• scientific article; zbMATH DE number 3880671 (Why is no real title available?)
• scientific article; zbMATH DE number 3898258 (Why is no real title available?)
• scientific article; zbMATH DE number 3941518 (Why is no real title available?)
• Contributions of Ronald V. Book to the theory of string-rewriting systems
• The uniform conjugacy problem for finite church—Rosser thue systems is NP-complete
• Confluence of one-rule Thue systems
• On reduced thue systems
• A note on thue systems with a single defining relation
• Cancellation rules and extended word problems
• Almost all one-rule Thue systems have decidable word problems
• scientific article; zbMATH DE number 4037834 (Why is no real title available?)
• The inclusion problem of context-free languages: some tractable cases
• The Inclusion Problem of Context-Free Languages: Some Tractable Cases
• The Church-Rosser property and special Thue systems
• On the regular equivalence problem for regular Thue systems
• Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general

This page was built for publication: Homogeneous Thue systems and the Church-Rosser property

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q798317)