Homogeneous Thue systems and the Church-Rosser property

DOI10.1016/0012-365X(84)90177-8zbMATH Open0546.03019MaRDI QIDQ798317FDOQ798317

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)

Cites Work

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

Cited In (15)

• The undecidability of the preperfectness of Thue systems
• Undecidable questions related to Church-Rosser Thue systems
• THE INCLUSION PROBLEM OF CONTEXT-FREE LANGUAGES: SOME TRACTABLE CASES
• Thue systems as rewriting systems
• Some undecidable termination problems for semi-Thue systems
• 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
• 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
• 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)