Homogeneous Thue systems and the Church-Rosser property

DOI10.1016/0012-365X(84)90177-8zbMath0546.03019MaRDI QIDQ798317

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

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

Related Items

On the regular equivalence problem for regular Thue systems, Thue systems as rewriting systems, A note on thue systems with a single defining relation, Confluence of one-rule Thue systems, Some undecidable termination problems for semi-Thue systems, Solvability of word equations modulo finite special and confluent string-rewriting systems is undecidable in general, Cancellation rules and extended word problems, THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES, The Inclusion Problem of Context-Free Languages: Some Tractable Cases, Contributions of Ronald V. Book to the theory of string-rewriting systems, Undecidable questions related to Church-Rosser Thue systems, Almost all one-rule Thue systems have decidable word problems, The undecidability of the preperfectness of Thue systems

Cites Work

• The equation \(a_ M=b^ Nc^ P\) in a free group
• Testing for the Church-Rosser property
• On a special monoid with a single defining relation
• On monoids presented by a single relation
• Infinite regular Thue systems
• Undecidable questions related to Church-Rosser Thue systems
• Confluent and Other Types of Thue Systems
• A note on special thue systems with a single defining relation
• Unnamed Item
• Unnamed Item
• Unnamed Item